|
| Voyage intellectuel (suite) par Pe***tr***a*1318 le
[Aller à la fin] |
| Problèmes | |
|
Questions faisant référence à la solution de l'hyper-jeudans Question naïve pour les solutionnistes par nicolasdupont
1) Bravo à postériori pour ce superbe paradoxe, il est parfait encelà que sa solution est très compréhensible et apte à convaincre (ça n'est pastoujours synonyme !), ou alors tu as réussi à la rendre comme telle ce quiest encore plus à ton mérite. Donc vulgarisation 100% réussie.
2) ...Très compréhensible quoiqu'un doute subsiste, l'ensemble des jeuxfinis n'existe pas en tant que tel ou n'existe pas dans le contexte de la définition de l'hyper-jeu ? 3) Est-ce qu'un choix portant sur un ensemble apparemment définimais en réalité pas, peut peut tjs déboucher sur un paradoxe (que l'ensemble soit indéfini en tant que tel ou de par la définitiondu paradoxe) 4) Est-ce que ta solution vulgarisée, bien que présentant le fil principal,ne laisse pas de côté des subtilités (fameuses subtilités qui sont souventpresque des clefs, euphémismes utilisés pour résumer en 2 lignesde très complexes solutions) ? Car enfin si plein de matheux ce sont entichésde ce jeu, ils ont bien du en tirer des litres et des litres ? PS : C'est un forum d'échecs n'oublions pas, un oui-non-oui-non me suffirait ;-))
|
|
|
reponse 1) Merci. 2) Les jeux finis ne forment pas un ensemble sinon plus rien ne cloche dans la definition de l'hyperjeu mais il est alors impossible de savoir s'il est ou non dans cet ensemble, ce qui ne respecte un des axiomes de la theorie des ensembles. 3) Possible mais pas clair pour moi. 4) Pas de subtilites cachees, il me semble, mais utilisation implicite d'une logique fabriquee par les HOMMES, donc que tout les matheux sont pas obliges de partager (ni quiconque d'autre d'ailleurs). Par exemple certains pensent qu'il n'est pas sain de vouloir a toute force des "logiques parfaites" (i.e. sans paradoxe possible), que cela peut etre considere comme un "viol de la nature", voir une "appropriation divine" et donc que l'hyperjeu reste et restera un "mystere" (dans le sens philosophique du mot). Voila un litre.
|
|
|
PS Les matheux passent pas leur temps a discuter de l'hyperjeu, mais des fois, a la fin d'un banquet de fin de congres, on s'amuse bien avec ce genre de trucs.Pendant que j'y pense, voila une autre recreation de fin de banquet amusante.Tu as 12 pieces dont une qui est fausse.Tu dois la trouver a coup sur avec une balance de Roberval en 3 pesees.
|
|
|
ça par contre... ...je connais ;-)
j'avais essayé d'étudier une variante avec 2 fausses boules mais g pasapprofondi
|
|
|
PS n°2 Même question avec 13 pièces + 1 correcte.
|
|
|
autre question liee J'ai cherche la fonction de n=nombre de pesees, qui donne le maximum de pieces ou on peut trier la fausse. J'ai trouve une formule assez jolie mais qui depend des resultats precedents (recurrence multiple) que je n'arrive pas a "synthetiser". Si quelqu'un connait...
|
|
|
Facile et évident (3^n)/2 si on a une bonne pièce.
|
|
|
Euh... Comme 3^n est impair, c'est en fait (3^n-1)/2. Donc :
pour n=1 : 1
pour n=2 : 4
pour n=3 : 13, etc...
Je précise que dans ce problème, on doit également dire si la pièce est plus lourde ou plus légère.
|
|
|
Facile et evident ? Peut-etre, mais j'aimerai connaitre la source de ton affirmation. Ma formule ne coincide plus avec la tienne a partir de n=5 ou tu trouves 364.
|
|
|
De plus en plus off topic ! Désolé, pas de source. J'ai trouvé ça tout seul comme un grand ! Je me suis toujours demandé pourquoi le problème était posé avec 12 pièces, alors que 3 pesées conduisent à 27 possibilités donc 1 pièce plus lourde où plus légère parmi 13.
(3^n-1)/2 est évidement un maximum : n pesées conduisent à 3^n résultats possibles. Un résultat est à éliminer : celui où la balance ne penche jamais. Sachant que la pièce peut-être plus lourde ou plus légère, on obtient (3^n-1)/2.
Il reste à trouver une répartition des pièces sur les plateaux qui fait que chaque pièce a un parcours différent. Par exemple avec la convention G=gauche, D=droite, X=hors de la balance :
pièce 1 : GGG
pièce 2 : GGX
pièce 3 : GDG etc... (j'ai fait au hasard, mais il y a une "bonne" méthode)
Il y a 27 possibilités mais une est à éliminer : XXX, et les possibilités sont appariées : si deux pièces différentes ont comme parcours GGX et DDX, on ne peut pas les discriminer.
Tout cela fait furieusement penser à la numérotation en base 3.
Avec la convention 0=gauche, 2=droite, 1=hors de la balance, on obtient que deux parcours sont appariés si leur somme fait 222 (en base 3) c'est à dire 26. Par exemple 102 et 120 (i.e. 11 et 15).
Il faut donc choisir 13 nombres parmi les nombres de 0 à 26 sans prendre le nombre 13 (i.e. 111) et sans que la somme de deux nombres fasse 26
Un autre problème est qu'il doit y avoir une répartion a peu près égale sur chaque plateau à chaque étape (à 1 près. C'est à ça que sert la pièce correcte). Une solution possible est 0-1-3-4-5-14-15-16-17-18-19-20-24.
Je te laisse trouver comment j'ai trouvé cette solution et comment généraliser à n pesées. J'avoue n'avoir pas regardé au delà de 4.
|
|
|
re : 1)2)3)4) (ce message si sub-divise, typiquement en l'occurrence cela va dans le sens de la représentationstructurée de yvap)
2) je ne comprends pas. Est-ce qu'un ensemble est indéfini à partirdu moment où on sait qu'on ne peut décider si un élément qui n'existe paslui appartient ou non ? A ce moment-là aucun ensemble ne l'est !!??3) je suis étonné qu'il n'y ait pas eu de 'systématisation' de la question...4) je ne suis pas sûr de saisir toute la portée de ta réponse mais je suisassez partisan de la défense du 'bordel ambiant', les maths doivent resterles maths et le langage doit rester dans une certaine mesure de l'à peu près.Sans à peu près on serait privés de merveilleuses disputes ou dechaleureuses mésententes ? ;-)
|
|
|
re : FPC re ton PS N°2 : je n'ai pas compris ton problème, 13 fausses pièces et 1 correcte ?ça veut dire koi ??
(3^n-1)/2 : pour n=1 ça ne marche déjà pas, coment dire si elle est +lourde ou + légère que les autres ? ;-))
+ sérieusement, j'essaye de regarder tes explications.
|
|
|
re : FPC pour n = 2 ça ne marche pas non plus, avec 4 boules on peut certes en 2 peséesrepérer la mauvais mais pas dire si elle est + lourde ou + légère que les autres !!
|
|
|
Précision On a une pièce fausse parmi 13, et on a en plus une pièce dont on sait qu'elle n'est pas fausse (soit 14 pièces en tout).
Si on n'a pas de pièce correct, le nombre est : (3^n-1)/2 -1 (une de moins) c'est à dire (3^n-3)/2, soit 0 - 12 - 39 - etc...
Ce qui me semble évident, c'est que le maximum est bien (3^n-1)/2, mais la solution qui permet d'obtenir le maximum n'est finalement pas si évidente que ça.
PS : On est loin du oui-non-non-oui demandé dans ton article original ;-).
|
|
|
Erratum Dans la deuxième phrase, lire : (3^n-3)/2, soit 0 - 3 - 12 - 39 - etc...
|
|
|
reps Peres 2) Tu mets pas les trucs dans le bon ordre. Si jeux finis=ensemble alorshyperjeu existe. Or on a vu que non.3) Peut-etre que ca existe. Je suis pas logicien.4) Moi aussi, mais si un jour quelqu'un trouve une "logique universelle", adieu veaux, vaches, cochons...FPC Tres interessant. OK pour le max, mais pas clair qu'il puisse toujours etre atteint (faut que je retrouve montravail la dessus pour n=5)
|
|
|
PS a FPC pour n=2, comment tu peux savoir si la fausse piece est + lourde ou + legere, dans le cas ou les 2 pesees sont equilibrees ?
|
|
|
reps à nicolas 2) tu me dis je mets les charrues avant les boeufs et moi je te dis la mêmechose, amusant non ? Parce que pour en revenir au bon vieux bon sens commun, "l'ensemble des jeux finis" n'importe quel quidam dansla rue t'assureras qu'il existe en ce sens que tu peux imaginer une grandebrouette dans laquelle tu entasses tous ces jeux (il n'y ambiguïté pour aucunjeu puisque l'hyper-jeu n'existe pas !). Parti de là tu définis un jeupour lequel il est impossible de décider de son appartenance ounon à cet ensemble, comme l'ensemble est défini, une telle indécisionne peut exister et donc la définition du jeu est incorrecte !!?
Enfin je vais y repenser à tête reposée.Ps à ton ps à fpc : cf ma remarque kelk lignes au-dessus ;-)
|
|
|
Détails pour n=2 Avec les notations de mon commentaire : on choisit les nombres 0, 5 , 6 et 7(i.e. 00, 12, 20, 21 en base 3). Il faut choisir les nombres de manière que la somme de deux d'entre eux soit différente de 8 (i.e. 22).
Soit A , B C et D les 4 pièces douteuses, X la pièce correcte.
Le parcours de :
A est : 00 soit gauche-gauche
B est : 12 soit hors-droite
C est : 20 soit droite-gauche
D est : 21 soit droite-hors
Il n'y a plus qu'à compléter avec la pièce correcte. Les 2 pesées sont donc :
pesée 1 : AX et CD
pesée 2 : AC et BX
On peut également coder le résultat des pesées de la même façon : 0=penche à gauche, 1=équilibre, 2=penche à droite.
Il y a 9 possibilités :
00 : A est plus lourde.
01 : D est plus légère. (01 est le "complémentaire" de 21).
02 : C est plus légère...
Si on obtient 11 (équilibre 2 fois), c'est qu'aucune pièce n'est fausse ! C'est le cas qui fait apparaitre le 1 dans la formule (3^n-1)/2. Relire le début de ma tentative de démonstration.
|
|
|
Pour être plus clair Si deux pièces (A et B) ont deux parcours "complémentaires" : par exemple gauche-gauche (00) et droite-droite (22), on ne peut pas distinguer le cas "A plus lourde" de "B plus légère". C'est pour cela qu'il faut que la somme de deux nombres soit différentes de 8.
J'avoue avoir du mal a être parfaitement clair, mais bon, écrire dans cette petite case, c'est vraiment ch...
|
|
|
Autre manière de voir : (suite des détails pour n=2)
Si A est plus lourde, le résultat des pesées est 00
Si A est plus légère, le résultat est 22 (complémentaire)
Si B est plus lourde, le résultat est 12
Si B est plus légère, le résultat est 10 (complémentaire)
...
Si aucune pièce n'est fausse, le résultat est 11. Il y a 9 résultats possibles qui correspondent à 4 pièces, soit plus lourdes, soit plus légères (x2) + 1 cas correspondant à aucune pièce fausse.
Le fait de devoir me faire comprendre m'aide à clarifier ma propre pensée !
|
|
|
rep a peres C'est justement ca qui fait la beaute du truc : le pekin moyen n'emmetra aucun doute sur l'existence de l'ensemble des jeux finis...mais pas le subtil logicien !! Autre exemple amusant : les constituants de l'univers ne forment pas un ensemble (les physiciens ne sont pas encore sur de l'existence "reelle" de certaines particules) mais il le sera peut-etre un jour !!
|
|
|
FPC : sans bonne pièce ? C'est vraiment intéressant ton truc et très convaincaint, mais de là à le demontrer...je ne vois pas trop à première vue comment aborder la démonstration du cas général !
Ce qui est très subjuguant c'est la transformation d'une réflexion en une systématisation,ou la main mise mathématique...Ceci dit j'ai une remarque.
En plus des restrictions horizontales(horizontale c.a.d. par boule, par opposition à une vision verticalepar pesée) qui interdit à une bouled'une part de n'être jamais pesée et d'autre part de ne pas suivreun traitement symétrique à celui d'une autre boule - en plus de cesrestrictions donc - et dans le cas où on ne dispose pas de la 'bonne boulesupplémentaire' il faudrait ajouter une règle qui interdit pour chaquepesée un nombre impair de boules, ou encore imposer qu'à chaque peséele nombre de X -le nombre de boules hors plateau - soit de la même paritéque le nombre total de boules.
|
|
|
Tu as tout compris En fait, la boule correcte n'est là que pour un problème de parité. Elle n'intervient pas de façon fondamentale dans la solution (voir les détails pour n=2).
Si on n'a pas de boule correcte, on ne peut tester que (3^n-1)/2 - 1 boules en n pesées. A chaque pesée, il doit y avoir 1/3 de boules à gauche, 1/3 de boules à droite, 1/3 de boules hors de la balance.
Hors justement, (3^n - 1)/2 - 1 = 3*(3^(n-1)-1)/2 est divisible par 3 ! (Il s'agit de la suite 0 - 3 - 12 - 39 déjà citée.
|
|
|
facile et évident (un client d'oeil à une évidence bien longue à accoucher ;-)) )
Ta formule ne fonctionne toujours pas pour n = 2.
Sinon je crois saisir ton truc, (je paraphrase) sans être capablede traduire numériquement la règle de parité de pesée (règle verticale),tu te convaincs que le maximum est qd même tjs atteignable de parla nature même du maximum qui permet tjs une pesée 'maximale' (3 tiers)
|
|
|
Problème pour n=2 ? C'est la troisième fois que vous me posez la question pour n=2, mais je ne vois pas le problème. On peut tester 3 pièces sans pièce correcte supplémentaire, 4 pièces si on a en plus une pièce correcte. J'ai même donné les détails des pesées. Qu'est-ce qui ne marche pas ?
Je ne me convainc de rien du tout : j'ai un procédé qui permet de choisir judicieusement la répartitions des pièces. Ce procédé exploite effectivement la répartition en tiers et est généralisable à n pesées.
Le droit à une pièce supplémentaire correct ne me semble pas exhorbitant : sinon, on ne peut pas trouver une pièce fausse et dire si elle est plus lourde ou plus légère parmi 1 ou 2 pièces !
|
|
|
La preuve est faite ! Theoreme : avec n pesees, on peut decouvrir une piece fausse parmis (3^n-1)/2.Merci FPC de m'avoir indique cette borne sup. La preuve est de difficulte "moyenne", en tout cas trop longue pour etre ecrite ici.
|
|
|
|
n=2 Mea culpa je fatigue, tu as raison ça marche. Je reviens demain soitconvaincu soit avec un contre exemple. Nicolas : en 2 mots (vraiment !) par curiosité peux-tu juste me dire quelsoutils ou mécanismes sont mis en oeuvre pour démontrer ça pour le cas 'n' ?
|
|
|
Petit curieux... Grosso modo, y faut couper en trois :1) le probleme originel.2) le meme probleme mais ou on dispose en plus de pieces OK (si le premiere pesee est equilibree)3) du probleme de trouver le max parmis des pieces dont on sait que une est fausse, et qui sont de plus "etiquetees" lourdes ou legeres (si la premiere pesee est desequilibree).J'avais deja une formule pour ca mais "recurrente". J'ai juste ameliore cette apres-midi, et prouve qu'elle est egale au sup propose par FPC.
|
|
|
PS Et les 2 envellopes ? Moins coriace que l'hyperjeu (ce truc est une invention du "malin") mais tres interessant quand meme.
|
|
|
fissa merci pour le grosso modo.
je n'oublie pas du tt les enveloppes loin de là mais pas trop de tempsen ce moment (l'informatique est une redoutable science de l'à peu près et d'une gourmandise en temps sans bornes), d'ailleurs l'hyperjeun'est pas encore tout à fait pour moi un sujet clos, j'y songe j'y songe
|
|
|
Qu'est-ce qu'il a de plus que moi ? Je m'échine à essayer d'expliquer la solution, et Nicolas Dupont arrive avec un argument d'autorité ("C'est juste parce que je l'ai démontré !") et tout le monde est d'accord. Bouhouhou, snif ;-).
Bon, à part ça, voici la répartition des pièces pour n pesées : Problème des pièces
Convaincus ?
|
|
|
Pleure pas, FPC ! Ce qui est amusant, c'est que nos preuves sont conceptuellement assez differentes. Si je trouve un peu de temps, je la publierai aussi. Mais le probleme est que je fais des maths avec l'application TEXture que tout le monde ne possede pas. Ou alors y faudrait ensuite la changer en post-script.
|
|
|
Salut, les gars! Juste un petit coucou pour que vous ne vous sentiez pas trop seuls tous les trois ;-)
Gériencompri.
|
|
|
petit bout g trouvé 30mn ce we pour me poser sur un coin avec un bout depapier.
g encore une autre approche, qui se rapproche de celle de FPC.Ce qui ne me convaincait pas entièrement c le fameux "choixjudicieux" pour que les deux côtés soient équilibrés. J'aurais aimétrouver une formule ki calcule pour n'importe quel n larépartition des boules.
Mon approche donc ne fait que systématiser le choix des parcourspossibles de boules et permet donc de remplir facilement des plateaux mêmepour n grand. Mais il reste encore le "judicieux" pour établir le droite-gauche.
|
|
|
Tu fais par recurrence et ca marche. La reponse, c'est que c'est la partie entiere du tiers des pieces qu'il faut mettre sur chaque plateau (exemples : partie entiere du tiers de 13=4 et partie entiere du tiers de 40=13)...On pourrai croire que s'il y a equilibre, on est roule car il reste 14 pieces en 3 pesees. Mais on dispose alors d'un stock de bonnes pieces, et ca marche...(je te laisse trouver comment, si pas deja fait).
|
|
|
voui voui en fait je suis arrivé à l'expression du (3^n...) à partir d'une sommed'arrangements (toutes les combinaisons d'absence et de présenceaux pesées) multipliés par une somme d'arrangements (ttes les combinaisonsde passage de droite à gauche ou non). g pas eu le courage de réduirel'expression mais ça doit donner le même truc (g vérifié pour kelk n).
En fait dans 3^n... , le 3 ne provient pas de [pesée { =, }] maisde [boule {absente, pesée du même côté que celui de la première pesée ou pesée du côté opposé}].Du coup en + ça donne une façon de placer les boules de manièrequasi directe (le 'quasi' est à cause du fameux droite-gauche) pour n'importe quel n.Je viens de comprendre ton histoire de récurrence, en suivant la mêmeapproche, soit lesn parcours de boules, alors si on rajoute une pesée à chaque parcourson peut faire en + un 'boule à droite', 'boule à gauche', 'boule absente'(donc *3), ce à quoi il faut ajouter le parcours ('droite' ou 'gauche') +'absent', 'absent', 'absent'.
On retrouve comme ça le 1*3+1 = 4, 4*3+1 = 13, 12*3+1 = 40 etc...et sans la boule en + : (0+1)*3 = 3, (3+1)*3 = 12, (12+1)*3 = 39 etc... je sais pas si je suis très clair mais je me comprends bien ! merci nicolas !
|
|
|
oups erratum (fichu html) il fallait lire :
[...]le 3 ne provient pas de la liste [résultat de pesée{égal, supérieur ou inférieur}] [...]
|
|
|
