Sujet pour totomn ! ...

freddy · 16-08-2011 17:58:48

Hello tutti,

je viens de croiser sur le net une sujet qui devrait montrer à notre ami totomn la supériorité d'un raisonnement à une preuve informatique.

Le sujet : "Il y a fort longtemps, à Paris, un forain proposait aux badauds le pari suivant : il s'engageait à trouver en moins d'une minute deux sous ensembles disjoints (mais pas nécessairement exhaustifs) de nombre parmi 10 dont la somme des termes de chacun des sous ensemble était de même valeur. Les 10 nombres, tous distincts, étaient choisis par le badaud parmi les 100 nombres entiers compris entre 1 et 100. Le badaud pouvait miser jusqu'à 100 euros. Si le forain échouait, il versait au joueur 10 fois sa mise".

Le forain cessa le jour où nerosson, qui n'avait pas peur de venir faire la fête à Paris à cette époque, écouta le camelot, réfléchit quelques minutes, puis lui proposa d'inverser le jeu : à lui de relever le défi, au camelot de choisir les numéros et de miser.

Sauriez vous dire pourquoi ?

Un exemple :

le badaud choisit les nombres : {4, 12, 25, 32, 49, 51, 69, 70, 85, 99}

le forain trouve : {12,49} et {4,25,32} car 49+12= 32+25+4

Dernière modification par freddy (17-08-2011 06:49:28)

nerosson · 17-08-2011 14:21:48

Salut, freddy et tous les autres,

Une nouvelle preuve que j'ai vieilli !

Ta question sous-entend qu'il y a une méthode rationnelle pour trouver la réponse quels que soient les nombres choisis par le badaud. Je confesse que je ne l'ai pas trouvée. Je chercherai encore car le problème est intéressant.

J'ai également pris le problème à rebrousse-poil et cherché si on pouvait trouver une suite de dix nombres qui rende toute réponse impossible. Rien trouvé jusqu'ici.

Je note que ta réponse n'utilise que les cinq premiers nombres.

Ce qui atténue ma confusion, c'est qu'il y a déjà eu une cinquantaine de lecteurs et pas de réponse.

Je remarque aussi que les dix nombres de ton exemple sont tous pris dans des dizaines différentes.

Dernière modification par nerosson (17-08-2011 14:30:51)

freddy · 17-08-2011 14:42:15

Salut mon ami,

pour l'exemple, pas de souci, j'ai fait comme tu as dit, sans raison autre que celle "pour voir".

Pour la solution, je n'ai pas cherché mais pense qu'il peut y en avoir d'autres. Totomn nous dira.

Sinon, tu as bien compris : il y a un "truc" qui te rends certain de toujours trouver.

Hint : Pense aux chaussettes !!!

nerosson · 17-08-2011 15:24:31

Re,

99 +70 = 169
49 +51+69 = 169

Aucun mérite : je l'ai trouvé par tâtonnement !

P.S. Je ne peux pas employer la méthode expérimentale : j'ai tellement de tiroirs et si peu de chaussettes !

Dernière modification par nerosson (17-08-2011 15:31:03)

nerosson · 17-08-2011 16:44:16

Re,

69+32 = 101
85+12+4 = 101

Pas plus avancé ! ! !

nerosson · 17-08-2011 17:26:35

Re,

69+49 = 118
70+32+12+4 =118

J'ai beau comparer toutes ces réponses, je n'arrive pas à en dégager une loi commune.

thadrien · 17-08-2011 21:10:55

Salut,

Le raisonnement est un classique du genre :

* Il y a \(2^{10}-1=1023\) sous-ensembles non vides possibles.

* La somme des 10 nombres est comprise entre 1 et \(10*100=1000\). Il y a donc 1000 sommes possibles.

1024>1000, donc, d'après le principe des tiroirs, il y a obligatoirement deux sous-ensembles dont la somme des éléments est identique. Ils ne sont pas nécessairement disjoints, mais ce n'est pas grave, car il suffit d'enlever les éléments communs aux deux ensembles pour résoudre le problème.

Maintenant que l'on a prouvé l'existence de la solution, comment la déterminer ?

