Bonjour,

Le plus grand nombre entier positif refusé par la machine (machine analytique de Babbage) est 77.

Bonjour,

Wow sacré défi ! Pas évident de trouver une méthode sans programmation ici; et encore sans réelle certitude.

Bon, comme d'antant j'admirais Michael Jordan, je propose .

Pour ce qui est de la machine, comme je viens de l'acheter aux puces il y a 23 jours..., je propose LA Machine de Türing.

Merci pour ce défi.

Tout d'abord, établissons quelques propriétés simples :
* Si est accepté par la machine, alors est accepté également.
En effet, et , donc et
* De la même façon, on montre que si est accepté par la machine, alors

sont acceptés. D'autres "déductions" peuvent être faites, mais celles-ci suffisent...
* On remarque également que tout carré parfait non nul est accepté

On écrit ensuite tous les nombres de 1 à 100 par exemple, et l'on entoure les nombres que l'on sait être accepté par la machine : on entoure dans un premier temps tous les carrés, puis à partir de ces nombres acceptés, on entoure d'autres nombres déduits (comme 1 est entouré, 2*1+2, 2*1+8, 2*1+9, 3*1+6 et 3*1+8 sont également acceptés), puis l'on recommence ...
On remarque alors qu'il semble qu'à partir de 24, tous les nombres sont entourés. (En fait, 32 n'est  pas entouré, mais la décomposition 18+9+3+2 montre qu'il est quand même accepté par la machine). On va donc le démontrer, en supposant que l'on ait déjà démontré (par ce crible) que tous les nombres compris (au sens large) entre 24 et 57 sont acceptés par la machine.

Soit pour , l'hypothèse : "Tous les nombres compris entre et sont acceptés par la machine".
- est OK
- Supposons que est vraie. Montrons que est vraie, càd que est accepté.
* Soit est pair : alors, est compris entre et et est donc accepté, d'après l'hypothèse . Donc, est également accepté.
* Soit est impair : alors, est compris entre et et est donc accepté. Alors, est également accepté.
Donc, est vraie.

On en déduit donc que tous les nombres supérieurs ou égaux à 24 sont acceptés par la machine.
On teste le nombre 23, qui se révèle être refusé. 23 est donc le plus grand entier refusé par la machine.

PS : Je suis ouvert à toute démo plus simple et surtout plus courte que la mienne ... Ca me semble très tarabiscoté pour un exercice qui semble facile. Mais au vu du nombre de réponses, ca ne doit pas être si facile que ca ...
La machine semble être la Difference Machine.

bonjour, et merci pour cette énigme

poser la question comme tu le fait, Minkus, m'indique, de toute évidence et à moins d'un gros piège, qu'a partir d'une valeur, il existe toujours une solution pour décomposer un nombre acceptable par la machine.


Remarquant alors que tous les carrés étaient acceptables (en effet a² peut s'écrire sous la forme a * a et a* 1/a = 1) j'ai cherché des solutions pour les autres nombres.

A partir de 24, et ce jusqu'a 50, j'ai toujours réussi (pafois avec du mal) à trouver une solution.

j'en déduit que le plus grand nombre entier positif refusé par la machine est le nombre 23

en esperant qu'il n'y en ai pas d'autres plus grand,

@ plus, Chaudrack

PS: Si j'ai juste, je suis curieux de voir la démonstration de ce phénomène étrange..(ben si j'ai faux, aussi)

Bonjour, le plus grand nombre refusé est 77.

Pour la machine, je chercherai quand j'aurai réussi à squatter un ordi assez longtemps.

J'ai mis très longtemps à poster car je n'ai pas trouvé de démonstration; je me suis donc rabattu sur une méthode empirique, avec laquelle je trouve 51
Sans beaucoup de garantie...

Je ne sais plus sur quel livre de maths j'ai lu que tous les nombres à partir de 25 ont cette propriété.


Mais comme
25 = 5 + 5 + 5 + 5 + 5
et
1/5+1/5+1/5+1/5+1/5 = 1

