Des chiffres et des lettres

Vous connaissez cette émission qui passe sur la 3 ? Voici une énigme un peu ardue qui m'est venue à l'esprit il y a quelques années :

Vous vous rappelez du jeu où on vous propose une suite de nombres (exactement 6 nombres) qu'il ne faut utiliser qu'une seule fois avec les opérations + , - , x , / pour trouver un autre nombre ? Et ben là, mon énigme consiste à trouver une méthode générale pour calculer le plus grand nombre avec cette suite et ces opérations et non un autre nombre donnée. Par exemple, si on vous donne comme suite 1 , 2 , 3 , 4 , 5 , 6 , il faut chercher N_max : le plus grand nombre qu'on peut construire avec ces chiffres et ces opérations. En l'occurrence, N_max = (1+2)*3*4*5*6 = 1080.

il est déjà assez évident (mais à prouver bien sûr) que les opérateurs "/" et "-" ne vont pas exister dans la formule finale cherchée...

Soient 2 nombres entiers positifs A et B vérifiant (A<=B)

Comparons (A+B) et (AxB) ?

si A = 1, alors (A+B) > AxB.
si A > 1, alors (A+B) < AxB.

on peut généraliser ce résultat ...
Soient a,b,c,d,e et f, 6 nombres entiers > 0, triés dans l'ordre croissant...

si a = 1, alors, Nmax = (a+b).c.d.e.f

si a > 1, alors, Nmax = a.b.c.d.e.f

qu'est-ce que tu en penses?

Ben je peux dire que l'idée existe, mais je ne peux pas dire si c'est vrai ou si c'est faux avant d'avoir lu la démonstration complète. J'ajoute que les nombres peuvent se répéter (on peut avoir plusieurs 1).

Tout commence par des petits essais surtout lorsqu'on n'est pas dans un examen, et on n'est pas pressé par le temps

bien sur

Soit l'ensemble N = {n(i), i=1..m} formé de "m" nombres entiers >= 1.

Soient A et B deux ensembles définis par :
A = {n(i) tel que n(i) = 1}
B = {n(i) tel que n(i) >= 2}

On a donc: N = A U B.

L'objectif est de trouvé le plus grand nombre (qu'on appelle Nombre Maximal) qu'on peut obtenir en faisant des multiplications, additions, soustractions, divisions successives sur les éléments de N sans utiliser chaque élément plus qu'une seule fois. Cette condition s'applique même aux résultats de chaque opération arithmétique.

On appelle N_MAX, A_MAX et B_MAX les nombres maximaux respectifs des ensembles N, A et B.

On se propose de répondre aux deux questions suivantes :

0) Y-a-t-il des cas où on utilise les opérateur "-" ou "/" pour construire un nombre maximal?
1) Comment calculer A_MAX ?
2) Comment calculer B_MAX ?
3) En déduire le calcul de N_MAX ?

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

2) Comment calculer B_MAX ?

Soient p et q deux éléments de B tels que p<=q.

Code:

p <= q
p+q <= 2q
or
2<=p<=q
donc
2q<=p.q<=qxq

alors, on obtient: p+q<=pxq

Etant donné ce produit "pxq", on pourra répéter le même raisonnement avec les éléments restants de B : {"pxq"} U B\{p,q}.

On en déduit que le plus grand nombre formé par des opérations arithmétiques "x" et "+" sur les éléments de B est :

B_MAX = Produit(éléments de B)

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

1) Comment calculer A_MAX ?

Prenons un cas explicite. A = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}.

à suivre ...

La démonstration de B_max me laisse sceptique (mais pas le résultat car il est juste). Qu'est-ce qui te fait croire que B_max se construit de cette manière ? C'est-à-dire en calculant itérativement le max de deux entiers jusqu'à arriver à B_max. Peut-être qu'il y a une façon plus compliquée de calculer B_max en faisant intervenir à la fois plus que deux entiers ? Il te reste à démontrer qu'effectivement cette construction t'amène à B_max et non à une solution approchée.

Sami a écrit:La démonstration de B_max me laisse sceptique (mais pas le résultat car il est juste). Qu'est-ce qui te fait croire que n_max se construit de cette manière ? C'est-à-dire en calculant itérativement le max de deux entiers jusqu'à arriver à n_max. Peut-être qu'il y a une façon plus compliquée de calculer n_max en faisant intervenir à la fois plus que deux entiers ? Il te reste à démontrer qu'effectivement cette construction t'amène à n_max et non à une solution approchée.

J'espère que tu as bien réfléchi avant d'être aussi douteux

Si on se limite aux deux opération "+" et "x" ... Tout obtenu avec ces opérations (y compris celui que tu as appelé "construit d'une façon plus compliquée") est contruit itérativement.

C'est-à-dire en calculant itérativement le max de deux entiers jusqu'à arriver à n_max

J'ai parlé uniquement de "B_MAX".

Il te reste à démontrer qu'effectivement cette construction t'amène à n_max et non à une solution approchée.

Si B_MAX existe, il est évident qu'il est construit avec des opérations élémentaires "+" et "x".