On peut procéder, par ordinateur, ainsi : on construit un tableau de 1000 cases, autant que de sommes possibles. Ensuite, on énumère les 1024 sous-ensembles possibles. Pour chaque sous-ensemble, on stocke le sous-ensemble dans la case du tableau correspondant à la somme des éléments de l'ensemble si cette dernière est vide. Si elle est déjà pleine, on retourne les deux ensembles, dont on aura au préalable retiré les éléments disjoints.

A noter que la démonstration est nécessaire à la construction de l'algorithme, ne serais-ce que pour déterminer les structures de données optimales à sa résolution.

Maintenant, comment résoudre ce problème à la main ?

On peut toujours trouver des bornes plus fines pour la somme, mais cela ne réduit qu'assez peu la taille du problème.

Je réfléchis encore à ce problème, mais plus tard.

freddy · 17-08-2011 22:08:48

Clap, clap, clap, clap, clap, ...., clap !

freddy · 18-08-2011 01:16:24

Re,

en fait, le total maximal = 955 = 91+92+ ... + 100, mais c'est un péché véniel.

Augustin · 18-08-2011 10:30:41

Bonjour,

Au moins avec Thadrien on réconcilie démonstration et utilisation de l'ordinateur, et on a les tiroirs por ranger ses chaussettes....
A défaut de peaufiner un algorithme, il faudrait ajouter les capacités associatives uniques de notre cerveau (calcul mental pour ce camelot qui certainement calculait vite en séparant unités et dizaines). Ce sont elles qui sous-tendent l'intuition quelquefois trop dédaignée...

Cordialement

nerosson · 18-08-2011 17:08:54

Salut à tous,

Moi, je comprends vite, mais il faut m'expliquer longtemps.

Alors, je voudrais bien que l'on m'explique comment, EN MOINS D' UNE MINUTE, ET PAR UN CALCUL MENTAL, on peut trouver deux sous-ensembles égaux.

Dans un problème tel que celui-ci, quand j'entends parler d'ordinateur et d' intuition, "je tire mon révolver", comme disait je-ne-sais-plus-qui à propos de je-ne-sais-plus-quoi.

Par ailleurs, étant donné qu'un ensemble peut se composer de deux à huit éléments (il faut bien en laisser deux pour l'autre ensemble), j'aimerais qu'on me confirme le nombre d' ensemble possibles (j'y arriverais sans doute, mais ça me prendrait du temps, mais c'est tellement plu simple de demander) ....

Ce que je lis me semble ressembler à de la force brute. La solution n'est pas là.

Dernière modification par nerosson (18-08-2011 17:15:53)

thadrien · 18-08-2011 20:32:16

nerosson a écrit :

Ce que je lis me semble ressembler à de la force brute. La solution n'est pas là.

Tu as entièrement raison !

Cependant, tu noteras que l'on a quand même avancé car, maintenant, on est sur et certain qu'il existe au moins une solution, tandis qu'avant, on cherchait dans le vide. Et on a une idée d'une approche permettant de la calculer.

Maintenant, comment faire le calcul de tête ? Aucune idée ! C'est pour cela que j'ai promis de réfléchir encore, mais après les révisions de partiels.

Dernière modification par thadrien (19-08-2011 00:36:37)

totomm · 19-08-2011 10:55:27

Bonjour,

nerosson a écrit :

Alors, je voudrais bien que l'on m'explique comment, EN MOINS D' UNE MINUTE, ET PAR UN CALCUL MENTAL, on peut trouver deux sous-ensembles égaux.

Utiliser le calcul mental ne vaut pas dire que rien n'est écrit : La liste des 10 nombres est écrite, et le camelot peut griffonner de son coté, tout en présentant un résultat écrit sous la liste...

On sait aussi qu'il y a des trucs qui facilitent le résultat. exemple :
Griffoner très vite (ou mémoriser) les différences 8, 13, 7, 7, 2, 18, 1, 15,...tilt 13+2=15
Je donne donc rapidement ce résultat : 70+25+51 = 85+12+49
et j'espère que vous allez me dire que vous êtes épaté : moins d'une minute je vous assure...

et il y a bien d'autres trucs. Enfant, j'observais les camelots sur les grands boulevards des grands magasins parisiens...

Et arrêtons d'opposer force brute et "raisonnement intelligent" : Toute méthode qui établit un résultat est bonne à considérer !