et que

24 = 12 + 6 + 4 +  2
et  
1/12 + 1/6 +1/4 + 1/2 = (1 + 2 + 3 + 6)/12 = 1

Je propose comme solution :

[i]23 EST LE DERNIER NOMBRE NON ACCEPTE PAR LA MACHINE A NOMBRES[/i]

Bonjour !

Je pense que le plus grand entier refusé par la machine est 23.

C'est vraiment sans conviction !!! J'ai cherché longuement avec papier+crayon, sans rien trouver de décisif pour arriver à un quelconque résultat. Finalement hier j'ai écrit une implémentation de la machine à nombres en java. Malheureusement d'une part l'execution est très lente (complexité n² je pense) et l'utilisation d'appels récursifs provoque des dépassements de pile... Bref je n'ai pas pu tester au delà du rang 110.

Néanmoins dans la liste des solutions (nombres acceptés par la machine) on constate que plus on avance dans les entiers, plus le nombre de possibilités s'accroit pour les écrire sous une forme qui convient. Cela me rassure un peu sur ma réponse, même si ce n'est pas aussi bien qu'une justification théorique...

Merci en tout cas pour ce défi très... coriace ! Et très curieux de voir les réponses des autres mathiliens !

Pour la question subsidiaire je suis un peu plus sûr de moi ! Il s'agit de l'une des machines à calculer de Charles Babbage. Voir lien wikipedia :



A++

J'ai fini par trouver une décomposition pour 51=4+4+5+6+12+20
Ce qui fait que la bonne réponse doit être 32...

Bonjour à tous.