Pour être plus formel, on appelle B_MAX(k), B_MAX à la kième étape de sa construction.
Vu la distributivité de la "x" par rapport à "+" (ou "+" par rapport à "x", j'ai oublié lol), le résultat suivant est "atomique" :

B_MAX(k+1) = B_MAX(k) (+,x) {n(i)} où n(i) est un nombre de B "non encore utilisé".

ça veut dire qu'une opération qui fait intervenir plusieurs opérateurs {+,x} et opérandes peut toujours être décomposée en une suite d'opérations binaires. Le résultat final est une somme de produits. Ce que j'ai essayé de prouver ci-dessus, c'est que si n(i)>1, le résultat final ne peut pas être une somme de produit de n(i), mais uniquement un produit de n(i).

La preuve est simple. Il suffit de montrer que A+B <= AxB.

J'espère que c'est plus clair.


(Désolé pour la nomenclature utilisée, elle peut être source de confusion)

Oui, tu as raison. Ce que je n'ai pas vu, c'est que tout nombre doit se construire de cette manière, y compris B_max
Ma démonstration est pratiquement équivalente à la tienne (je l'ai fait il y a longtemps...). J'utilise les mêmes notations :

B_max existe et est fini car n est fini.

Pour calculer B_max, on va certainement utiliser tous les n(i) , car sinon je pourrais toujours multiplier par les n(j) non utilisés à la fin pour obtenir un plus grand nombre.

Il existe une permutation de [[1,n]] que j'appelle θ telle que :

B_max = [...[ n(θ(1)) φ(1) n(θ(2)) ] φ(2) n(θ(3)) ].... n(θ(n-1)) ] φ(n-1) n(θ(n)) ]

avec :
quelque soit j dans [[1,n]] n(θ(j)) > 1
quelque soit k dans [[1,n-1]] φ(k) appartient à { + , x , / , -}

On voit bien que si on choisit un k dans [[1,n-1]] , φ(k) donnera un plus grand nombre si c'est une multiplication, car :

B_max(k, x) = [...[ n(θ(1)) φ(1) n(θ(2)) ] φ(2) n(θ(3)) ].... n(θ(k)) ] x n(θ(k+1)) ]

B_max(k, +) = [...[ n(θ(1)) φ(1) n(θ(2)) ] φ(2) n(θ(3)) ].... n(θ(k)) ] + n(θ(k+1)) ]

B_max(k, -) = [...[ n(θ(1)) φ(1) n(θ(2)) ] φ(2) n(θ(3)) ].... n(θ(k)) ] - n(θ(k+1)) ]

B_max(k, /) = [...[ n(θ(1)) φ(1) n(θ(2)) ] φ(2) n(θ(3)) ].... n(θ(k)) ] / n(θ(k+1)) ]

On a :

B_max(k , x) >= B_max(k , +)
Car : B_max(k-1, φ(k-1)) >= 2 et n(θ(k+1)) >=2
(Cette inéquation n'est valable que lorsqu'on prend les k de 1 vers n , c'est-à-dire de plus en plus grand, et non n'importe comment, ce qui nous affirme que B_max(k-1, φ(k-1)) >= 2)

B_max(k , +) >= B_max(k , - )
Car additionner donne un plus grand nombre que retrancher

B_max(k , +) >= B_max(k , / )
Car additionner donne un plus grand nombre que diviser

En itérant le k sur tous les φ(k), on conclue que : quelque soit k dans [[1,n-1]] , φ(k) est une multiplication.

Donc
B_max = Produit( n(i) , i=1..n )

"J'en profite pour vous demander s'il n'y a pas un moyen d'ajouter un interpréteur LaTeX dans le forum, car ça rendra les formules plus lisibles."

"J'en profite pour vous demander s'il n'y a pas un
moyen d'ajouter un interpréteur LaTeX dans le forum, car ça rendra les
formules plus lisibles."

Je vais voir !!! ça sera génial s'il en existe un.

2) Comment calculer A_MAX ?

Pour le moment je me contente de donner la formule à laquelle j'ai abouti !!!

Soit la notation suivante :
On appelle MAX(m) le nombre maximal qu'on peut former à partir de "m" chiffres "1".

Par exemple; MAX(5) = le nombre maximal de l'ensemble {1,1,1,1,1}. MAX(5) = (1+1+1)x(1+1) = 6.

[Vous devez être inscrit et connecté pour voir cette image]

A vous de "me vaincre" amicalement biensûr

@+

Je suis tout à fait d'accord avec toi pour les trois formules

Je viens de me rendre compte que ma démonstration est incomplète. La manière avec laquelle j'ai mis les parenthèses vertes est un cas spécial. Si on prend les nombres 2 , 3 , 4 et 5 , le nombre (2x3)+(4x5) ne peut pas être représenté par cette façon.
Je dois revoir tout ça.

nabiL a écrit:2) Comment calculer A_MAX ?

Pour le moment je me contente de donner la formule à laquelle j'ai abouti !!!

Soit la notation suivante :
On appelle MAX(m) le nombre maximal qu'on peut former à partir de "m" chiffres "1".

Par exemple; MAX(5) = le nombre maximal de l'ensemble {1,1,1,1,1}. MAX(5) = (1+1+1)x(1+1) = 6.

[Vous devez être inscrit et connecté pour voir cette image]

A vous de "me vaincre" amicalement biensûr

@+

J'ai démontré ce résultat. (j'espère que c'est correct biensûr, faut jamais être trop sûr de soi-même ).

Je vous laisse le soin d'y réfléchir ... au cas où vous trouverez une issue, on en parlera.