Cordialement

freddy · 19-08-2011 11:07:46

Salut,

je plussoie totomn, inutile de tout trouver, il suffit d'en trouver une. J'ai mis aussi moins d'une minute pour trouver le résultat de mon exemple, par simple recherche de différence (17, 13 + 4) ! ...

MAIS avant toute chose, il fallait prouver qu'une solution existait sûrement, ce que thadrien a fait avec brio.

C'était là un peut mon idée : une procédure "force brute" aurait établi qu'on peut trouver une solution (nombre fini de solutions), mais rien ne vaut une preuve formelle.

Et là, on voit bien comment l'informatique peut nous aider. Il y avait d'ailleurs un sujet qui a été relancé il y a quelque temps où nous avons tous trouvé des solutions informatiques après avoir conduit un raisonnement algébrique et géométrique pour nous assurer de l'existence d'au moins une solution. En clair, quand je sais de façon formelle qu'une solution (ou au moins une) existe, je peux alors la chercher avec l'aide de l'informatique. A l'inverse ...

nerosson · 19-08-2011 14:12:08

Salut à tous,

D'abord, merci de toutes ces réponses. C'est toujours bien de savoir qu'on a été lu et que quelqu'un a pris la peine de réfléchir à à ce qu'on a dit, même s'il n'est pas d'accord. Mais bien entendu, j'ai quelques remarques à faire.

D'abord toi freddy (tout le monde sait que j'ai un plaisir particulier à te houspiller).
C'est seulement maintenant que tu me dis que le coeur du problème, c'était de montrer qu'il y avait nécessairement une solution. Si la question avait été posée dans ce sens, peut-être (je répète : peut-être) que j'aurais trouvé. Tu avais trouvé une solution :j'ai consacré mes efforts à en chercher d' autres.

@Totomm et Hadrien: Hadrien à mieux cerné le problème que moi, puisqu'il a commencé par démontrer qu'il y avait obligatoirement une ou des solutions, alors que moi, n'ayant pas compris où était le coeur du problème, je n'ai pas su exploiter les chaussettes.

Totomm et freddy ont trouvé en moins d' une minute (je ne songe pas à mettre votre parole en doute), mais vous n' avez pas, me semble-t-il, ce que moi je me suis évertué à chercher : une technique particulière. Ce que vous me dites prouve simplement que vous avez le cerveau vif et que moi j'ai le cerveau lent, ce que je sais depuis toujours ET DONT JE N'AI JAMAIS EU HONTE : pour moi, l'important est de savoir si un cerveau progresse, que ce soit vite ou lentement est une question secondaire. D'ailleurs, je vais vous faire une confidence : il n'y a pas que le cerveau, tout ce que je fais je le fais lentement : Quant, à douze ans, je faisais les foins aux "Raverettes", j'exaspérais mon père parce que je semblais y mettre une sorte de nonchalance. Revenons, aux ensembles : vous avez trouvé vos réponses comme j'ai trouvé les miennes, mais plus vite.

Totomm, venons-en à la "force brute" : Je ne la néglige pas : quand, en cryptographie, je tombe sur un substitution, il est fréquent qu'avant toute autre recherche, j'essaye le Jules César sous sa forme brute (ça prend cinq minutes), pour éliminer d 'entrée de jeu cette possibilité avant d' entreprendre des recherches beaucoup plus longues et minutieuses. Et Gielev m'a dit qu'il faisait de même avec le "rail-fence" dans le cas d' une transposition.

Mais, bien plus souvent, la force brute est la solution du pauvre : on se rabat sur elle quand on n'a rien trouvé de mieux. Et souvent elle est d'une longueur qui la rend plus théorique que pratique. Un exemple : la sustitution monoalphabétique : si le cryptogramme est suffisamment long, on le décrypte aisément par le raisonnement. Par la force brute, il faudrait faire 26! (factorielle 26) essais.

Cordialement à tous.

freddy · 19-08-2011 14:30:46

nerosson a écrit :