Pour ce défi assez difficile, je tiens à vous proposer une correction détaillée. (Attention c'est un peu long.) Je commencerai par montrer que 77 est bien acceptable puis je démontrerai que tout nombre supérieur ou égal à 24 l'est aussi. Pour conclure, j'expliquerai pourquoi 23 ne l'est pas. C'est un peu ce qu'a fait nobody d'ailleurs.

Première partie : 77 n'est pas la réponse au défi.

J'ai eu un peu peur en voyant les premières réponses de Gloubi et Nofutur2 surtout que Gloubi donnait une référence. J'ai donc dû vérifier certaines choses pour arriver à :

   + + + + + + = 1 et 3 + 6 + 4 + 16 + 16 + 16 + 16 = 77.

Cela montre qu'il faut parfois se méfier de l'ami Google.

Cette solution n'est pas facile à trouver et je ne l'ai pas obtenue de façon directe ou par coup de chance. Je l'ai en fait déduite d'une autre solution comme je vais l'expliquer dans la deuxième partie.

Deuxième partie : Une première approche.

On cherche donc pour un nombre a donné une série d'entiers a₁, a₂.....a_n tels que a₁ + ..... a _n = a et 1/a₁ +....+1/a_n = 1. Si cette suite existe on dira que le nombre a est n-acceptable.

L'élément principal à prendre en compte est le nombre n de fractions nécessaires à la décomposition. Pour les petites valeurs de n les solutions sont assez faciles à trouver.

Pour n=1, une seule solution. 1 est donc 1-acceptable.

Pour n= 2, une seule solution avec + = 1. Le nombre 4 est donc 2-acceptable.

Pour n = 3.

+ + = 1 et 2 + 3 + 6 = 11

+ + = 1 et 2 + 4 + 4 = 10

+ + = 1 et 3 + 3 + 3 = 9

Les nombres 9, 10 et 11 sont donc 3-acceptables.

Pour n = 4 ça se complique.

En fait le plus petit des a_i est forcément entre 2 et n donc ici entre 2 et 4. En effet si le plus petit des a_i est 5 alors 4 ne peut pas être égal à 1.

Il faut donc commencer par essayer de caser puis au fur et à mesure les plus grosses fractions possibles, la 4e étant fixé par le calcul.

Exemple :

On commence avec puis on a donc déjà et on ne peut donc pas mettre sinon on retombe sur la solution avec n=3. On doit donc mettre . On arrive alors au total de et il suffit de rajouter .

Résultat : + + + = 1 et on obtient a = 2 + 3 + 7 + 42 = 54. Le nombre 54 est 4-acceptable.

En continuant de la sorte on trouve les solutions suivantes (données avec les entiers a_i mais sans les écritures fractionnaires):

37 = 2 + 3 + 8 + 24
32 = 2 + 3 + 9 + 18
30 = 2 + 3 + 10 + 15
29 = 2 + 3 + 12 + 12
31 = 2 + 4 + 5 + 20
24 = 2 + 4 + 6 + 12
22 = 2 + 4 + 8 + 8
20 = 2 + 6 + 6 + 6  dernière solution avec
22 = 3 + 3 + 4 + 12
18 = 3 + 3 + 6 + 6
17 = 3 + 4 + 4 + 6
16 = 4 + 4 + 4 + 4

Bilan :

Nombres 1-acceptables : 1
Nombres 2-acceptables : 4
Nombres 3-acceptables : 9, 10 et 11
Nombres 4-acceptables : 16, 17, 18, 20, 22, 24, 29, 30, 31, 32, 37, 54

Troisième partie : L'effet boule de neige.

Dans cette partie je vais montrer comment certains nombres acceptables permettent d'en obtenir d'autres.

Supposons que a est acceptable.

Alors on a 1/a₁ + ...... + 1/a_n = 1.

Divisons les 2 membres de cette égalité par 2 : 1/(2a₁) + ...... + 1/(2a_n) =

Ajoutons à chaque membre : + 1/(2a₁) + ....... + 1/(2a_n) = 1

Nous avons alors trouvé un nouveau nombre acceptable : 2 + 2a₁+ ..... + 2a_n = 2 + 2a

Ce nombre est (n+1)-acceptable car a est n-acceptable.

Nous avons démontré une propriété très intéressante : Si a est n-acceptable alors 2a + 2 est (n+1)-acceptable.

En appliquant cette propriété aux nombres déjà trouvés nous obtenons un nouveau groupe de nombres acceptables.

34 est ainsi 5-acceptable car 34 = 216 + 2

De même on obtient les nombres 36, 38, 42, 46, 50 à partir des nombres 17, 18, 20, 22, 24.

Pour trouver cette propriété nous avons utilisé le cas + = 1.

Mais on peut en trouver d'autres. Avec + +   = 1 nous obtenons des nombres du type 2a + 8 qui sont (n+2)-acceptables et avec + + = 1 nous obtenons 2a + 9.

En utilisant aussi les nombres 4-acceptables nous obtenons des nombres de la forme 3a + 6, 3a + 8, 2a + 29, 2a + 35 etc...

Ces propriétés nous permettent d'obtenir tous les nombres entre 24 et 55. Ensuite on peut facilement démontrer que les deux relations 2a+8 et 2a+9 permettent d'obtenir aussi tous les nombres supérieurs à 55. En effet, 56=224+8  57=224+9  58=225+8  59=225+9 etc...;

Ainsi nous obtenons le résultat suivant : Tout nombre supérieur ou égal à 24 est acceptable.

Quatrième partie : 23 est refusé.

En observant les nombres 1,2,3,4-acceptables, nous pouvons remarquer que le plus petit nombre 3-acceptable est 9 et le plus petit nombre 4-acceptable est 16.

En fait on peut démontrer (je vous épargnerai celle ci) que le plus petit nombre n-acceptable est n².

Par conséquent aucun nombre inférieur à 25 ne peut être 5-acceptable et encore moins  6,7,...-acceptables et donc tous les nombres inférieurs à 25 qui ne sont pas 1, 2, 3 ou 4-acceptables sont refusés.

Il y en a exactement 13 : 2, 3, 5, 6, 7, 8, 12, 13, 14, 15, 19, 21 et 23 le plus grand d'entre eux.

CQFD.

Merci d'avoir suivi

minkus

PS : Conbcernant la machine, le site où j'ai trouvé la photo disait que c'était la machine de Turing. Elle doit ressembler un peu à celle de Babbage...

Bonjour Minkus,

En pièce jointe, ma réference. Le pire c'est que ce que dit Gérard Villemin n'est pas faux!

Pour une fois que je trouve une solution à une énigme en moins de cinq minutes, et sans me fatiguer.

Comme quoi...

A+,
gloubi

Salut !

J'ai utilise google... pour la question subsidiaire ! En fait, si on cherche "Babbage" dans google-image, on tombe exactement sur la meme machine ! Par exemple sur ce site :

Je croyais de plus que Turing etait un pur theoricien, et qu'il n a jamais construit de vraie machine. Est-ce faux ?

Pour ce qui concerne l'enigme, pas le temps pour l'instant de lire dans le detail les reponses de tout le monde (meme si je suis impatient de pouvoir le faire). Je regarderai ce que sortait mon programme pour 77. En tout cas bravo a ceux qui ont repondu sans l'aide de l'informatique !!

A++

Il est possible que Gérard Villemin considère des nombres distincts comme cela est le cas dans son exemple.

Arf, j'aurais dû chercher un peu plus, j'avais trouvé la liste des nombres 1,2,3 et 4-acceptables ainsi que la relation 2a+2 mais je ne suis pas allé plus loin alors que j'étais près du but.
Tant pis pour moi

Fractal

bonjour,je n'ai p&as réussi à mettre au point une démonstration rigoureuse donc je me suis abstenue quant à la machine elle ressemble à mon métier à tisser;merci pour ce défi,je vais étudier les démonstrations des gagnants pour améliorer la mienne(si j'ai le temps car comme disait borneo ces jours ci finalement en vacances on n'a pas plus de temps que pendant l'année)
bonne soirée