Salut à tous,
D'abord, merci de toutes ces réponses. C'est toujours bien de savoir qu'on a été lu et que quelqu'un a pris la peine de réfléchir à à ce qu'on a dit, même s'il n'est pas d'accord. Mais bien entendu, j'ai quelques remarques à faire.
D'abord toi freddy (tout le monde sait que j'ai un plaisir particulier à te houspiller).
C'est seulement maintenant que tu me dis que le coeur du problème, c'était de montrer qu'il y avait nécessairement une solution. Si la question avait été posée dans ce sens, peut-être (je répète : peut-être) que j'aurais trouvé. Tu avais trouvé une solution :j'ai consacré mes efforts à en chercher d' autres.

Mon cher ami, si tu lis bien l'énoncé, il dit à peu près : "le forain cessa le jour où nerosson réfléchit quelques minutes et proposa au forain de renverser le jeu : à ce dernier de miser, à nerosson de trouver. Sauriez vous dire pourquoi ?". Pourquoi le forain cessa, donc.

Ceci voulait dire, de manière peut-être masquée pour certains, mais que je croyais claire pour au moins toi (oui, je sais, qui aime bien châtie bien !) que tu avais compris que le forain était toujours certain de trouver une solution ! Me serais je trompé sur tes facultés de compréhension et ta grande finesse d'esprit ???

PS : J'ai fourni un exemple car je me suis aperçu que, souvent, ici, un énoncé pouvait être mieux compris avec un exemple à l'appui (très classique en pédagogie, ce qui m'a toujours fait dire qu'il ne fallait jamais construire un exemple au hasard)

Dernière modification par freddy (19-08-2011 14:33:46)

nerosson · 19-08-2011 14:50:04

Salut à tous et à freedy en particulier,

Ce qui m'a frappé dans l'énoncé, c'est "en moins d'une minute". J'en ai conclu (à tort) qu'il y avait là une technique mathématique précise, alors qu'en fait, il y avait :
a) la certitude qu'il y aurait toujours une solution,
b) la confiance du forain dans son aptitude à calculer très vite, confiance que moi je n'ai pas, donc je n'aurais pas défié le forain.

Mes facultés de compréhension et ma grande finesse d 'esprit ? T'es pas un peu entrain de te payer ma tête ?

totomm · 19-08-2011 16:25:49

re-bonjour,

nerosson a écrit :

b) la confiance du forain dans son aptitude à calculer très vite, confiance que moi je n'ai pas, donc je n'aurais pas défié le forain.

Ce forain bon bonimenteur sait ausi perdre suffisamment de temps en temps pour allécher les clients...C'est bien sûr un complice qui empoche, tout en laissant voir aux badauds le genre de liste qui, soit-disant, FAIT GAGNER FACILEMENT. Et qui en fait est parmi les faciles en connaissant le(s) truc(s)...

Quant au principe des tiroirs de Dirichlet, c'est bien que ce soit THadrien qui l'ai rappelé...

Force Brute : C'est incroyable cette façon de considérer l'utilisation de l'ordinateur, quand justement il faut y mettre réflexion et intelligence du problème pour obtenir un résultat valide.
Certains semblent considérer qu'on devient ignorant des démonstrations mathématiques parce qu'on produit un résultat sur ordinateur : Répondre à "Comment fait on ?", c'est produire une méthode de construction d'un résultat sans se contenter de "démontrer qu"un résultat existe" ...

Cordialement

freddy · 25-08-2011 23:34:57

Salut totomn,

à ce propos, je serais preneur de la méthode que tu as développée pour arriver à établir les 32 5-grilles nécessaires et suffisantes pour retrouver les 220 3-grilles des nombres compris entre 1 et 12.

Te souviens tu ?

freddy · 26-08-2011 08:05:31

totomm a écrit :

re-bonjour,
nerosson a écrit :
b) la confiance du forain dans son aptitude à calculer très vite, confiance que moi je n'ai pas, donc je n'aurais pas défié le forain.
Ce forain bon bonimenteur sait aussi perdre suffisamment de temps en temps pour allécher les clients...C'est bien sûr un complice (le baron) qui empoche, tout en laissant voir aux badauds le genre de liste qui, soit-disant, FAIT GAGNER FACILEMENT. Et qui en fait est parmi les faciles en connaissant le(s) truc(s)...
Quant au principe des tiroirs de Dirichlet, c'est bien que ce soit THadrien qui l'ait rappelé...
Force Brute : C'est incroyable cette façon de considérer l'utilisation de l'ordinateur, quand justement il faut y mettre réflexion et intelligence du problème pour obtenir un résultat valide.
Certains semblent considérer (tu as des preuves de ce que tu avances ?) qu'on devient ignorant des démonstrations mathématiques parce qu'on produit un résultat sur ordinateur : Répondre à "Comment fait on ?", c'est produire une méthode de construction d'un résultat sans se contenter de "démontrer qu'un résultat existe" ...
Cordialement