Bonjour à tous

apres avoir posté, j'ai continué mes recherches sur ces nombres particuliers.

Il semblerait que ces nombres sont appellés "bons" tels que le présente ce site:



ou encore celui-ci



@ plus, Chaudrack

Chaudrak, à l'origine ces nombres viennent d'un exercice de la finale (niveau lycée) du 3e championnat des jeux mathématiques et logiques de 1989 qui s'intitulait "les nombres mauvais". C'est en tout cas ma source et je pense que le site de l'académie d'Amiens est moins ancien.

Il faut savoir qu'à l'époque la finale comportait 6 ou 7 exercices à réaliser en 3 heures si mes souvenirs sont bons. Il y avait d'ailleurs deux séances. Je m'en souviens bien car j'y ai moi même participé pour la première fois cette année là précisément, mais je n'ai pas eu cet exercice car j'étais au niveau collège. Ca date un peu

Salut Minkus,

Citation :
Il est possible que Gérard Villemin considère des nombres distincts comme cela est le cas dans son exemple.

Okay Torpedo, comme quoi on peut faire d'un même problème deux défis d'un coup...et quelques poissons au passage :D

Chapeau bas à ceux qui ont pensé à établir une (ou plusieurs) propriété "liminaire" de ces nombres dits" nombres bons", et ensuite à l'appliquer comme un crible d'abord aux nombres de 1 à 56 puis à tous les entiers.
De belles présentations de ces nombres et de belles démonstrations existent sur internet. Très intéressantes ... Merci à chaudrack pour ses indications.
Pour ma part, j'avoue ne pas avoir su comment aborder ce problème. Comme je n'aime pas ne pas répondre, je me suis contenté de recopier une réponse donnée par Gérard Villemin sur son site, en sachant très bien qu'il considérait une décomposition en nombres différents.
Encore bravo à ceux qui ont trouvé la solution !!!

Argh ! ça m'apprendra à copier bêtement des réponses trouvées sur le net

Pour un des derniers défis, je me suis "fortement inspiré" d'une solution trouvée sur le net : j'espère que cela ne va pas me coûter de poisson, comme borneo et nf2 ici