Salut,

je suis d'accord que répondre à "comment fait on ?" est bien mieux que de se contenter de montrer que le résultat existe.

Toutefois, il me semble qu'il est nécessaire de montrer au préalable que le résultat existe avant de développer une méthode de recherche de résultat : j'en connais (et j'en suis) qui ont perdu un temps fou à chercher une solution à un problème qui n'en admettait pas ...

Sinon, tout ceci me rappelle une petite blague moqueuse bien connue : trois ingénieurs de trois écoles différentes, que nous appellerons X, Y et Z, construisent un ascenseur à sous marin à Brest.

L'ascenseur prend l'eau et noie un sous marin nucléaire d'attaque (oups). Z prend tout de suite une pompe aspirante pour vider l'ascenseur ; Y prend les plans et cherche l'erreur de calcul et enfin X dit sentencieusement : "Je savais bien qu'il y aurait une fuite"

PS : comment faisaient nos aînés quand l'ordinateur n'existait pas ?

Mstafa · 26-08-2011 10:38:01

Salut tout le monde,

Permettez moi de participer avec vous dans cette discussion et de vous présenter ce que j'ai trouvé :

Posons [tex]E=\lbrace a_1 , a_2 , ... , a_{10} \rbrace [/tex] l'ensemble de ces dix nombres,

Pour l’existence c'est déjà prouvée, mais je peux affirmer qu'il existe toujours deux sous ensemble disjoint de cardinal [tex]\leq 5[/tex] vérifiant la propriété.

En effet car le nombre de sous ensembles de cardinal [tex]\leq 5[/tex] est égale à [tex]C_{10}^{1} +... + C_{10}^{5} = 637 [/tex]

les sommes possibles pour ces ensembles sont comprises entre [tex]1[/tex] et [tex]490 [/tex]

Donc l'application qui à un ensemble de cardinal ≤5 fait correspondre ça somme ne peut pas être injective.

Et par suite il existe deux sous ensembles qui ont la même somme.

Moi je veux étudier le cas simple où les deux ensembles sont de cardinal [tex]\leq 2[/tex]

Et quand est ce que le Forain sera sûr qu'il est bien dans ce cas ?

à mon avis le Forain doit nécessairement passer par ce cas, la méthode que je pense convenable est la suivante :

Exemple [tex] E = \lbrace 2 , 3 , 13 , 25 , 35 , 45 , 51 , 66 , 70 , 90 \rbrace[/tex]

2 3 13 25 35 45 51 66 70 90 E
5 15 27 37 47 53 68 72 92 E + 2
16 28 38 48 54 69 73 93 E + 3
38 48 58 64 79 83 103 E + 13
60 70 76 91 95 115 . . .
80 86 101 105 125
96 111 115 135
117 121 141
136 156
160

Le Forain s’arrêtera lorsqu'un nombre va se répéter par exemple :

38 = 35 + 3

38 = 25 + 13 Don il s’arrêtera à la 4 e^ème ligne.

Pour répondre à la question :

Le nombre de sous ensembles de cardinal [tex]\leq 2[/tex] est égale à 55

les sommes possibles pour ces ensembles sont comprises entre [tex]a_1[/tex] et [tex]a_{10} + a_{9} [/tex]

Donc une condition nécessaire pour tomber sur ce cas est que : [tex]a_{10} + a_{9} -a_1 +1< 55[/tex]

et qui n'est pas une condition suffisante. mais il y a grande chance pour tomber sur ce cas ( peut-on calculer la probabilité pour voir)

Si le triangle précédant est composé uniquement de nombres différents le Forain va surement perdre ? !

totomm · 26-08-2011 17:26:45

Bonjour,
Je suis inscrit car Fred m'a permis de corriger un adresse erronée (.fr au lieu de .com). Merci à Fred

freddy a écrit :

Salut totomn,
à ce propos, je serais preneur de la méthode que tu as développée pour arriver à établir les 32 5-grilles nécessaires et suffisantes pour retrouver les 220 3-grilles des nombres compris entre 1 et 12.
Te souviens tu ?

Je recherche et je posterai le programme Python (que je crois avoir gardé) dans le forum "Programmation" d'ici quelques jours.
Cordialement

Mstafa a écrit :

Si le triangle précédant est composé uniquement de nombres différents le Forain va surement perdre ? !

La méthode des différences retrouve aussi, rapidement, une égalité. Dans le cas présenté : 1, 10, 12, 10...tilt
donc on écrit immédiatement 35+3 et 25+13. Cette méthode balaie les sommes de plus de 2 termes, mais n'est pas aussi exhautive pour les sommes de 2 termes ?!

Cordialement

totomm · 26-08-2011 17:43:14

re,

freddy a écrit :

je suis d'accord que répondre à "comment fait on ?" est bien mieux que de se contenter de montrer que le résultat existe.
Toutefois, il me semble qu'il est nécessaire de montrer au préalable que le résultat existe avant de développer une méthode de recherche de résultat : j'en connais (et j'en suis) qui ont perdu un temps fou à chercher une solution à un problème qui n'en admettait pas ...

On finira bien par trouver un accord :-)
idéalement je conteste "nécessaire de montrer au préalable" car j'essaie toujours d'évaluer ce qui sera le plus rapide : trouver une démonstration ou écrire le programme qui me dira (en temps d'exécution limité) si une solution existe ou non...

et je ne suis pas paresseux au point de toujours écrire un programme...
Par contre dans le cas des vases communicants, j'ai appris en programmant un tas de choses intéressantes sur les séquences minimales, dont je ne vois pas du tout comment en "démontrer" l'existence...

Cordialement

totomm · 27-08-2011 09:43:40

Bonjour,

@ freddy : Mon code pour "Combinaisons de 12 nombres : triplets" est dans le sous-forum "Programmation"

Cordialement

Forum de mathématiques - Bibm@th.net

#1 16-08-2011 17:58:48

Sujet pour totomn ! ...

#2 17-08-2011 14:21:48

Re : Sujet pour totomn ! ...

#3 17-08-2011 14:42:15

Re : Sujet pour totomn ! ...

#4 17-08-2011 15:24:31

Re : Sujet pour totomn ! ...

#5 17-08-2011 16:44:16

Re : Sujet pour totomn ! ...

#6 17-08-2011 17:26:35

Re : Sujet pour totomn ! ...

#7 17-08-2011 21:10:55

Re : Sujet pour totomn ! ...

#8 17-08-2011 22:08:48

Re : Sujet pour totomn ! ...

#9 18-08-2011 01:16:24

Re : Sujet pour totomn ! ...

#10 18-08-2011 10:30:41

Re : Sujet pour totomn ! ...

#11 18-08-2011 17:08:54

Re : Sujet pour totomn ! ...

#12 18-08-2011 20:32:16

Re : Sujet pour totomn ! ...

#13 19-08-2011 10:55:27

Re : Sujet pour totomn ! ...

#14 19-08-2011 11:07:46

Re : Sujet pour totomn ! ...

#15 19-08-2011 14:12:08

Re : Sujet pour totomn ! ...

#16 19-08-2011 14:30:46

Re : Sujet pour totomn ! ...

#17 19-08-2011 14:50:04

Re : Sujet pour totomn ! ...

#18 19-08-2011 16:25:49

Re : Sujet pour totomn ! ...

#19 25-08-2011 23:34:57

Re : Sujet pour totomn ! ...

#20 26-08-2011 08:05:31

Re : Sujet pour totomn ! ...

#21 26-08-2011 10:38:01

Re : Sujet pour totomn ! ...

#22 26-08-2011 17:26:45

Re : Sujet pour totomn ! ...

#23 26-08-2011 17:43:14

Re : Sujet pour totomn ! ...

#24 27-08-2011 09:43:40

Re : Sujet pour totomn ! ...

Réponse rapide

Pied de page des forums