Petites enigmes

On avait un joli topic avec des enigmes plus ou moins scientifiques avant le crash, alors je me permet de relancer.

On prend une pyramide de 15 cases (5 de haut, 5 de larges)


Il faut y placer les nombres de 1 a 15 sachant que le nombre dans la brique au dessus de 2 autres doit valoir la difference entre le plus grand et le plus petit des nombres du dessous.
J'espere que j'ai ete clair...

Quelle(s) est/sont la/les solution(s) ?
Une methode autre que par tatonnement ?

Trouvé en deux minutes :

A priori, s'il faut mettre des nombres entre 1 et 15, ça disqualifie 16 et 32. A priori toujours, le nombre de nombres correspondant au nombre de cases, il faut une bijection entre les nombres et les cases.

Yop! Je l'ai! Après un bon nombre de tentatives:




Le truc qui peut piéger, c'est qu'il faut pas croire que les plus petits chiffres se trouveront en haut. Une fois qu'on a trouvé la ligne du bas, le reste coule tout seul

Edit: Echo, je crois que t'a pas du bien piger le principe de l'énigme

Ce nouveau topic est accueilli avec plaisir... et permanentisé, comme l'ancien !

--
Mouton

Sylvius de Napline a écrit :

C'est bien ca, tous les nombres de 1 a 15 doivent se retrouver dans une case.


Jeff de l'Aurore a écrit :

C'est ca (le symetrique etant juste aussi)

La question etant maintenant, y a-t-il une methode pour trouver la solution?
J'ai eu beau la poser dans tous les sens, noter chaque element qu'on sait et ce qui en decoule, j'ai pas trouve une methode par deduction qui permet de remplir...
Pourtant, il doit bien y en avoir une.... j'espere.

Elune Morningwood a écrit :

> La question etant maintenant, y a-t-il une methode pour trouver la solution?

Une recherche exhaustive ?

Il y a 15*14*13*12*11 étages de base possibles, c'est instantané sur un ordinateur.

Arf... J'ai lu que la moitié de l'énoncé...
La grande spécialité de l'ensemble de ma vie.
Je me disais bien aussi que c'était trop facile.

Edit : Mouarf, je suis aveugle, j'ai encore mal lu.

mmmh trouver par logique, je pense pas, ou alors c'est un bon gros système de 15 équations à 15 inconnues... Mais flemme de vérifier

A mon tour de proposer une énigme je suppose? Bon j'en ai pas de super balèze qui me viennent en tête, j'en avais une, mais j'arrive pas à bien l'afficher donc c'est mort... si quelqu'un a, qu'il propose

Jeff de l'Aurore a écrit :
> mmmh trouver par logique, je pense pas, ou alors c'est un bon gros système de 15 équations
> à 15 inconnues... Mais flemme de vérifier


Ben en fait, par logique, j'ai des choses comme :

Le Monde des Mathématiques se lancent dans les énigmes !

Jennifer Lowraj a écrit :
> Le
> Monde des Mathématiques se lancent dans les énigmes !

J'espère ne pas me tromper :

Effectivement pour la deuxième (différence minimum)... j'ai un peu fait mon boulet, mais pour le premier je pense que tu te trompes.



Edit, je viens de voir que je suis un boulet, vu que c'est la même valeur mais une autre façon de l'écrire

Y fait peur le monsieur...

Bien vu Sancho pour la différence.

Sancho V Six-Troënes a écrit :

>

J'ai un peu de mal avec ton dernier calcul

Gamaté a écrit :
>

Deux cercles, de rayons respectifs racine carrée de 3 et 3 ont, en leurs points d'intersection, des tangentes perpendiculaires.
Quelle est l'aire de leur partie commune ?

Je propose cette année des énigmes plutôt simples à mes élèves. Je pense les mettre ici comme aide-mémoire et aussi pour voir si vous avez des suggestions. Ça risque d'être donné du jeudi au jeudi.

Première semaine : soit X = 2¹⁰ ⁰⁰⁰. Combien X a-t-il de chiffres écrit en décimal ? Quels sont les deux derniers ?

--
Mouton

Mouton a écrit :

Ta puissance est trop petite, c'est illisible. Tu peux pas mettre 2^quelque chose ?

Jennifer Lowraj a écrit :

Ta puissance est trop petite, c'est illisible. Tu peux pas mettre 2^quelque chose ?

Il a marqué 2^10 000 ( smartphone ? )

Mouton a écrit :
> Première semaine : soit X = 2¹⁰ ⁰⁰⁰. Combien X a-t-il de chiffres écrit
> en décimal ? Quels sont les deux derniers ?

Alors sauf erreur de ma part :



J'aime vraiment bien la première partie mais moins la deuxième.

Elune Morningwood[62§o]Jumper a écrit :

>



--
Mouton

Mouton a écrit :

Enigme de la semaine :

On place 1 point sur un cercle, le cercle n'est pas divisé, u1 = 1.
On place 2 points sur un cercle, on les relie, le cercle est divisé en deux, u2=2.
On place 3 points sur un cercle, on les relie tous entre eux, le cercle est divisé en quatre, u3=4.
On place 4 points sur un cercle, on les relie tous entre eux, le cercle est divisé en huit, u4=8.

Il faut faire attention à ne pas avoir trois segments concourants, sinon on perd une division. Par exemple, pour 6 points, il ne faut pas faire un hexagone régulier.

Que vaut u7, u8, u18 ? (et pour vous : donner une formule générale).

--
Mouton

Le disque est divisé ?

Sylvius de Napline a écrit :

> Le disque est divisé ?

Cas u2 :


Le disque est divisé en la partie au dessus de la ligne rouge et celle en dessous.

Et Mouton, c'est méchant celle là

Sylvius de Napline a écrit :

> Le disque est divisé ?

Oui. Je l'ai donné en dessinant les figures, et sans rien expliquer (j'ai juste mis des nombres dans les différentes zones) aux élèves.

--
Mouton

Tu as surtout écrit "le cercle est divisé"._

Sylvius de Napline a écrit :

> Tu as surtout écrit "le cercle est divisé"._

J'avais compris ta remarque. On est entre nous, je pense qu'avec l'exemple que je donne, l'énoncé est assez clair. Je n'ai pas fait d'erreur auprès de mes élèves, vu que je leur ai donné l'énoncé sous forme de figure.

--
Mouton

Celle de cette semaine m'a été soufflée par Mikumi :

On dispose de 4 "8", des quatre opérations, de la racine carée et des parenthèses. Il faut réussi à calculer autant d'entiers distincts entre 1 et 30.

Exemple : (8+8+8)/8 = 3. On est obligé d'utiliser tous les 8, on peut employer plusieurs fois la même opération.

--
Mouton

Déjà les 20-1 premiers (en espérant pas avoir fait de fautes en écrivant)

Elune Morningwood[62§o]Jumper a écrit :

Je n'autorise pas la concaténation comme opérateur de base

Cela dit, tes résultats sont astucieux.

--
Mouton

Mouton a écrit :
> Je n'autorise pas la concaténation comme opérateur de base

C'est pas de la concatenation, je les pose juste l'un a cote de l'autre. Apres si ca se lit comme si j'avais concatene, c'est un autre probleme

Sinon, on est cence pouvoir tous les faire parce que j'avoue que je bloque pour pas mal apres. J'ai l'impression de manquer un element mais je sais pas quoi.

Elune Morningwood[62§o]Jumper a écrit :

> C'est pas de la concatenation, je les pose juste l'un a cote de l'autre.

BA TU PEU PA !

> Sinon, on est cence pouvoir tous les faire parce que j'avoue que je bloque pour pas mal apres.
> J'ai l'impression de manquer un element mais je sais pas quoi.

Je pense que c'est impossible de tout faire. Je pense que je plancherai sur une démonstration algorithmique ce week-end.

--
Mouton

Donc version corrigee avec tout ce que j'ai et rajoute le peu que j'ai trouve dans la suite:

Elune Morningwood[62§o]Jumper a écrit :

J'ai le 11 en plus, mais je n'en vois pas d'autre (et j'ai la flemme d'écrire un programme pour tout tester).

Papi Crocell a écrit :

> J'ai le 11 en plus, mais je n'en vois pas d'autre (et j'ai la flemme d'écrire un programme
> pour tout tester).

Le programme est fait, mais il n'est pas exhaustif, parce que je n'ai pas supposé que les racines non-entières sont toujours inutiles. Je suis maintenant assez convaincu qu'elles le sont, pourtant, et donc je devrais réécrire ça en dynamique en remplissant définissant ai,j = vrai si on peut écrire i avec j huits.

Tiens, t'as pas des idées, pour les semaines à venir ? Je peux commencer à leur poser des problèmes NP-difficiles, mais bon.

--
Mouton

Mouton a écrit :
>les racines non-entières sont toujours inutiles

T'as bien vu que non, sinon comment je ferais 1 ?

Sinon oui c'est inutile car pour revenir a un entier, il faut faire une multiplication que tu aurais pu faire avant.

Elune Morningwood[62§o]Jumper a écrit :

> T'as bien vu que non, sinon comment je ferais 1 ?

Heu, comme ça ?


Ou alors j'ai pas compris le jeu.

Alivien Avimoa a écrit :

Ca m'avait tout l'air d'être une réplique... ironique en fait ;)

L'énigme de cette semaine est la suivante :
on dispose de 6 tasses (2 rouges, 2 pourpres, 2 écarlates) et 6 soucoupes (2 rouges, 2 pourpres, 2 écarlates). On dispose au hasard les soucoupes sur les tasses. Quelle est la probabilité que chaque tasse soit une soucoupe de couleur différente de la sienne ?

Je donne également la réponse à celle de la précédente :

# proc (8*8*8*8);;
0 = (8-8)
1 = (8/8)
2 = Sqrt(Sqrt((8+8)))
3 = Sqrt(((8/8)+8))
4 = Sqrt((8+8))
5 = ((8/8)+Sqrt((8+8)))
6 = (8-Sqrt(Sqrt((8+8))))
7 = (8-(8/8))
8 = 8
9 = ((8/8)+8)
10 = (Sqrt(Sqrt((8+8)))+8)
11 = (Sqrt(((8/8)+8))+8)
12 = (Sqrt((8+8))+8)
14 = ((8+8)-Sqrt(Sqrt((8+8))))
15 = ((8+8)-(8/8))
16 = (8+8)
17 = ((8/8)+(8+8))
18 = (Sqrt(Sqrt((8+8)))+(8+8))
20 = (Sqrt((8+8))+(8+8))
24 = (8+(8+8))
- : unit = ()

Le code Caml est normalement assez lisible et dispo ici. Il tourne assez vite.

--
Mouton, qui aime bien le rouge.

C'est bizarre que tu ne l'aies pas fait en récursif. C'est un cas de programmation dynamique ou la transformation en code itératif est un peu merdique. C'est vraiment plus rapide comme ça ?

Mouton a écrit :

# proc (8*8*8*8);;
0 = (8-8)
1 = (8/8)
2 = Sqrt(Sqrt((8+8)))
3 = Sqrt(((8/8)+8))
4 = Sqrt((8+8))
6 = (8-Sqrt(Sqrt((8+8))))
7 = (8-(8/8))
8 = 8
9 = ((8/8)+8)
10 = (Sqrt(Sqrt((8+8)))+8)
12 = (Sqrt((8+8))+8)
16 = (8+8)
24 = (8+(8+8))
- : unit = ()

Tu respectes pas tes règles :
Mouton a écrit :
> On est obligé d'utiliser tous les 8, on peut employer plusieurs fois la même opération.

D'ailleurs c'est ce qui m'avait fait le plus chier dans l'affaire cette règle.
Sinon, je vois que mentalement j'avais presque tout sauf le 11.

Elune Morningwood[62§o]Jumper a écrit :

> Tu respectes pas tes règles

Je m'attendais à cette remarque. 8 = sqrt(8*8), ce qui permet de rajouter des 8 sans problème, et donc je n'ai pas fait le rajout dans les arbres au moment de la présentation.

Sur le code, je l'ai pensé en itératif, donc je l'ai fait en itératif. J'avais fait du récursif très très maladroit (même dossier, autre fichier) avant, donc j'ai changé. Tu vois les choses comment en récursif ?

--
Mouton

En fait, ça rentre assez mal dans le schéma classique de la programmation dynamique. Il est plus simple d'énumérer les expressions comme tu le fais, tandis que si on appliquait bêtement le schéma classique, on essaierait de dire "je veux les solutions pour 4 huit, donc je vais d'abord chercher celles avec 1, 2 ou 3 huit".

Construire la liste des expressions est un processus récursif, je ne comprend pas bien comment tu es arrivé à en faire une boucle, qui te fera revenir plusieurs fois sur la même expression.

Une première version

Le tableau est assez creux, et itérer dessus est assez inefficace. C'est un argument supplémentaire en faveur de la récursivité. Mais au delà de ça, il reste des boucles dans le programme précédent, qui vont itérer sur beaucoup de vide. J'ai autorisé les valeurs à monter à 256 et il y a beaucoup de valeur inatteignables entre 1 et 256. Du coup, plutôt que d'itérer sur le tableau pour trouver des expressions déjà construites, je vais les stocker dans une liste et itérer la liste. En prime, ça simplifie un poil le programme.

Une seconde version

Sur ma machine, la première version termine en 4ms et la seconde en 2ms. On peut optimiser en utilisant ta remarque, (sqrt(8*8) = 8) ce qui réduirait le nombre d'expressions à stocker, mais requiert un chaînage un peu plus élaboré que les listes ocaml.

Mouton a écrit :

> L'énigme de cette semaine est la suivante :
> on dispose de 6 tasses (2 rouges, 2 pourpres, 2 écarlates) et 6 soucoupes (2 rouges, 2 pourpres,
> 2 écarlates). On dispose au hasard les soucoupes sur les tasses. Quelle est la probabilité
> que chaque tasse soit une soucoupe de couleur différente de la sienne ?

Elune Morningwood[62§o]Jumper a écrit :



Et pourtant tres difficile pour mes eleves, qui ne sont pas au point en probas. Du coup, ca fait une intro sympa.

--
Mouton

Mouton a écrit :
> Et pourtant tres difficile pour mes eleves, qui ne sont pas au point en probas. Du coup, ca
> fait une intro sympa.


A ce niveau la, j'aime bien la proba suivante :

Lors d'un jeu on a 3 portes identiques : 2 contiennent rien et 1 contient un prix.
Le joueur choisit la porte de son choix.
Le presentateur ouvre une mauvaise porte parmi les deux portes que le joueur n'a pas choisi. Puis il propose au joueur de changer de porte.
Apres avoir eventuellement change de porte, le joueur ouvre la porte et prend le prix.

Le joueur doit-il changer de porte? Est-ce que ca ne change rien a ses chances? Pourquoi?


Et en annexe, tes eleves, ils sont a quel niveau? Parce que t'as des enigmes complexes et des bien moins complexe.
Genre le coup de division de cercle, pour moi c'etait des personnes niveau fac assez avance alors que le coup des tasses, je vois ca plus niveau lycee.

Elune Morningwood[62§o]Jumper a écrit :

> Lors d'un jeu on a 3 portes identiques : 2 contiennent rien et 1 contient un prix.
> Le joueur choisit la porte de son choix.
> Le presentateur ouvre une mauvaise porte parmi les deux portes que le joueur n'a pas choisi.
> Puis il propose au joueur de changer de porte.
> Apres avoir eventuellement change de porte, le joueur ouvre la porte et prend le prix.
>
> Le joueur doit-il changer de porte? Est-ce que ca ne change rien a ses chances? Pourquoi?

C'est une énigme très connue effectivement. Dans mon cas, elle pose plusieurs problèmes :
- la réponse est du oui/non. Comme je demande peu de justifications, je choisis des énigmes pour lesquelles les élèves peuvent bidouiller un peu, et sortir quelque chose même sans avoir tout compris aux dessous du problème. Ici ce serait impossible.
- l'énoncé n'est pas toujours clair. Par exemple, tel que tu l'as écrit, il est impossible de dire s'il faut changer de porte ou si ça ne change rien (ça dépend de si le présentateur sait que la porte qu'il ouvre est mauvaise, ou s'il ouvre une porte au pif et constate qu'elle est mauvaise)
- il est facile de trouver la solution en ligne. Ou plus généralement, c'est un peu du "je sais / je sais pas". Il est très rare de trouver tout seul la réponse à cette énigme.

> Et en annexe, tes eleves, ils sont a quel niveau? Parce que t'as des enigmes complexes et des
> bien moins complexe.

Première année de prépa TSI. Ce sont des élèves qui ont fait des choses par le passé, mais moins que des élèves de S. Leur niveau est très hétérogène, à la fois en terme de calculs, de compréhension de concepts, ou d'imagination/initative face à des problèmes nouveaux. Par exemple, j'ai l'impression que le coup des cercles leur a posé moins de problème que le coup des tasses, mais ils ont peut-être eu de l'aide sur le cercle. C'était un problème un peu trop difficile par rapport à ce que je pense poser à l'avenir (ou alors pas trop souvent).

> Genre le coup de division de cercle, pour moi c'etait des personnes niveau fac assez avance
> alors que le coup des tasses, je vois ca plus niveau lycee.

La division de cercles se fait bien au niveau prépa, en fait. Je ne demandais pas de formule explicite, et seulement les termes U_6 et U_18. Je les ai recalculés avec leurs connaissances de calcul, en calculant une formule de récurrence à la calculatrice : Voir le corrigé. Pour les tasses, je pense que presque aucun élève ne sait calculer ça au niveau lycée. Déjà, dénombrer les permutations différentes (6!/(2!)^3) n'est pas évident. Compter celles qui collent est difficile aussi. Le calcul est moins technique, mais le raisonnement est moins développé dans ce domaine, chez eux. Ce n'est ici que ma perception des choses, hein. De toute façon, ce n'est pour moi pas un problème de varier la difficulté : ça intéresse des élèves différents. Par exemple, mes élèves costauds en maths n'ont pas cherché l'enigme avec les huit, et c'est très bien : d'autres élèves ont bidouillé et cherché leur liste (et ont oublié 11).

Un dernier truc : je suis content de tous les retours que j'ai de votre part concernant cet essai. Je ne sais pas bien si je continuerai toute l'année, mais pour le moment, je suis aussi content des réponses des élèves que j'ai reçues. Si j'ai du temps, je vous scannerai la réponse d'un élève pour l'énigme 2, il y avait des choses très intéressantes dedans.

--
Mouton

Mouton a écrit :
> Déjà, dénombrer les permutations différentes (6!/(2!)^3) n'est pas évident. Compter celles qui collent est difficile aussi.

C'est surtout que c'est pas comme ca qu'il faut partir pour un eleve de lycee.
L'eleve de lycee partira comme suit :


Je pense meme que c'est plus rapide que par les permutations (mais c'est plus du "je touche" que du "je calcule").


Sinon, je pense que pour les eleves c'est sympa d'avoir des enigmes comme ca qui permettent de faire tourner son cerveau.

Elune Morningwood[62§o]Jumper a écrit :

> Je pense meme que c'est plus rapide que par les permutations (mais c'est plus du "je touche"
> que du "je calcule").

Bon, j'ai passé un moment à réfléchir sur ce que tu disais. Ce « 1/90 » m'avait dit quelque chose, mais en fait, ce n'est pas la bonne réponse. Je pense que tu as mal lu l'énoncé, et calculé la proba que toutes les tasses soient sur une soucoupe de leur couleur.

Du coup, le problème est moins simple, et tu as du travail

--
Mouton

Mouton a écrit :
> Du coup, le problème est moins simple, et tu as du travail

Effectivement j'ai mal lu l'enonce...
J'ai calcule pour que tout corresponde par pour que tout soit different... m'apprendra a lire en diagonal et effectivement c'est plus complexe.

Elune Morningwood[62§o]Jumper a écrit :

Tu as la même solution que moi, avec la même méthode.

Et de manière amusante, la disjonction que tu fais est assez peu applicable si on essaye de généraliser. Est-ce que du coup tu penses que l'écart de difficulté est normalisé ?

Il faut que je cherche un problème pour la semaine prochaine. Sur des complexes ou de la géométrie dans le plan. Vous avez des idées ?

--
Mouton

Je suis extremement mauvais pour pondre des enigmes.

Avec du retard, forcément (mais je n'ai eu aucune proposition pour l'enigme précédente) :

On se donne un graphe complet à 6 sommets et deux joueurs. Chaque joueur à son tour colorie une arête de sa couleur (rouge ou verte). Un joueur gagne s'il a colorié un triangle.

Montrer qu'il y a forcément un vainqueur.

Pour aller plus loin : le jeu de la gaufre se joue sur un tableau n×m. Chaque joueur à son tour désigne une case valide, et supprime alors toutes les cases qui sont en haut et à gauche de cette case (autrement dit, si je désigne la case (i,j), je supprime toutes les cases (k,l) telles que k≥i et l≥j ; supprimer signifie "rendre invalide"). Le perdant est celui qui choisit la case (1,1). Discuter, suivant les valeurs de (n,m), de l'existence d'une stratégie gagnante pour le premier ou le deuxième joueur.

--
Mouton

Mouton a écrit :
> On se donne un graphe complet à 6 sommets et deux joueurs. Chaque joueur à son tour colorie
> une arête de sa couleur (rouge ou verte). Un joueur gagne s'il a colorié un triangle.
> Montrer qu'il y a forcément un vainqueur.



Pour le deuxieme:

Elune Morningwood[62§o]Jumper a écrit :

> Pour le deuxieme:

Il faut déjà montrer qu'un des joueurs a une stratégie gagnante (pas difficile si on a l'habitude de ce genre de raisonnements ou si on a le théorème adapté). Je te laisse chercher. J'avais fait cette démonstration à un de mes oraux d'agrégation, ça m'avait valu une plutôt bonne note.

--
Mouton

Peut-on suspendre un tableau à deux clous de telle sorte que si on enlève n'importe lequel des deux clous, le tableau tombe ?

Si oui, peut-on suspendre un tableau à trois clous de telle sorte que (...) ?
Si oui, jusqu'à combien de clous peut-on faire ça ?

(on supposera une ficelle infiniment longue, et le fait que le tableau tombe s'il n'est plus retenu par rien du tout).

--
Mouton

Mouton a écrit :

> (on supposera une ficelle infiniment longue, et le fait que le tableau tombe s'il n'est plus
> retenu par rien du tout).

Je ne suis pas sur de comprendre. Le tableau ne tombe jamais puisqu'il est systématiquement retenu par un clou au moins, du coup ?

Satori9960 a écrit :

> Je ne suis pas sur de comprendre.

Moi je suis sûr de ne pas comprendre.

La ficelle peut etre enroulee autour des clous de plein de manieres differentes.

Exemple : clic

Si tu retires le clou de gauche, le tableau tombe. Si tu retires celui de droite, le tableau ne tombe pas.

--
Mouton

Ca marche quelque soit n > 1 .

Mathématiquement, on commence par n=2 ça se prouve en étudiant le groupe fondamental (l'ensemble des classes d'homotopie des lacets du plan) du plan privé de deux points, qui n'est pas commutatif. Si a et b sont deux générateurs de ce groupe (correspondants chacun à faire un tour autour d'un clou, a autour du premier clou dans le sens indirect et b autour du deuxième clou dans le même sens, par exemple), a*b*a^(-1)*b^(-1) revient par exemple à relier faire passer la ficelle de gauche dans un sens autour du premier clou, dans le même sens autour du deuxième, puis dans le sens contraire autour du premier clou puis dans le sens contraire autour du deuxième clou. En fait, cette formule est directement reliée au chemin à faire faire à la ficelle qui tient les tableaux.

Retirer un clou revient à prendre pour a ou b l'élément neutre e du groupe. Si on retire un des clous (a=e ou b=e), on a bien a*b*a^(-1)*b^(-1) qui vaut e, donc le tableau tombe.

Pour généraliser à n noeuds, on le fait par récurrence.

Si F est une formule (la même que a*b*a^(-1)*b^(-1)) qui correspond au chemin à faire avec la corde pour n clous, et si p est le générateur du plan privé de (n+1) points associé au clou que l'on a rajouté, il faut faire à la corde le chemin G = F*p*F^(-1)*p^(-1). Et dans ce cas, si on retire un clou : soit c'est un clou apparaissant dans la formule F, donc par récurrence, on a bien F=e et donc G=e, si c'est p, on a aussi G=e.

C'est vraiment pas clair, mais ça ressemble en rien à ce que j'ai déjà étudié en maths, donc j'espère que c'est compréhensible. Si tu peux l'expliquer plus clairement/rigoureusement Mouton, ça serait avec plaisir !

Karmina Duxion[62§o]Old$chool a écrit :

Dans le cas de deux ou trois clous, tu as la possibilité de juste faire un dessin, pour visualiser

Sinon, je n'ai pas beaucoup plus clair pour les niveaux suivants, et je trouve ça assez chouette d'avoir trouvé ça seul-e.

--
Mouton

edit: Je croyais que la récurrence ne marchait pas à partir de 1. Mais elle marche très bien. Et puis Karmina Duxion ça fait presque "induction", alors c'est merveilleux.

Effectivement, ça marche dès n=1, où la solution est triviale (mais si vous arrivez à accrocher la corde de telle sorte que si on retire le clou, le tableau tienne en suspend , je suis preneur).

Facile, on met le tableau par terre. Tu peux oter 500 clous, il tombera pas

L'énigme de cette semaine est une fausse démonstration qui montre que tout triangle est isocèle en n'importe lequel de ses sommets. Je n'ai rien donné de plus comme indication.

La démonstration se base sur une figure fausse (une bissectrice et la médiatrice du côté opposé qui se croisent au centre du triangle), et n'est donc pas reproductible tellement ici.

--
Mouton

Mince, moi qui attendait une énigme pour réfléchir .

Si tu veux réfléchir, en voici une que je ne poserai pas à mes élèves.

n garçons et n filles veulent avoir des rapports sexuels chacun avec chacune (hétérosexuels uniquement). Seulement, chacun a une MST très rare et très contagieuse. Tu peux choisir l'ordre dans lequel les rapports ont lieu, mais personne ne doit se faire contaminer par une maladie qu'il n'a pas déjà.

Heureusement, ils ont des préservatifs qu'on peut empiler (ainsi, si un garçon a un rapport avec une fille et deux préservatifs neufs, l'intérieur du premier préservatif est contaminé par le garçon, l'extérieur du deuxième par la fille, mais les autres faces sont "réutilisables").


Question préliminaire : montrer que n² préservatifs suffisent.
Question préliminaire (oui, ça prend tout son sens ici) : montrer que 2n préservatifs suffisent.
Vraie question : De combien de préservatifs a-t-on besoin au maximum ?

--
Mouton

Il y a n MST différentes maximum ? Est-ce qu'on sait qui a quelle MST ?

Karmina Duxion[62§o]Old$chool a écrit :

> Il y a n MST différentes maximum ? Est-ce qu'on sait qui a quelle MST ?

Il y en a 2n. L'idée c'est qu'aucun rapport ne peut être non-protégé.

--
Mouton

Mouton a écrit :

Karmina Duxion[62§o]Old$chool a écrit :

> A chaque mec son préservatif. Chaque fille couche avec un mec différent. Notons IJ le
> préservatif qui a été utilisé par l'homme I et la fille J. J=f(I) est une bijection de [1,n]
> Si l'homme A veut coucher avec la fille B, il met le préservatif Af(A) puis par-dessus le préservatif
> (f^(-1)(B))B. (Ce qui donne en gros un préservatif global AB).

Le préservatif f^(-1)(B)B peut avoir été en contact avec l'homme f^-1(B) avant. De ce fait, il contamine l'extérieur de Af(A), qui ne sera plus utilisable ensuite.

Note que tous les rapports doivent avoir lieu. Essaye par exemple d'appliquer ça avec 2 garçons et 2 filles ? 3 garçons et 3 filles ?

--
Mouton

Cette semaine :
Combien de 0 à la fin de 10000! ?

--
Mouton

Mouton a écrit :

> Cette semaine :
> Combien de 0 à la fin de 10000! ?

Elune Morningwood[62§o]Jumper a écrit :

30! = 265252859812191058636308480000000

--
Mouton

Ouais j'ai fait mon boulet

Ca me rappelle un Project Euler il me semble .

Mes élèves ont trouvé aussi (mais sans trop comprendre, si j'ai bien vu)

Leur calculatrice allait jusqu'à 400!, donc ils ont fait des essais, ce qui est cool, et ont cherché une formule.

--
Mouton

Mouton a écrit :

> Mes élèves ont trouvé aussi (mais sans trop comprendre, si j'ai bien vu)

Alors que pourtant c'est assez bas comme niveau mathématique (même moi j'ai trouvé la réponse :P c'est dire)
ça demande juste de savoir ce qu'est une factorielle et être capable de comprendre comment t'obtiens un 0 pourtant.

Il faudrait être aussi capable de comprendre ce résultat. Ici, ça veut dire, comprendre ce qu'il faut prouver. Ça ne se fait dans le secondaire que dans l'option spécialité mathématiques de la terminale S.

Énigme classique, paradoxe des anniversaires :

À partir de quelle valeur de n une classe de n élèves a-t-elle plus de 75% de chances d'avoir deux élèves nés le même jour ?

--
Mouton

Mouton a écrit :

J'ai eu un prof qui pariait un bière qu'il y avait deux étudiants nés le même jours dans la classe. Enfin, il le faisait quand il y avait plus de 20 étudiants dans sa classe (c'est à dire pas sur les deux années où je l'ai eu, la physique n'attire pas/plus).

Karmina Duxion[62§o]Old$chool a écrit :

Pareil.

Sauf erreur de ma part, la formule c'est :

Karmina Duxion[62§o]Old$chool a écrit :

Ha oui.
Pour le coup, je ne sais pas comment je me suis débrouillé pour trouver un mauvais résultat en appliquant la bonne formule (sans doute une erreur d'étourderie)

Petite énigme sortie d'un rally mathématique que j'ai fait avec des élèves de seconde : (Je l'ai fait en latex et j'ai la flemme d'enlever les sauts de ligne )

Les faits:

Dans une maternité, 5 Bébé ont perdu leurs bracelet d'identification dans 5 chambres voisines.

1. Il y a cinq Bébé dont les yeux sont de couleurs différentes.
2. Chaque Bébé a une mère de nationalité différente.\
3. Chacune des mères a un animal préféré & un âge différent.\
4. Chaque Bébé a un prénom différent.\

Les questions sont :

Qui possède le un mouton? \
Quelle nationalité a la mère de 25 ans?\
De quelle nationalité et quel âge a la mère de Sae?\
Quel nom a donné à sa progéniture la propriétaire du renard?\


Quelques indices:\
1 L'Allemande a un enfant aux yeux noirs.\
2 La Française adore ses aigles.\
3 L'Américaine a nommer sa fille Abygaelle.\
4 La mère de l'enfant aux yeux vairon a 22 ans.\
5 L'enfant aux yeux marron est dans la chambre immédiatement à Droite de celle où se trouve l'enfant aux yeux Vairon.\
6 La mère de Sae possède un Tigre. \
7 Kenny a les yeux Verts.\
8 L'enfant de la mère Russe est dans la première chambre à Gauche.\
9 La mère d'un Bébé voisin de Rosie possède un renard.\
10 Kenny est le voisin d'un propriétaire d'écureuil.\
11 Le Bébé de la chambre du milieu a une mère de 35 ans.\
12 La mère Japonaise a 29 ans.\
13 La mère de Charles-Edouard a 17 ans.\
14 Le Bébé de la mère Russe est voisin du Bébé aux yeux bleus.\

Kitsune Wolfie a écrit :

En gros, c'est l'énigme d'Einstein, mais les maisons bleues, c'était moins à la mode que les bébés et les moutons ?

C'est une version de l'énigme d'Einstein, mais mes élèves étant à 97% des filles, fallait bien transposer ça...

En V5 on avait celle de KI comme version de l'énigme!

En Latex, il y a l'environnement enumerate, et il est possible de copier/coller à partir du pdf pour récupérer le texte sans le formatage.

Kitsune Wolfie a écrit :

> C'est une version de l'énigme d'Einstein, mais mes élèves étant à 97% des filles, fallait bien
> transposer ça...

Tu peux présenter des personnages féminins dans des postures un peu moins aliénantes que "juste mères", hein.

--
Mouton

Énigme de Noël :

Un renard (de Noël) se cache parmi 5 trous alignés : O O O O O

Chaque nuit, il change (obligatoirement) de trou, pour se décaler vers la gauche ou vers la droite (s'il est au bord, il en part nécessairement). Chaque jour, on peut fouiller un trou de son choix.

1/ Que dit le renard ?
2/ Peut-on choper le renard à coup sûr et si oui, en combien de jours minimum ?



Bonnes fêtes à tous.

--
Mouton

Karmina Duxion[62§o]Old$chool a écrit :





---

Effectivement, j'ai posté trop vite . Là ça doit être bon.



Edith m'a dit que c'était la même réponse que la tienne.

Karmina Duxion[62§o]Old$chool a écrit :
> Edith m'a dit que c'était la même réponse que la tienne.

Oui, sauf que moi j'y suis allé avec de longues phrases pas forcément très précises

Mais t'avais un raisonnement plus fin. Moi c'était bourrin .

Le renard dit "RINGEDINGEDINGEDING"

Joyeux Noël à tous !

--
Mouton

Petite enigme de ma part :

Faire en sorte que cette phrase soit vrai en remplacant les _ par des chiffres :

"Dans cette phrase, il y a _ fois 0, _ fois 1, _ fois 2, _ fois 3, _ fois 4, _ fois 5, _ fois 6, _ fois 7, _ fois 8 et _ fois 9."

Elune Morningwood[62§o]Jumper a écrit :

Tombant dessus par hasard :



Si on considère dix comme dix et non comme 1 et 0.

Non ?

Edit : après relecture, si on remplace par des chiffres, on doit seulement mettre un nombre allant de 0 à 9 donc ???

Archangel a écrit :
> Edit : après relecture, si on remplace par des chiffres, on doit seulement mettre un nombre
> allant de 0 à 9 donc ???

Oui normalement c'est uniquement des chiffres, meme si avec des nombres, on peut trouver des solutions (pour ma part en considerant que 10 = 1 fois 1 et 1 fois 0)

Et c'est ca Trixie Jutland.

L'énigme en ce moment n'est pas marrante : il s'agit juste de trouver la matrice de la dérivation polynomiale. (on vient de voir vaguement ce que sont les systèmes linéaires, et les liens ne sont pas tous faits). (je le poste quand meme parce que ce topic me sert de cahier de texte ).

--
Mouton

Un barman aveugle dispose de 4 verres disposés devant lui en carré sur un plateau. Certains verres sont à l'endroit, d'autres à l'envers, et son objectif est de les mettre à l'endroit. Comme il a des gants de boxe, il ne peut pas sentir si les verres sont à l'endroit ou à l'envers, mais il peut les retourner sans problème. Il ne peut pas savoir lui-même quand les verres sont à l'endroit, donc il a besoin d'un adjoint qui lui dit quand les verres sont à l'endroit. L'adjoint n'est vraiment pas aidant : cela se passe de la manière suivante :
- le barman retourne un ou plusieurs verres devant lui (ceux qu'il veut, comme il veut).
- il demande à son adjoint si les verres sont tous à l'endroit (si oui, il a gagné, sinon, il sait juste qu'il y a au moins un verre à l'envers).
- l'adjoint, facétieux, tourne alors le plateau devant le barman, autant qu'il veut, et on recommence.

Le barman a-t-il une stratégie gagnante ? En combien de coups maximum ?

--
Mouton

Mouton a écrit :

Le barman a-t-il une stratégie gagnante ? En combien de coups maximum ?

Honnêtement j'en doute, l'adjoint pouvant adapter ses rotations à toute stratégie qu'il détectera (je comprends que le barman ne connait pas l'angle de rotation du plateau).

Karmina Duxion[62§o]Old$chool a écrit :

Ta solution est fausse, pour des raisons assez triviales (je n'ai pas besoin de voir l'automate).

Plutôt que de donner la solution, je propose un indice : on peut décider, après chaque coup, de jouer deux fois "je retourne les 4 verres". Ça permet de gagner si on arrive à "4 verres à l'endroit" ou si on arrive à "4 verres à l'envers" (plutot que seulement "4 verres à l'endroit").

--
Mouton

Mouton a écrit :

Je n'avais pas précisé ton indice même si je fonctionne déjà comme cela (on gagne avec les 4 verres retournés ou dans le bon sens), mais je ne vois pas où je peux avoir faux. Bien sûr en effectuant une opération on ne sait pas dans quel état on va tomber, mais il n'empêche que mon enchaînement mène à coup sûr en 7 coups maximums (sans compter les "je retourne tous les verres") vers un état où les 4 verres sont dans le même sens.

Karmina Duxion[62§o]Old$chool a écrit :

Ce n'est pas possible non plus

Indice : est-ce que ta stratégie marche si tous les verres sont dans le même sens dès le départ ?

--
Mouton

Mouton a écrit :

Indice : est-ce que ta stratégie marche si tous les verres sont dans le même sens dès le départ ?

Après ton indice précédent, toute stratégie devrait commencer par vérifier ça en retournant tous les verres deux fois.

A priori j'ai la meme reponse que Satori avec une verification au debut qu'on est pas deja dans la bonne position inversee.

Apres, je me demande ce que ca pourrait donner si on interdit de retourner les 4 d'un coup. Je sais pas si il est possible de gagner a coup sur dans ce cas.

Elune Morningwood[62§o]Jumper a écrit :

Ce qui fait que tu arrives à 16 demandes de vérifications. C'est sain, parce que c'est le nombre de configurations possibles quand tu as les verres en face de toi au départ (et les transformations que tu fais sont toujours bijectives, donc quelle que soit la transformation que tu fais en 15 étapes, il y a une configuration qui fait que tu n'es jamais passé par la case "tous les verres à l'endroit").

> Apres, je me demande ce que ca pourrait donner si on interdit de retourner les 4 d'un coup.
> Je sais pas si il est possible de gagner a coup sur dans ce cas.

Aucune idée. C'est une question intéressante, je pense que ça devient impossible.

--
Mouton

Coucou les Mind Gamers !

Je vous propose une variante 'très large' des jeux de Nim, que j'ai inventée il y a 40 ans, et avec lequel on a fait des parties acharnées entre vieux cons à l'apéro sur le comptoir (visiblement çà permet de le prolonger, vous pourrez en voir des traces vivantes sur moi en RIK ).

L'ensemble est © Gérard Lochon 1974 - 2014 ; variante également © Gérard Lochon 1981 - 2014 : extension infinie du tableau et des règles à l'hexagone, et aux tableaux de dimension supérieures à 2.

Au lieu d'avoir les dispositions classiques genre jeu de Marienbad 1-3-5-7 alumettes, voici la disposition et les règles :

Le tableau de jeu est un damier de n*m cases, contenant chacune un jeton (à l'époque, j'avais choisi n=m=5 pour que le jeu ne dure pas trop longtemps).

Donc commencez avec un 5 x 5 pour voir

But du jeu : Jeu à 2, chacun son tour ; comme dans la plupart des jeux de Nim, on définit le gagnant comme celui qui n'a pas pris le dernier jeton.

Tour de jeu : chaque joueur a, à son tour, le choix entre la prise et le déplacement. Quand il ne plus faire autre chose que la prise du dernier jeton, ni n'a été déclaré "bredin", il est réputé perdant.
S'il est Bredin, la partie est nulle.

La PRISE : il s'agit de retirer un ou plusieurs jetons CONSÉCUTIVEMENT placés sur une ligne ou une colonne du tableau de jeu.

Attention : une ligne ou une colonne coupée en deux ou en plusieurs compte comme des segments de lignes ou colonnes multiples !
Par exemple si votre adversaire à pris, au premier tour, le jeton se situant au milieu de la ligne du haut, cette ligne est désormais coupée en deux, et vous ne pouvez plus, quand c'est votre tour, la retirer en totalité !

Le DEPLACEMENT : il s'agit de bouger, verticalement ou horizontalement, UN jeton, libre au moins du mouvement d'une case dans une des deux directions horizontale ou verticale, d'un nombre de cases compris entre 1 et le nombre de places disponibles dans la ligne ou la colonne choisie pour le sens de déplacement.

REGLE : on ne peut, à son tour de jouer, utiliser le déplacement si on l'a déjà utilisé personnellement le tour d'avant. (c'est ce qui permet de converger vers un temps fini du nombre de coups de la partie)

Le BREDIN : ce qui veut dire le 'simplet', dans le patois auvergnat. Il s'agit du joueur qui, à la suite soit d'une prise soit d'un déplacement provoque une situation où l'autre joueur ne peut plus que reproduire une exacte situation des jetons sur le damier déjà précédemment constatée.

Bon amusement, trouvez-moi des stratégies et des tactiques que je ne connais pas ...

P est un polynôme unitaire de degré 9 tel que P(1) = 1, P(2) = 4, P(3) = 9, ... P(9) = 81. Que vaut P(10) ?

--
Mouton

100 ?
Je ne sais pas ce que veut dire "polynôme unitaire de degré 9" mais bon ...

Naiaphykit a écrit :

> 100 ?

Ce serait trop simple

> Je ne sais pas ce que veut dire "polynôme unitaire de degré 9" mais bon ...

Ça veut dire que la fonction P que tu cherches est de la forme P(X) = X^9 + a X^8 + b X^7 + c X^6 + d X^5 + e X^4 + f X^3 + g X^2 + h X + i

où a,b,c,d,e,f,g,h, et i sont des constantes réelles.

(degré 9 signifie que le premier terme est X^9, et unitaire signifie que le coefficient devant X^9 est forcément 1).

--
Mouton

Sauf erreur de ma part :



Ca se fait assez bien sous excel

Edit :

Elune Morningwood[62§o]Jumper a écrit :

J'aurais dû préciser : j'ai posé la question à mon petit frère un jour. Il m'a donné la réponse 10 minutes plus tard, et on était dans la rue.

Il n'y a besoin de rien pour exprimer la réponse, et l'explication tient en un bel argument mathématique. C'est ça que je recherche.

--
Mouton

C'est pas drole de donner juste la reponse :

Elune Morningwood[62§o]Jumper a écrit :

Dans une copie, j'écrirais OUCH !

--
Mouton

On prend une grille de n×m carrés, chacun coloriés en noir et blanc.

On dit qu'on a trouvé un "rectangle" si on trouve 4 carrés disposés en rectangle (avec possiblement de l'espace entre eux) coloriés avec la même couleur.

On donne une grille sans rectangle. Que peuvent valoir m et n ?

Des indications, que vous ne regarderez pas, bande de tricheurs !



--
Mouton

Mouton a écrit :

Elle etait pas deja passe celle la (peut-etre avant la v6) ?

Elune Morningwood[62§o]Jumper a écrit :

> Elle etait pas deja passe celle la (peut-etre avant la v6) ?

Si si, sans doute. Mais elle a sa place sur ce topic de toute façon alors…

Au-dessus :

On peut démontrer des choses un peu mieux, dans le même esprit que ta preuve 3×9.

--
Mouton

Milvian a écrit :



--
Mouton

Mouton a écrit :

Karmina Duxion[62§o]Old$chool a écrit :

Précisément

--
Mouton

Le jeu de Set se joue avec 81 cartes.

Chaque carte comporte 1, 2 ou 3 symboles qui sont des losanges, des rectangles ou des cercles. Ils sont rouges, bleus ou verts, et sont remplis, hachurés ou vides (il y a une carte de chaque combinaison.

Un "set" est un ensemble de trois cartes telles que pour toute caractéristique (nombre, type, couleur, remplissage), les trois cartes prennent soit trois valeurs identiques, soit trois valeurs différentes.

Par exemple :
3 losanges rouges hachurés
2 rectangles verts hachurés
1 cercle bleu hachuré
est un set.

En revanche :
2 losanges verts hachurés
3 rectangles verts rempli
1 cercle vert hachuré
n'en est pas un (le remplissage pose problème).

Si vous voulez vous entrainer, il y a un challenge où il faut trouver des sets ici.

L'énigme de la semaine est de déterminer le nombre maximum de cartes qu'on peut aligner qui ne comporte pas de set.

--
Mouton

C'est marrant, j'avais un projet d'info au dernier trimestre qui était de coder cet exact jeu sur Androïd en version solo et multijoueur.

Pour l'énigme :

Mouton a écrit :

> L'énigme de la semaine est de déterminer le nombre maximum de cartes qu'on peut aligner qui ne comporte pas de set.

J'arrive à construire un ensemble de 16 cartes, mais je pense qu'on doit pouvoir monter plus haut.

Indice :

Karmina Duxion[62§o]Old$chool a écrit :

>

Peux-tu le prouver ? (ou au moins donner un exemple)

On dispose d'une barre de fer infiniment fine d'un mètre, et de 26 fourmis ponctelles (une espèce injustement déconsidérée par les biologistes). On peut les placer comme on veut au départ (position et sens), et elles avancent d'un mètre par heure. Quand deux fourmis se rencontrent, elles font demi-tour (elles bumpent, quoi). Comment placer les fourmis pour qu'il reste des fourmis sur la barre le plus longtemps possible ?

--
Mouton

Oui j'ai exhibé un exemple mais ça va pas être pratique à afficher. Je vais donner les nombres en base 3 correspondant au carte. De gauche à droite : la couleur des formes, le nombre de formes, la forme, le remplissage.

Karmina Duxion[62§o]Old$chool a écrit :

Cadeau

C'est plus joli comme ça oui .

Pour les fourmis,

Karmina Duxion[62§o]Old$chool a écrit :

Du coup, j'enchaine, je n'ai rien de très difficile en ce moment :

Un malade doit prendre deux comprimés chaque jour : un comprimé A et un B. Les tubes sont convenablement étiquetés, mais les comprimés eux-même sont indiscernables. Les médicaments coûtent un bras (on ne peut pas se permettre d'en perdre), on doit en prendre exactement un par jour (plus serait dangereux).

Comme tous les jours, le malade ouvre le tube A, fait tomber un comprimé, puis ouvre le tube B et verse, mais deux comprimés tombent. Il a donc dans la main un comprimé A et deux comprimés B, indiscernables. Que feriez-vous à sa place ?

Edit : pardon, balise spoiler, désolé

Tirodem Von Ninja [61§c] a écrit :

Bravo !

édit: Méthode donc un plus bourrin qu'au dessus..

Humbert Humbert a écrit :

> édit: Méthode donc un plus bourrin qu'au dessus..

Sauf que tu peux avoir plus d'un avec ta méthode (tu ne peux pas vérifier l'homogénéité de ton mélange...)

Ouais enfin à ce niveau là, on peut facilement dire que tu peux pas vérifier que tu as bien une moitié exactement quand tu coupes en deux.

Elune Morningwood[62§o]Jumper a écrit :

Sauf que ça reste assez précis pour savoir que t'es proche de 1, alors que t'as aucune possibilité de t'assurer l'homogénéité dans le 2ème cas, et où t'as autant de chance d'avoir 2B et 0A que d'en avoir 1/1.

D'ailleurs c'est p'tet pas pour rien que la plupart des médocs sont la petite fente pour les rendre sécables

> Elune Morningwood[62§o]Jumper a écrit :
Sauf que ça reste assez précis pour savoir que t'es proche de 1, alors que t'as aucune possibilité de t'assurer l'homogénéité dans le 2ème cas, et où t'as autant de chance d'avoir 2B et 0A que d'en avoir 1/1.


Si tu broie finement ta poudre dans un mortier, statistiquement je vois pas comment tu a "autant de chance d'avoir 2B et 0A que d'en avoir 1/1" en prélevant la moitié du milieux.

C'est comme si tu avais 1 million de billes rouge et noir. Si tu mélange le tout et que tu sépares en deux, tu tends immanquablement vers une répartition 50/50 ?

Ou alors j'ai vraiment rien compris au statistique

Humbert Humbert a écrit :

Alors en fait ma reaction est plus base sur le fonctionnement de creation de la pillule.

En effet, pour faire une pillule, tu prends de la poudre du composant actif et tu y ajoutes un excipient. Tu melanges le tout et avec le resultat, tu formes tes pillules.
Resultat, tu as une mauvaise precision sur la teuneur exacte d'une demi pillule.

Humbert Humbert a écrit :

> Ou alors j'ai vraiment rien compris au statistique

Si tu broyais un milliard de pilules un milliard de fois, majoritairement, t'aurais 50/50. Sinon, bah, non. Et plus précisément, c'est 200 billes noires/rouge sur ton milliard, t'as combien de chances d'avoir 100 billes noires/rouge si tu prends un demi milliard ?

Elune Morningwood[62§o]Jumper a écrit :

Si le comprimé est sécable, t'as 50% de chaque coté (j'ai envie de dire : si c'est pas le cas, les mecs ont mal fait leur boulot). Et si on part sur cette objection, broyer un médicament t'as beaucoup de chance de perdre le principe actif (c'est absolument déconseillé de faire ça). De même, si un comprimé n'est pas sécable, il ne faut pas le couper.

Mouton, pourquoi es-tu parti, comment survivre sans tes énigmes !

Sorti du cahier sciences du Monde d'il y a quelques semaines.

Dans un triangle non plat, il existe une relation entre la longueur d'une médiane et les longueurs des trois côtés du triangle. Celle-ci aurait été découverte en premier par Apollonios de Perga.

Pour ce qui nous concerne, on va de plus supposer que deux médianes de notre triangle sont perpendiculaires. Dans ce cas de figure, existe-t-il une relation entre les longueurs des trois médianes ? Peut-on énoncer un résultat dans l'esprit de Pythagore ?

(Hint : J'ai trouvé la relation en question, mais ma démo me semble lourde. Je suis curieux de voir d'autres raisonnements).

Irhoenqai a écrit :



Facile, peut-etre un peu long pour si peu, mais assez detaille.

On se situe dans un anneau de N salles dont chacune contient un interrupteur qui contrôle une ampoule. Au départ, les interrupteurs des pièces sont sur une position inconnue. Déterminer un algorithme qui permet de trouver la valeur de N.

Trois droites parallèles.

Placer un point sur chaque à la règle et au compas qui forment un triangle équilatéral.

Indice :

On se donne un polynome de degré quelconque à coefficients entiers positifs. On ne connait pas ces coefficients, mais on peut demande P(a) pour n'importe quelle valeur de a, entier.

Peut-on retrouver les coefficients du polynome en demandant un nombre fini de valeurs ? En demandant un nombre borné de valeurs ? En combien de valeurs au minimum ?

Je pense que deux valeurs suffisent.

Soit le jeu suivant : on se donne un rectangle de n×m cases. Chaque joueur à tour de rôle désigne une case et on supprime les cases qui sont au-dessus et à gauche de cette case.

Le joueur qui prend le dernier carré a perdu.

Montrer que le premier joueur a une stratégie gagnante s'il y a plus d'une seule case.

Guest a écrit :

> Trois droites parallèles.


j'ai pas essayé, si j'ai tout faux... n'hésitez pas...

Bugs Bunny a écrit :

C'est la bonne demarche ! On peut faire un peu plus simple sans doute.

As-tu teste sur geogebra pour voir si ca marche ?

Guest a écrit :

> As-tu teste sur geogebra pour voir si ca marche ?

Je ne connaissais pas ce site. Bref, c'est vérifié et ça marche.

On se donne une grille nxn, sur laquelle on peut disposer n-1 virus. Une case se fait contaminer si deux cases adjacentes (sur 4 au maximum) sont contaminees. Montrer que la grille complete ne sera pas contaminee.

De façon intuitive je dirais que tu ne peux contaminer que (n-1)² cases.

En les posant en diagonale tu va convertir tout le carré en question, et j'ai du mal à trouver une disposition plus optimale que celle là (à savoir où avec 2 virus tu convertis 2 cases et non une seule). T'as donc x² virus où le nombre de virus originaux est de x.

Satori9960 a écrit :

> De façon intuitive

Tout l'objectif est d'avoir une démonstration formelle. La solution tient en un seul mot (ie si vous l'avez, la démonstration est triviale).

Un circuit de course est circulaire, assez long, donc il y a des postes de ravitaillement placés n'importe où sur le circuit. Chaque poste ne peut délivrer qu'une certaine quantité de carburant à votre passage (pourtant, votre réservoir n'est pas limité), pas forcément suffisante pour rallier le point suivant. En revanche, la somme des capacités de tous les postes donne exactement la bonne quantité pour faire un tour complet.

Montrer qu'on peut choisir un poste de ravitaillement à partir duquel on peut faire un tour complet.

Satori9960 a écrit :

> En les posant en diagonale tu va convertir tout le carré en question

Absolument pas.
Tu a n-1 virus, pour des colonnes et lignes de n cases.
Il te manque fatalement un trou sur ta diagonale qui ne pourra pas être contaminé, car tu n'aura aucun virus de base sur cette ligne colonne d'où contaminer.*
A moins que le carré dont tu parle soit le carré n-1, la oui. Mais comme j'espère le montrer, ce ne sera absolument pas la disposition mathématiquement optimale.

Bien évidemment, c'est le n-1 qui pose problème.
Avec les mathématiques:
On a n-1 cases infectés dans la situation de départ. ces cases sont des carrés de 4 côtés. On a donc 4(n-1) côtés de cases infectés au départ.
Pour qu'une case soit infecté, elle doit être en contact avec deux côtés infectés.
Toute infection ne peut donc se produire que si une case a 2 côtés infectés, et toute case nouvellement infecté consommera ces deux côtés (côté consommé: côté ne pouvant infecter de nouvelles cases) et créera au maximum 2 côtés nouvellement infectés.
Mais pas obligatoirement. Les côtés extérieurs des cases infectés seront obligatoirement des côtés qui seront consommés sans aucun pouvoir d'infection (ils ne touchent qu'une case puisqu'ils forment le périmètre, et cette case doit être infecté a la base pour infecter le côté).
par conséquent, le nombre de côtés de cases infectés ne peut que rester stable ou diminuer.
Le nombre de côtés de cases infectés, pour remplir tout le carré, doit pouvoir couvrir tout les côtés de cases périphériques (celles consommés sans pouvoir d'infection).
Hors, ce nombre est connu; Pour un carré de nxn, il est de 4n.
Hors, le nombre de côtés de cases infectés de départ est, au mieux, 4(n-1).

Trois conclusions:
Ce nombre de virus, n-1, est insuffisant.
Le nombre maximum de carrés possiblement infectés est de n²-4 (puisque le potentiel d'infection maximal de départ est de 4n-4, et le potentiel nécessaire pour une infection totale est de 4n, toutes les cases peuvent être infectés, sauf 4).

PS: Pardonc, ma seconde conclusion est fausse je pense. En fonction de la taille du carré.

J'aurais tendance a croire que la disposition optimale nécessite qu'aucune case infecté de départ ne touche le bord du cadre. Mais je me demande comment contaminer alors, les cases du bord du cadre.
En fait, la contamination du bord du cadre au départ est indispensable et en même temps, voué a l'échec.

Ce qui fait qu'on a une démonstration bien plus évidente et plus rapide a effectuer, peut être:
Ou en tout cas, plus logique:
Pour contaminer tout le carré, il faut que toute ligne et colonne soit entièrement contaminé.
Pour contaminer une ligne ou colonne entière: Il faut soit que deux lignes ou colonnes entières soient contaminés (et tiennent la colonne ou ligne en question en étau, donc, adjacentes), soit qu'une case soit contaminé sur la ligne ou la colonne a la base (car la contamination ne peut être diagonale, donc, pour contaminer une ligne ou colonne, il faut un contaminant original).
On élimine la première solution, qui consiste a dire: Pour contaminer une colonne ou une ligne, il faut déjà en contaminer 2. Si on peut en contaminer 2, on peut a fortiori en contaminer entièrement une.

Or:
En estimant que chaque virus peut contaminer une ligne et une colonne, et qu'on a n lignes et n colonnes, il faut n virus. Nous avons n-1 virus. Il est donc impossible de s'assurer d'avoir un virus sur chaque ligne et colonne.
Et donc, impossible de contaminer toute ligne et colonne du carré.
Et donc, impossible de recouvrir le carré.

Pour le circuit:

On considère N nombre de points aléatoirement répartis sur un cercle. On appelle X le trajet du point A au point A+1 et X+1 le trajet de A+1 à A+2.
On a donc A, A+1,... A+N la liste des points répartis.
Et X, X+1,... X+N la liste des distances entre ces points.
Le total des distances entre ces points est égal a 360° (tour complet du cercle).

On considère des valeurs Y, Y+1,... Y+N ou le total de ces valeurs est de 360°.
On réparti aléatoirement ces valeurs aux points de A à A+N.

On effectue ensuite un calcul, en soustrayant a chaque Y la valeur Y-1, soit la valeur du point précédant le leur.
On associe chaque résultat, R obtenu, au point correspondant sur le cercle, soit le point auquel est associé Y.
On note Ar le résultat associé au point A, et Ar+1 le résultat suivant. On note Ar+X un résultat parmi l'ensemble, et (Ar+X)+1 le résultat du point suivant.
Si Ar+X est positif, cela signifie que le point A est atteignable a l'aide du carburant du point A-1. Ar est le gain de carburant supplémentaire effectué durant le trajet (indépendamment du carburant nécessaire au trajet)
Si Ar+X est négatif, cela signifie que le point A n'est pas atteignable a l'aide du seul carburant du point A-1. Ar est la perte de carburant supplémentaire effectué durant le trajet (indépendamment du carburant nécessaire au trajet)

Pour chaque Ar+X > 0, on remplace Ar+X par la valeur (Ar+X)+((Ar+X)+1). On remplace (Ar+X)+1 par la valeur 0.
On recommence l'opération a chaque valeur Ar+X supérieure a 0, jusqu'à ce qu'il ne reste que 2 valeurs Ar+X différentes de 0.
La valeur positive sera placé au point de départ optimal.


Bon, j'avoue, c'est beaucoup plus fouilli ici, parce que c'est toujours un truc dans lequel je me perds, les questions d'ensemble et de calculs d'ensemble.
En gros, on pondère chaque quantité de carburant de chaque point en fonction de la distance séparant le point pondéré du point suivant. On obtient un circuit avec des gains et des pertes de carburant net (dont le total fait 0). On élimine les valeurs négatives en les soustrayant au premières valeurs positives trouvés dans le sens inverse du parcours du circuit. On applique ces nouvelles valeurs pondérés au point détenant la valeur positive a laquelle on a soustrait. Le résultat peut être négatif.
On continue a éliminer les valeurs négatives en les associant aux valeurs positives trouvés aux points rencontrés en remontant le circuit, jusqu'à n'avoir que 2 valeurs, une positive et une négative (car le total de toutes les valeurs pondérés est de 0, il n'y a ni surplus, ni déficit de carburant au total sur la piste). La valeur positive donne l'emplacement de départ optimal.

C'est vrai, là, c'est la résolution a la Brutus. Il y a probablement un truc mathématique. Mais bon, je vais pas donner deux solutions dans le même post, c'est sale.
Faut bien que d'autres s'amusent.

D'ailleurs

Fausse énigme:

Fausse, parce qu'elle est idiote et simpliste. Mais on sais jamais, vous pourriez tomber dans l'énorme chausse-trappe que je vais tendre.
Je joue au go contre un ordinateur. Sur un Goban de NxN, nous avons chacun un nombre X(N²) pierres (X<N).
L'ordinateur va jouer comme ceci:
- Il cherchera toujours d'abord a prendre mes pierres. Il attaquera toujours par mon côté droit (sa gauche) et fera le tour de mes pierres dans un sens horaire (gauche, haut, droite, bas selon mon point de vue). Il abandonnera s'il vois que mes pierres ne sont plus prenables (règle des deux yeux).
- S'il ne peut pas effectuer la première directive, il mettra une pierre dans le coin supérieur gauche, puis, une pierre a côté, puis, une pierre a côté, et ainsi de suite, tant qu'il ne peut pas remplir le premier ordre.
- Il ne passera jamais son tour.
Je joue comme bon me semble.
Combien de pierres me faut il pour le vaincre ? Avec quel score ?

Comme je l'ai dit, ce n'est pas une vraie énigme, et pas une vraie énigme de maths. La solution est bien évidemment, évidente, mais bon, ça fera au moins faire 10 secondes de triturage. Je suis très mauvais pour me souvenir des énigmes, bien plus pour me souvenir des solutions.
(bon, je précise: Au Go, si vous vous demandez, vous posez des pierres sur des intersections de lignes. Vous perdez un groupe de pierres reliés entre elles si l'ennemi occupe toutes les libertés de votre groupe. Une liberté, c'est une intersection de ligne adjacente sur le côté ou la hauteur. Quand avec un groupe de pierre, vous formez deux "yeux", c'est a dire, des pierres en cercle autour d'une liberté laissé non prise, le groupe est imprenable, car on ne peut poser qu'une pierre par tour).

Milvian a écrit :

> Le nombre maximum de carrés possiblement infectés est de n²-4 (puisque le potentiel d'infection
> maximal de départ est de 4n-4, et le potentiel nécessaire pour une infection totale est de
> 4n, toutes les cases peuvent être infectés, sauf 4).

C'est une borne supérieure, pas un maximum.

> Pour contaminer tout le carré, il faut que toute ligne et colonne soit entièrement contaminé.

Ce raisonnement m'a l'air faux. Tu utilises à la fois la nécessité de contaminer toutes les lignes et le fait que ce n'est pas rentable d'en contaminer 2 pour en contaminer une. Bah pourtant, ca fait que tu peux en contaminer n-1 pour en contaminer n, donc c'est utile. D'ailleurs, avec une disposition en rectangle, il est possible d'infecter un rectangle de 2n+1 par n avec 2n virus.

> Pour le circuit:

Rien compris, et pourtant une solution tient en trois lignes, mais j'ai pu mal m'exprimer. Les positions des stations ne sont pas aléatoires mais imposées, ainsi que la quantité d'essence dans chaque station.

> Je joue au go contre un ordinateur. Sur un Goban de NxN, nous avons chacun un nombre X(N²)
> pierres (X<N)

C'est peut-être parce que je ne connais pas bien les règles du go, mais je ne comprends pas :
> - Il cherchera toujours d'abord a prendre mes pierres. Il attaquera toujours par mon côté droit
> (sa gauche) et fera le tour de mes pierres dans un sens horaire (gauche, haut, droite, bas
> selon mon point de vue). Il abandonnera s'il vois que mes pierres ne sont plus prenables (règle
> des deux yeux).

Que veut dire "attaquer", quel est le "côté droit" (s'il y a plusieurs blocs connexes ?), il fera le tour dans quel sens ? Par exemple, si on suit le carre n-2 x n-2 centre, l'ordinateur va se contenter de longer ? et du coup on gagne parce qu'il se prive tout seul de liberte pendant qu'on construit un oeil, et il suffit d'une pierre pour le fermer ensuite ?

Guest a écrit :

A minima, le raisonnement mathématique est juste.
La quantité de côtés de cases infectés ne pouvant que stagner ou diminuer, il faut que cette quantité soit suffisante dès le départ pour contaminer l'ensemble des côtés qui forme le périmètre de la grille.
Le périmètre de la grille est comptable comme étant n, le nombre de carré sur un bord de la grille, par 4, le nombre de bords de la grille.
Donc, il faut 4n côtés.
Hors, nous en avons a la base 4(n-1). Donc, un chiffre inférieur. Qui ne pourra encore une fois, que stagner ou diminuer.
Donc, c'est impossible.

Le raisonnement est logique: On cherche comment contaminer toute la grille.
Pour cela, il faut au moins ce demander quels sont les prérequis a la contamination d'une ligne ou d'une colonne.
Hors, pour contaminer une ligne ou une colonne, il faut soit qu'un contaminant soit présent sur la ligne ou la colonne a la base (aucune contamination par les diagonales n'est possible), soit qu'il y ai déjà 2 lignes contaminés entièrement qui la cernent.
Mais dire que la solution pour contaminer une ligne est d'en contaminer deux, reviens a dire que pour avoir A, il faut avoir 2A.
Nous, on cherche a obtenir les prérequis logiques a la contamination d'au moins une ligne.
Dire que le prérequis est d'en contaminer deux.. Très bien.
Quel est alors le prérequis pour en contaminer deux, qui soient, par définition, espacés d'au moins une ligne ou colonne (puisque le but est de contaminer la colonne ou ligne au départ de la réflexion toujours...)
Le prérequis est d'avoir deux contaminant, au minimum, 1 sur chaque ligne ou colonne, ou d'avoir 4 lignes ou colonnes (adjacentes, bien sur, a celles visés) qui soient contaminés a la base sur tout leurs carrés.

et on reboucle en augmentant les prérequis nécessaire jusqu'à avoir des chiffres supérieurs a n (dans les deux cas). Je ne compte même pas le paradoxe qui consiste a dire que pour que la ligne/colonne A soit contaminé, il faudrait contaminer les B et C qui sont ces colonnes/lignes adjacentes, et que pour contaminer B et C, il faut contaminer A qui leur est adjacente... Bref, ce prérequis n'est pas valide dans la démarche: Quels sont les prérequis a la contamination de la grille ?

En fait, sur ces deux prérequis, l'un est irréalisable car nous sommes plafonné a n-1 virus de base, alors qu'il en faut n, l'autre est impossible tout simplement parce qu'il reboucle sur lui même.
Donc, les prérequis sont impossibles. La disposition impossible.

Je sais que tu attends une propriété mathématique en deux mots qui explique toute la solution: Mais les solutions que je proposent, sont toutes deux valides.
Au passage, on ne peut pas considérer ma démonstration comme le fait que pour contaminer n lignes/colonnes, il faut contaminer n-1 lignes/colonnes. Car dans la grille, toutes les lignes et colonnes n'ont pas deux lignes ou colonnes adjacentes (les colonnes et lignes qui sont en position 1 et en position n, soient les bords de la grille).
Ces colonnes là ne répondent pas au prérequis de base de cette proposition: Elle n'ont pas assez de lignes ou colonnes adjacentes pour que ma proposition s'applique.


Pour le circuit:
Oui, très bien, les positions des stations sont imposés, la quantité d'essence aussi...
Mais est ce qu'on les a, ces positions ? Non.
Alors, comme on a pas de disposition précise, et qu'il n'y a aucune règle de disposition particulière de posé (n'importe ou n'est pas une règle mathématique, ou alors si, mais c'est l'aléatoire), on doit raisonner en envisageant toutes les possibilités pour intégrer la bonne par défaut. Pour ça, il faut donc prouver que peu importe le placement des points et les dispositions du carburant, la solution est possible.

Pour mon énigme: je pense que je donne la réponse en disant cela mais... Toutes les questions que tu te pose sont inutiles a sa résolution optimale. Promis.
Comme je l'ai dit, c'est pas une vraie énigme mathématique.
En fait, tu n'est pas très loin dans ta supposition de la résolution optimale. Mais comme je l'ai demandé, la résolution optimale est capable de vous dire combien de pierres sont nécessaire pour le vaincre.
Pour le score, on compte simplement qu'une pierre prise a l'ennemi vaux un point.
Mais en effet, je suis d'accord sur un point: Il vaux mieux connaitre les règles du go pour bien comprendre l'enigme. Quoi que mon explication des règles est pour ainsi dire, presque exhaustive, tant les règles de ce jeu sont simples.

Pour le circuit une simple récurrence marche bien:

n = 1 : trivial, une station qui a assez d'essence pour faire le tour

car n+1, en considérant n qui fonctionne.
On a somme des distances = somme des réserves de carburant. Il existe donc au moins 1 réserve de carburant supérieur ou égal à une distance. En partant de ce point, on peut donc arriver à un point suivant.
Partant de ce point, on peut donc considérer que la réserve de carburant est la somme des deux, et la distance à parcourir aussi. On revient alors à un cas n.

Elune Morningwood[62§o]Jumper a écrit :

Sauf que s'il existe un nombre suffisant de points de ravitaillement, on a pas 1, mais peut être 2, 3, voir 4 stations qui ont une réserve supérieure a la quantité nécessaire pour le trajet jusqu'à la station suivante.
Et on a donc aussi le cas contraire. Des stations avec moins de carburant que nécessaire.
La question est donc: Quel point de ravitaillement assure un excédent suffisant pour qu'il soit possible d'atteindre le point d'excédent suivant et ce jusqu'à faire le tour.

L'intuition voudrais qu'on dise: Le point qui en a le plus grand excédent. Sauf que les stations suivantes peuvent parfaitement avoir un déficit encore plus grand.

Au passage, si on part du principe qu'il y a un excédent quelque part, il va falloir considérer qu'il y a un déficit ailleurs. C'est mathématique.

La récurrence s'intéresse juste à réduire le nombre de station pour revenir à un cas connu dont on sait que la solution marche.

On va prendre le cas suivant avec tous les points avec 10 d'écart.

A-B-C-D-E-F-A

On a un total de carburant de 60.
A a 11
B a 10
C a 9
D a 9
E a 11
F a 10

On fait le cas n = 6
De A, j'arrive à B. On réduit alors le cas à n = 5. Avec le cas suivant:
A-C-D-E-F-A
Toutes les distances valent 10 sauf A-C qui vaut 20
Et la station A a maintenant le carburant de A et B soit 21

On est dans le cas n = 5 (dont on a déjà déterminé que c'était bon - principe de la récurrence)
En continuant, de A on arrive a C.
On a donc plus que A-D-E-F-A.
Avec d(AD) = 30, Carburant(A) = 11 + 10 + 9 = 30

Sur ce nouveau cas, de A on arrive a D. On réduit donc
A-E-F-A
Avec d(AE) = 40, Carburant(A) = 11 + 10 + 9 + 9 = 39

Sur ce nouveau cas, de E on arrive à F. On réduit donc:
A-E-A
Avec d(EA) = 20, Carburant(E) = 11 + 10 = 21

On est donc au cas a 2 points, de E on peut arriver à A et comme la somme de l'essence est suffisante pour faire le tour et qu'on est aller à toutes les stations, on a fait le tour en partant de E.

A partir du moment ou tu supprimes une station en la considérant absorbée par la station précédente qui parvient à l'atteindre, tu passes au cas n-1 que dont tu as déjà démontré que c'était réalisable car n=1 et n=2 sont trivial pour démarrer la récurrence.

Elune Morningwood[62§o]Jumper a écrit :

> La récurrence s'intéresse juste à réduire le nombre de station pour revenir à un cas connu
> dont on sait que la solution marche.

Et le raisonnement est juste.

Le mien pour cette énigme était un peu différent : tu pars de n'importe quel point, tu comptes en algébrique (positif ou négatif) ton carburant pendant un tour. La quantité d'essence atteint un minimum en une station. Il suffit de partir de cette station.

Bon, alors déjà, ça, non.
Juste non.
Rien que si on prends l'exemple d'Elune, la quantité d'essence sur son exemple atteint son minimum en E. Hors, si tu part du point E, tu n'arrivera même pas au point suivant.

Quand a la démonstration d'Elune... Elle a prouvé qu'on pouvait faire un tour complet.
Pas qu'on pouvait choisir un poste de ravitaillement à partir duquel on peut faire un tour complet.

Bien évidemment, dans son exemple, on sait instinctivement quel point choisir au départ.
Mais ça reste un exemple. Et d'ailleurs, un exemple ou les stations sont uniformément réparties le long du circuit. Alors que l'énoncé du problème ne nous indique absolument pas que cette répartition est uniforme.

En réalité, il faut partir du point suivant au point ou ton carburant atteint le minimum algébrique, parce que c'est uniquement en faisant d'abord tout le reste du circuit que tu peut espérer faire le tour complet au moment de passer ce point.
Mais ça revient a faire ce que j'ai fait: pondérer les quantités de carburant des stations par les distances qu'elles doivent couvrir, afin de faire apparaitre les déficits et bénéfices de carburant de chaque station, puis, absorber les déficits des stations en les répercutant sur les bénéfices des stations précédentes jusqu'à n'avoir plus qu'une station bénéficiaire.

je pourrais re-copier coller mon message précédent, mais je pense qu'on pourrait faire ça longtemps.

Milvian a écrit :

> Hors, si tu part du point E, tu n'arrivera même pas au point suivant.

Bah si. Parce que 11 (essence au point E) ≥ 10 (distance avant le point suivant).

Je me demande bien ce qui pose problème dans la démo (et je t'assure qu'elle est juste même si je l'ai décrite très rapidement).

> Quand a la démonstration d'Elune... Elle a prouvé qu'on pouvait faire un tour complet.
> Pas qu'on pouvait choisir un poste de ravitaillement à partir duquel on peut faire un tour
> complet.

Sa démonstration par récurrence permet de se ramener à un circuit dans lequel un poste a disparu. Si tu répètes ce procédé n-1 fois, il ne reste qu'un poste, c'est celui duquel il faut partir.

> En réalité, il faut partir du point suivant au point ou ton carburant atteint le minimum algébrique

La fonction est discontinue et a une discontinuité à chaque relais. En fonction de ce que tu considères comme "point suivant", ça peut changer. Ma formulation était plus précise : en regardant la quantité algébrique de carburant en partant d'une station quelconque, le minimum est atteint en un relais, il faut partir de ce relais. Je maintiens cette affirmation.

Guest a écrit :

> Hors, si tu part du point E, tu n'arrivera même pas au point suivant.

Autant pour moi.
Jai confondu le point E et D.
Et si tu me dit que du point D, tu arrive au point suivant sans pousser la voiture, je veux ta recette.
Parce que c'est pas au point E que tu atteint ton minimum, mais au point D.
Et c'est parce que tu atteint ton minimum en D que tu doit partir du point suivant, le point E (Parce que j'estime que la notion de "point suivant" a partir du moment ou tu a nommé tes points A, B, C, D, E, etc... n'est pas une notion variable).
Compte en algébrique dans l'exemple d'Elune, tu aura toujours ton minimum en D. Peu importe d'où tu part.
Après, si tu place ton résultat algébrique a chaque fin de trajet, là tu aura ton minimum en E. Mais après, c'est ma considération personnelle: Tu part du point, en prenant l'essence, et tu fait le trajet. Ton résultat algébrique est a placer selon moi, au point d'où tu a tiré l'essence utilisé.
Et dans l'absolu, je maintiens et affirme que ta solution est basiquement exactement la même que la mienne: Pondérer l'essence par la distance a parcourir.
Et je me cite puisque ça semble nécessaire:
En gros, on pondère chaque quantité de carburant de chaque point en fonction de la distance séparant le point pondéré du point suivant. On obtient un circuit avec des gains et des pertes de carburant net (dont le total fait 0). On élimine les valeurs négatives en les soustrayant au premières valeurs positives trouvés dans le sens inverse du parcours du circuit. On applique ces nouvelles valeurs pondérés au point détenant la valeur positive a laquelle on a soustrait. Le résultat peut être négatif.
On continue a éliminer les valeurs négatives en les associant aux valeurs positives trouvés aux points rencontrés en remontant le circuit, jusqu'à n'avoir que 2 valeurs, une positive et une négative (car le total de toutes les valeurs pondérés est de 0, il n'y a ni surplus, ni déficit de carburant au total sur la piste). La valeur positive donne l'emplacement de départ optimal.

La seule différence, c'est que je pondère ensuite les déficits en cherchant les surplus de carburants les plus prêt capable de les absorber. A la fin, tout les déficits sont absorbés a un relais, qui est le relais pour débuter la course (car en partant de ce point, on peut par la suite obtenir une séquence de surplus capable d'absorber la séquence de déficit).

Milvian a écrit :

 A o  o  o  o  o  o  o  o  o  o
11 10 9  8  7  6  5  4  3  2  1
 B o  o  o  o  o  o  o  o  o  o
11 10 9  8  7  6  5  4  3  2  1
 C o  o  o  o  o  o  o  o  o  o
10 9  8  7  6  5  4  3  2  1  0
 D o  o  o  o  o  o  o  o  o  o
 9 8  7  6  5  4  3  2  1  0  -1
 E o  o  o  o  o  o  o  o  o  o
10 9  8  7  6  5  4  3  2  1  0
 F o  o  o  o  o  o  o  o  o  o
10 9  8  7  6  5  4  3  2  1  0

Je viens de faire le tableau qui indique kilomètre par kilomètre le niveau du réservoir. Le minimum est bien atteint en E, donc tout va bien.

> Compte en algébrique dans l'exemple d'Elune, tu aura toujours ton minimum en D. Peu importe
> d'où tu part.

Bah non, vraiment pas. Et je crois que je comprends comment tu as compté, mais ce n'était vraiment pas naturel, et je déplore que tu n'aies pas fait l'effort inverse de considérer que notre explication se tenait : en l'occurence, les 10 km d'essence du segment [DE] finissent d'être consommés au point E, et pas au point D.

Un inconnu vous propose le jeu suivant : vous écrivez 50 nombres de votre choix sur 50 papiers distincts (aucune limitation sur les nombres à inscrire).

Lui aura les 50 papiers et va en retourner autant qu'il veut, mais un papier ne peut être retourné qu'une seule fois. À un moment, il s'arrête et dit « Le dernier papier que j'ai retourné était le plus grand de la série. ». S'il a raison, il empoche X euro. S'il a perdu, il vous donne un euro. Pour quelles valeurs de X accepteriez-vous de jouer ou pas ?

Guest a écrit :

> Pour quelles valeurs de X accepteriez-vous de jouer ou pas ?

Moon HyunA a écrit :

C'est une réponse acceptable, mais tu ne joueras pas non plus si X = 0.01 (je précise que quand il l'empoche, c'est que tu lui offres).

Guest a écrit :

Je ne comprends pas où vous voulez en venir...

Moon HyunA a écrit :

Bah avec les règles que j'ai données, on a effectivement intérêt à jouer pour toute valeur de X négative.

Mais on peut aussi accepter pour de petites valeurs de X (par exemple un centime), si on pense que la personne ne peut pas trouver le plus grand papier plus de 99 fois sur 100 [#].

Donc par exemple, pour X = 1 euro, est-ce qu'on a intérêt à jouer ? Plus précisément, à partir de quelle valeur vous arrêtez de jouer ? Historiquement, il me semble que l'anecdote était racontée avec X = 10.

[#] En fait, c'est 100 fois sur 101, le ratio, mais c'est presque pareil.

PS: Sauf si vraiment ça pose problème, je crois que je préfère le tutoiement

Pour le problème précédent : une stratégie simple : retourner la première moité des nombres, en noter le maximum M. Retourner ensuite des papiers de la deuxième moitié jusqu'à trouver une valeur dépassant M. S'arrêter alors. Cette stratégie garantit une probabilité > 1/4 de réussir.

On place une valise V1 (pavé droit ou parallélépipède rectangle) dans une valise V2. Montrer que la somme des trois dimensions de V1 est inférieure à la somme des trois dimensions de V2.

Donner un algorithme qui permet de trouver une paire de points les plus proches dans le plan et qui soit meilleur que quadratique (strictement).

Des balles numérotées entrent et sortent d'une boite. On veut écrire un programme qui permet de dire à chaque instant si toutes les balles dans la boite portent le même numéro. On dispose pour cela d'un nombre borné de cases mémoires, dont le contenu doit rester polynomial entre (N+M) (N étant le nombre total de boules rentrées, M le nombre de couleurs).
(La dernière précision est juste là pour éviter un codage rébarbatif du contenu de la boite).

Soit deux matrices 2×2 A et B réelles. On considère F = Vect(A,B,I), et on suppose que AB est dans F. Montrer que BA est dans F.

On prend un carré de 8×8 auquel on retire la case en haut à droite et la case en bas à gauche. Peut-on pavé l'espace restant avec des dominos 2×1 ?

Guest a écrit :

> On prend un carré de 8×8 auquel on retire la case en haut à droite et la case en bas à gauche.
> Peut-on pavé l'espace restant avec des dominos 2×1 ?

Guest a écrit :

> On prend un carré de 8×8 auquel on retire la case en haut à droite et la case en bas à gauche.
> Peut-on pavé l'espace restant avec des dominos 2×1 ?

Viendrez-vous à bout de l'exercice de maths qui a tenu en échec les bacheliers écossais ?

(Solution dessous en vidéo)


Edit. Bon c'est faisable rapidement, les 2 premières questions sont archi simple et la recherche de l'extremum est simplement calculatoire sans vrai piège.

Gum a écrit :

Trop facile, mon bac vaut mieux que ça on dirait. #noTroll

Essayons celle ci alors!

Quel est le numéro de la place de parking sous la voiture?


Encore une autre? Essayons celle-ci:


Dans quel sens se dirige ce bus?

Gum a écrit :

> Quel est le numéro de la place de parking sous la voiture?



> Dans quel sens se dirige ce bus?

Pour le bus :

Pour le bus, on manque d'informations



Reponse :

Yeahh!
Réponses:

On joue au 301, ou au 501. Le but c'est de faire le nombre de points indiqués, et pas un de plus. (on nous enlève ceux de trop si jamais, et on recommence jusqu'à faire le compte)

Pourquoi il vaut mieux viser le triple 19, que le triple 20, si on est pas très sûr de soi ?

NerdosValkyry a écrit :

Les points a proximités en cas de raté sont plus importants ?

Finidia [78§i] a écrit :

Exactement ! Si on manque de précision, statistiquement on fera plus de points en visant le triple 19 (et faire un 1 ça pique). L'idée étant qu'il faut monter le plus vite possible vers 3/500, et une fois qu'on approche, on se met vraiment à viser, pour finir pile. Par exemple arrivé à 450, on va viser le triple 17, que si on y arrive c'est gagné. (être bon en calcul mental ou avoir une calculatrice aide beaucoup à finir vite)

Vous saviez pas que jouer aux fléchettes, ça fait faire des maths ?

Tiens, ça me fait penser : Quel est le calcul qu'on n'arrête pas de faire, arrivé à 2/441 ? (En étant précis, cette fois, sinon ça sert pas à grand chose)

4 grenouilles sont disposées en carré (sur le plan, aux coordonnées 0,0 ; 0,1 ; 1,0 et 1,1). Le seul mouvement autorisé, c'est qu'une grenouille peut sauter par-dessus une autre, et se retrouve alors à la position symétrique (par rapport à la première). Au bout d'un certain nombre de mouvements, peuvent-elles se retrouver en 0,0 ; 0,2 ; 2,0 et 2,2 ? En 0,0 ; 0,3 ; 3,0 ; 3,3 ? Pour chaque, si oui, en combien de coups au minimum ?

On prend une grille de taille 2^n×2^n (par exemple de taille 256×256). On noircit une case quelconque. Ensuite, on peut noircir trois cases si elles sont contigues avec un angle (voir ici). Montrer qu'on peut noircir toute la grille quelle que soit la case noircie (et quel que soit n).

1. On peut toujours construire un triomino de taille n à partir de quatre triominos de taille n-1 en les combinant de la manière suivante.






Cette construction est valide quelque soit la rotation d'un angle multiple de 90° ; il est possible d'orienter ces triominos n'importe comment dans la grille. L'énoncé nous autorise à placer des triominos de taille 1. Par récurrence, on est donc capables de placer des triominos de taille n > 0 quelconque, de coté 2^n x 2^n.

2. A partir d'une grille de taille 2^n x 2^n avec une seule cellule noircie, on montre qu'on peut tout noircir. On part d'une décomposition en quadtree de la grille, où - la grille étant de dimension 2^n x 2^2 - chaque niveau de l'arbre décompose une sous grille de taille 2^i x 2^i en quatre grilles de taille 2^(i-1) x 2^(i-1).

On noircit récursivement, de sorte que la surface noircie à l'étape i soit de taille 2^i x 2^i, correspondant exactement à un sous-arbre du quadtree de hauteur (i+1). A l'étape 0, on part de la case noircie, soit une zone noircie de 1x1, correspondant à une feuille du quadtree. A chaque étape i suivante, on part de du nœud noirci dans le quadtree, on remonte au nœud parent, et on recouvre les trois autres nœuds fils d'un triomino de taille i. En effet, les trois fils représentent des zones "contingües avec un angle". Après la n-ème étape, on a noirci toute la grille.

Je ne vous sens pas convaincus. Alors une petite animation pour démontrer la correction de l'algorithme.

Sylvius de Napline a écrit :

> Je ne vous sens pas convaincus.

Si si, (bravo d'ailleurs) mais il existe une manière (à mon avis) plus élégante de le formuler, même si cette démonstration est rigolote.

On peut :
1/ couper le carré en 4
2/ regarder dans quelle partie se situe le point noircit
3/ placer un triomino à cheval sur les 3 autres carrés
4/ recommencer récursivement dans les 4 carrés (il manque maintenant un point à chaque).

--------------

100 personnes sont enfermées et ont le droit de se concerter. Puis on va leur assigner un numéro entre 1 et 100 (on peut donner le même à plusieurs personnes), et il faut qu'une au moins devine son numéro. Comment faire ?

Effectivement. C'est aussi beaucoup plus clair expliqué ainsi !

So Alive a écrit :

> 100 personnes sont enfermées et ont le droit de se concerter. Puis on va leur assigner un numéro
> entre 1 et 100 (on peut donner le même à plusieurs personnes), et il faut qu'une au moins devine
> son numéro. Comment faire ?

il manque une donnée dans ton problème ; tel que tu l'as posé, il s'agit pour chaque personne de deviner un nombre entre 1 et 100 sans aucune information.

Gâterie a écrit :

> il manque une donnée dans ton problème ; tel que tu l'as posé, il s'agit pour chaque personne
> de deviner un nombre entre 1 et 100 sans aucune information.

Effectivement j'ai oublié de préciser qu'une fois que les numéros sont attribués, chaque personne peut voir les autres chapeaux.

Bah le premier annonce un nombre qu'il voit. Les autres annoncent le même nombre.

Gâterie a écrit :

Bah le premier annonce un nombre qu'il voit. Les autres annoncent le même nombre.

C'est pas encore plus simple?
"Hey machin ton numéro est X"
"J'ai deviné que mon numéro était X".

Je veux dire... Ils ont le droit de se concerter? :')

Hélas, la concertation ne peut avoir lieu qu'avant la distribution des numéros. Une fois qu'ils sont distribués, plus de communication possible, et en particulier les annonces de numéros se font secrètement.

Du coup il n'y a pas de solution.

Il n'y a aucune corrélation entre les numéros que voit un prisonnier et son propre numéro (puisqu'il peut avoir un numéro déjà présent, ou un autre numéro). Il ne peut pas faire passer d'information aux autres prisonniers. Chaque prisonnier en est donc réduit à deviner un nombre aléatoire entre 1 et 100.

A moins éventuellement qu'ils choisissent dans quel ordre ils annoncent leur numéro. Et dans ce cas ça revient à la solution que j'ai déjà mise (il faut juste qu'ils s'attribuent des numéros au départ ; puis si le prisonnier numéro n annonce qu'il va répondre, ça signifie à tous les autres que quelqu'un d'autre porte le numéro n).

Comme je le disais, il manque une donnée à ton problème.

Désolé du double post, mais je pense que ça le mérite (si quelqu'un suit le sujet et a juste vu la connerie que j'ai écrite au-dessus... qu'il voit qu'il y a un nouveau post).

Donc on remplace 100 par 2 : 2 personnes sont enfermée, on leur attribue un nombre entre 1 et 2 (potentiellement le même), l'une d'entre elle au moins doit deviner le nombre qu'elle a. Stratégie : la première personne va dire le nombre qu'elle voit, la seconde va dire le nombre qu'elle ne voit pas. Résultats en fonction des nombres qu'elles ont :
* [1, 1] : la première personne répond 1, la seconde 2, gagné !
* [1, 2] : la première personne répond 2, la seconde 2, gagné !
* [2, 1] : la première personne répond 1, la seconde 1, gagné !
* [2, 2] : la première personne répond 2, la seconde 1, gagné !

... Bref si ça marche avec deux personnes, je ne serais pas si étonné qu'on puisse faire marcher le truc à n personnes. Ca a l'air d'être lié à une affaire de point fixe à la con sur des trucs compliqués (point fixe qui serait lié à une histoire de cardinalité, l'espace des stratégies étant bien plus grand que l'espace des fonctions [1,n] -> [1,n]). J'ai pas trop le temps de développer maintenant, mais oui, il est possible que le problème soit bien posé. A mon avis, si on trouve une stratégie gagnante à 3 personne, c'est gagné, on arrivera à la généraliser à une stratégie gagnante à n personnes.

(désolé du triple post, mais qu cas où So Alive continue a passer, qu'il voit la solution)

J'ai trouvé une solution, en résolvant en force brute le cas à 3 prisonniers puis en tentant de comprendre la structure. Je suppose que quelqu'un de plus malin aurait pas passé des plombes à décortiquer le truc pour trouver une solution aussi simple...

Note : toutes les opérations sont faites modulo 100 ; évidemment, lorsqu'une de ces opération répond "0" modulo 100, il faut lire "100".

Les prisonniers vont commencer par se numéroter de 1 à 100. Le prisonnier numéro n va annoncer le nombre g(n) :
g(n) = n - sum(nombres qu'il voit sur les autres prisonniers).

Démonstration que ça fonctionne : on note f : [1,100] -> [1,100] la fonction qui au prisonnier numéro n associe le nombre qui lui est assigné f(n). On note m = sum(f(n)). On va montrer que g(m) = f(m), ie que le prisonnier m répond le nombre qui lui est attribué.
g(m) = m - sum(nombres qu'il voit sur les autres prisonniers)
= m - sum_(n différent de m) (f(n))
= sum(f(n)) - sum_(n différent de m) (f(n))
= f(m)
qed


Note : je doute de l'applicabilité effective de cette solution. Mettons que les 100 prisonniers arrivent à se numéroter sans s'embrouiller, il faut ensuite que chacun fasse une somme de 99 nombres à deux chiffres, suivi d'une soustraction de deux nombre à deux chiffres... Les opérations ont beau être modulo 100, je doute qu'aucun prisonnier ne fasse d'erreur.


edit : question subsidiaire : à partir de la solution que j'ai trouvé, on peut construire d'autres solutions en changeant la numérotation des prisonniers. Existe-t-il encore d'autres solutions ?

Gâterie a écrit :

Note : je doute de l'applicabilité effective de cette solution.

Surtout quand on sait que juste avoir tout le monde qui dit le même nombre donne une très bonne chance d'être libéré

Gâterie a écrit :

Les prisonniers vont commencer par se numéroter de 1 à 100. Le prisonnier numéro n va annoncer le nombre g(n) :
g(n) = n - sum(nombres qu'il voit sur les autres prisonniers).

Hic.
On imagine un monde où les 100 prisonniers ont tous le chiffre 1, le premier gars passe donc g(1) = 1 - 99 = -98, c'est ce qu'il doit annoncer ?

Démonstration que ça fonctionne : on note f : [1,100] -> [1,100] la fonction qui au prisonnier numéro n associe le nombre qui lui est assigné f(n). On note m = sum(f(n)). On va montrer que g(m) = f(m), ie que le prisonnier m répond le nombre qui lui est attribué.
g(m) = m - sum(nombres qu'il voit sur les autres prisonniers)
= m - sum_(n différent de m) (f(n))
= sum(f(n)) - sum_(n différent de m) (f(n))
= f(m)
qed

Il y a deux choses ici : tu as seulement prouvé que g(m) = f(m), ça reste un cas très particulier. De plus ce cas n'a plus aucun sens dès lors que tu as la m = sum(f(n)) > 100, c'est à dire à partir du moment où l'un des prisionniers a un numéro supérieur ou égal à deux. Ca n'a plus de sens car tu définis tes fonctions à partir de [[1,100]] et on peut avoir m > 100 dès, quelque soit n, f(n) > 2, donc f(m) n'est pas définie.

Une solution où 99% des prisonniers s'en sortent serait comme t'essaies de le mentionner, le premier prisonnier se sacrifie en annonçant la somme des 99 autres nombres qu'il voit, puis les 99 concernés excluent celui qui s'est sacrifié et font nombre annoncé moins les 98 autres nombres que je vois.
Une solution où 100% des prisionniers s'en sortent serait le cas précédent + s'ils ont le droit d'ajouter une seconde information du type "mon numéro est xxx, et la somme des prisonnier est yyy"

Emile Loir a écrit :

Gâterie a écrit :

Note : je doute de l'applicabilité effective de cette solution.

Surtout quand on sait que juste avoir tout le monde qui dit le même nombre donne une très bonne chance d'être libéré

Pas sur, vu que "(on peut donner le même à plusieurs personnes)", dans la mesure qu'on ne sait pas à quel point un même nombre peut être donné plusieurs fois, il y a toujours des risques incalculables que le numéro choisit ne soit juste jamais cité...

Emile Loir a écrit :

> Gâterie a écrit :
>
>

> Note : je doute de l'applicabilité effective de cette solution.
>

>
> Surtout quand on sait que juste avoir tout le monde qui dit le même nombre donne une très bonne
> chance d'être libéré

A peu près 2 chance sur 3.




Question subsidiaire : est-il possible de créer une stratégie qui a moins de chance de réussir que "chacun dit un nombre au hasard" ?


O. a écrit :

> On imagine un monde où les 100 prisonniers ont tous le chiffre 1, le premier gars passe donc
> g(1) = 1 - 99 = -98, c'est ce qu'il doit annoncer ?

2.

Un calcul modulo 100 signifie, pour simplifier, que l'on peut ajouter ou retirer 100 au résultat (avec pour but d'obtenir un résultat entre 1 et 100) (en vrai le but est d'obtenir un résultat entre 0 et 99, mais j'ai précisé qu'un "0" devait se lire comme un "100"). Pour faire encore plus simple (et partiellement faux), à chaque opération on ne garde que les deux derniers chiffres du résultat.

> Il y a deux choses ici : tu as seulement prouvé que g(m) = f(m), ça reste un cas très particulier.

J'ai montré plus précisément que pour tout f : [1,100] -> [1,100], il existe m tel que g(m) = f(m). Ce qui est le résultat attendu. (J'aurais pu écrire g_f(n) ou g(f, n) à la place de g pour mettre en valeur la dépendance de g par rapport à f pour plus de clarté). Et il est vrai, ma démonstration présuppose pas mal de choses sur les calculs modulo 100 (en gros, toutes les petites propriétés qui garantissent qu'opérer modulo 100 a du sens), mais je voulais éviter de faire un cours sur Z/nZ pour éviter de faire un post imbitable.

Draziel a écrit :

Pas sur, vu que "(on peut donner le même à plusieurs personnes)", dans la mesure qu'on ne sait pas à quel point un même nombre peut être donné plusieurs fois, il y a toujours des risques incalculables que le numéro choisit ne soit juste jamais cité...

Oui, ça présuppose que les numéros sont répartis aléatoirement. Cela-dit, c'est pas absurde comme notion. Si t'as 20 fois le numéro 5, c'est pas aberrant de se dire "y a ptêt une chance que moi aussi j'ai le numéro 5", et d'adapter la stratégie en conséquence.
S'ils sont répartis aléatoirement pour de vrai, comme Gâterie a dit, c'est de l'ordre de 2/3 (je crois que j'avais calculé 61%?)

Gâterie a écrit :

Question subsidiaire : est-il possible de créer une stratégie qui a moins de chance de réussir que "chacun dit un nombre au hasard" ?

Si les nombre sont répartis de manière suffisamment aléatoire (et particulièrement, si chaque numéro est indépendant des autres) je ne pense pas.

T'as toujours au moins une chance sur 100 de tomber sur le bon nombre. (Sauf si on suppose que tu peux répondre autre chose qu'un nombre entier entre 1 et 100. Genre "bleu" ou "pi").

O. a écrit :

Une solution où 99% des prisonniers s'en sortent serait comme t'essaies de le mentionner

Ben c'est pas possible. C'est soit tout le monde, soit personne.
Cela-dit, je suis curieux de connaître la "vraie" solution, si ce que dit Gâterie n'est pas la solution recherchée.

Emile Loir a écrit :

> S'ils sont répartis aléatoirement pour de vrai, comme Gâterie a dit, c'est de l'ordre de 2/3
> (je crois que j'avais calculé 61%?)

Note bien que mon "2/3" est une estimation rapide quand on a pas envie (ou le temps) de faire le calcul, et bien assez efficace dans le contexte d'un jeu de rôle (peut-être pas tout à fait assez efficace dans le cadre d'un jeu compétitif - je sais pas, je suis pas joueur pro, c'est eux qui savent avec quelle incertitude ils doivent évaluer les probas). Ton 61% est sans doute plus juste (j'ai toujours la flemme de faire le calcul).


> Gâterie a écrit :
>
> > Question subsidiaire : est-il possible de créer une stratégie qui a moins de chance
> > de réussir que "chacun dit un nombre au hasard" ?
>
> Si les nombre sont répartis de manière suffisamment aléatoire (et particulièrement, si chaque
> numéro est indépendant des autres) je ne pense pas.
>
> T'as toujours au moins une chance sur 100 de tomber sur le bon nombre. (Sauf si on suppose
> que tu peux répondre autre chose qu'un nombre entier entre 1 et 100. Genre "bleu"
> ou "pi").

Justement, tu raisonnes comme je raisonnais au début sur la question (quand je pensais que c'était pas possible) : chacun a une chance sur 100 de répondre le bon nombre, la connaissance des autres nombres ne fournit aucune information sur le nombre qu'un prisonnier a.

Or, pour résoudre, on met en commun les infos de façon détourné. Au final on fait en sorte qu'exactement un prisonnier ait le bon résultat : chaque prisonnier a donc toujours 1% de chance d'avoir le bon résultat, mais on a cassé l'indépendance entre leur chance de succès grâce à la stratégie globale : P(tout le monde échoue) n'est plus égal à Prod_i (P(le prisonnier i échoue)) mais à 0.

La question est donc : est-il possible de déformer ces probabilités dans l'autre sens ? De faire en sorte que P(tout le monde échoue) soit cette fois plus grand que Prod_i (P(le prisonnier i échoue)) ?


... La réponse est oui, quand on raisonne à 2 prisonniers :

En répondant au hasard, chacun a 1 chance sur 2 de se planter, et donc au total 1/4 que tout le monde se plante. Considérons la stratégie suivante : chaque prisonnier donne le numéro qu'il voit sur l'autre prisonnier. Résultats :
* [1, 1] : la première personne répond 1, la seconde 1, gagné !
* [1, 2] : la première personne répond 2, la seconde 1, perdu :/
* [2, 1] : la première personne répond 1, la seconde 2, perdu :/
* [2, 2] : la première personne répond 2, la seconde 2, gagné !
Soit une chance sur deux de perdre, plus qu'en répondant au hasard.

... Comme on le voit, ici le pricipe est inverse de la stratégie gagnante : au lieu de faire en sorte qu'un unique prisonnier gagne, on fait en sorte qu'ils gagnent tous ensemble.

Du coup, quelle est la stratégie la moins efficace, et sa probabilité de gagner quand même ? (Il me semble qu'on peut minorer ce nombre par 1/(nombre de prisonnier) pour des raisons de probabilité : P(le prisonnier i gagne) doit rester égal à 1/n. Je subodore qu'il est possible d'atteindre ce 1/n : il s'agit de faire en sorte que P(le prisonnier i gagne) = P(tous les prisonniers gagnent)).



> Oui, ça présuppose que les numéros sont répartis aléatoirement. Cela-dit, c'est pas absurde
> comme notion. Si t'as 20 fois le numéro 5, c'est pas aberrant de se dire "y a ptêt une
> chance que moi aussi j'ai le numéro 5", et d'adapter la stratégie en conséquence.

Intuition : tu te trompes.

Une des intuition que j'ai eu pour trouver ma solution en force brute (avec 3 prisonniers), c'est "si tous les nombres sont égaux, alors tous les prisonniers doivent donner un nombre différent". Je suis absolument incapable de démontrer cette intuition - elle m'est venue pour des raisons de symétrie (la situation "tout le monde a le même nombre" est la situation la plus symétrique possible en entrée, la réponse "tout le monde donne un nombre différent" est la réponse la plus symétrique possible - sachant que, comme expliqué plus haut, il ne faut jamais que deux prisonniers gagnent en même temps pour assurer une victoire globale automatique). Cf aussi le cas à deux prisonniers (en répondant le truc qu'ils voient, il minimisent leur chance de victoire).

Mais je répète, c'est juste une intuition que tu te trompes. Une intuition éclairée, mais une intuition, rien de plus.

Ok, je vois.
Tu peux effectivement avoir une méthode suboptimale qui tournera aux alentours de 40% de réussite, en copiant ce que tu as fait avec deux joueurs.

Tu groupes les participants deux par deux et ils doivent dire le numéro de l'autre. Vu que la seule possibilité pour que l'un des deux gagne est que les deux aient le même numéro, ça réduit la possibilité de gagner. Si les participants sont en nombre impair, y en a un qui dit un nombre aléatoire. Ca doit augmenter un peu le taux de réussite, mais sûrement pas significativement.
Je suis pas certain qu'il soit possible de faire "mieux". Je ne vois pas comment forcer plus de 2 joueurs à partager le même nombre.

Une des intuition que j'ai eu pour trouver ma solution en force brute (avec 3 prisonniers), c'est "si tous les nombres sont égaux, alors tous les prisonniers doivent donner un nombre différent".

Je comprends pas ce que tu veux dire.
Tu veux dire que si tout le monde a le même numéro, alors la stratégie la plus efficace est de tous donner un numéro différent?

Moi, je vois 99 personnes ayant le numéro 5, je me dis pas "Ok, je garde ma stratégie, et je dis un nombre fixé à l'avance". Direct, je dis 5. Si je suis le seul à pas avoir 5, c'est pas grave, logiquement les autres auront la présence d'esprit de dire 5 en voyant 98 numéros 5.

On est bien d'accord qu'il s'agit d'un cas particulier et que c'est pas une stratégie viable toute seule. Par exemple s'il y a 6 cinq et 6 sept et que le reste est faible, je suis pas certain que ce soit viable (les "cinq" verront plus de sept et les "sept" verront plus de cinq). Il s'agit réellement d'une stratégie alternative quand un nombre est très nettement en supériorité numérique (sans que ce soit nécessairement tout le monde. Même 20%, s'il n'y a pas d'autres nombre en concurrence, c'est valable).

il ne faut jamais que deux prisonniers gagnent en même temps pour assurer une victoire globale automatique

Ah bon? Pourquoi?
Même dans ta stratégie à 100%, je ne suis pas convaincu que la solution soit unique.

Gâterie a écrit :

D'ac, j'avais zappé ta petite phrase sur le modulo 100.

Tu peux aussi écrire directement g(n) = n - sum(nombres qu'il voit sur les autres prisonniers) % (ou mod) 100, ça irait plus vite et ça permettrait d'éviter ce genre de confusion.

Gâterie a écrit :

> J'ai trouvé une solution

Bravo ! Et c'est cool de voir du monde sur ce topic.

Je précise à tout hasard qu'il n'y avait aucune considération de probabilité dans l'énoncé, entre autres parce que la distribution des valeurs sur les chapeaux n'est pas connue. On aurait pu d'ailleurs supposer que les numéros sont attribués en fonction de la stratégie choisie de manière à piéger les prisonniers. La notion de proba reste un outil intéressant quand même (par exemple, si on pouvait montrer que la probabilité de se planter est strictement positive quand la distribution des nombres est uniforme, alors on aurait répondu). Il y a des démonstrations vraiment cools qui utilisent des raisonnements de ce genre.

Cette histoire de "dé-indépendantiser" les probabilités s'applique dans d'autres énigmes, par exemple :
« 100 personnes ont le droit de se concerter puis vont être isolées dans des cellules. Chacune à tour de rôle sera emmenée dans une pièce contenant 100 tiroirs. Chaque tiroir contient le nom d'une personne différente, et chaque personne peut ouvrir 50 tiroirs et doit trouver son nom. Si une personne ne trouve pas son nom, tout le monde meurt. Comment maximiser la probabilité de survivre, peut-on avoir mieux que 1/(2^100) ? »

Ici, la notion de proba est pertinente si on considère que l'univers est la permutation initiale des tiroirs. Et il devient très facile d'avoir une stratégie qui fait moins bien que le hasard.

Il reste aussi celle-ci pour laquelle personne n'a proposé de réponse.

O. a écrit :

> Tu peux aussi écrire directement g(n) = n - sum(nombres qu'il voit sur les autres prisonniers)
> % (ou mod) 100, ça irait plus vite et ça permettrait d'éviter ce genre de confusion.

Je ne suis pas d'accord. Tu as supposé que les nombres manipulés étaient des entiers. La phrase de Gâterie précisait qu'il ne manipulait plus des entiers mais des éléments de ℤ/100ℤ, et avec les opérations usuelles, ses égalités sont du coup correctes sans besoin d'alourdir les notations.

Emile Loir a écrit :

> > il ne faut jamais que deux prisonniers gagnent en même temps pour assurer une victoire
> > globale automatique
> >
> Ah bon? Pourquoi?
> Même dans ta stratégie à 100%, je ne suis pas convaincu que la solution soit unique.

C'est une intuition que j'avais quand j'ai essayé de résoudre, c'est lié à une question de cardinalité mais je n'arrivais pas à le montrer ; lorsqu'on résout le cas à 3 prisonnier en force brute, c'est un truc qu'on voit apparaître, qui semble évident (on ne peut pas faire autrement) mais difficile à montrer. Avec la vision probabiliste, ça devient très simple à montrer.

@So Alive : parler de proba ici, c'est juste une façon alternative de parler de cardinaux ; il s'agit simplement de compter le nombre de configuration gagnante, et de diviser par le nombre de configuration. Il ne s'agit peut être pas de la probabilité réelle de gagner (si les interrogateurs adaptent les nombres à la stratégie etc), ça n'en reste pas moins une mesure de probabilité valable qui suit tous les théorèmes de proba.

Bref, avec une approche probabiliste, chaque prisonnier a 1% de chance de gagner ; pour la bête raison qu'il a toujours une configuration gagnante sur 100 (quoi que réponde le prisonnier 1 quand il ne voit que des 1, il y a 1 configuration où il gagne et 99 où il perd).

Maintenant, ce qui nous intéresse, c'est pas la chance de gagner de chaque prisonnier, mais la chance qu'au moins un prisonnier gagne :

P(prisonnier 1 gagne ou prisonnier 2 gagne ou ...) <= sum_i P(prisonnier i gagne) = sum_i (1%) = 1
(c'est pas une flèche mais un "inférieur ou égal")

Avec égalité si et seulement si les événements sont deux à deux disjoints, ie si et seulement si :
pour tout i et j, P(prisonnier i gagne et prisonnier j gagne) = 0
ie, une stratégie gagne à tous les coup si et seulement si elle ne fait jamais gagner deux prisonniers en même temps, qed.

@So alive : tout ça pour dire que les probas sont "juste" un outil dans ma trousse à outil, éclairant le problème sous un autre jour. J'ai "senti" qu'il fallait un unique gagnant par configuration, j'ai "senti" que c'était lié à un problème de cardinal, j'arrivais pas à le montrer (du moins, sans y passer des heures et au moins une dizaine de page). En prenant une approche probabiliste, ça m'est apparu comme une évidence de 5 lignes - parce que même si les proba discrètes ne sont qu'une reformulation des cardinaux et du dénombrement, on n'y raisonne pas exactement de la même façon, on n'y a pas la même façon d'appréhender le problème etc.


> Moi, je vois 99 personnes ayant le numéro 5, je me dis pas "Ok, je garde ma stratégie,
> et je dis un nombre fixé à l'avance". Direct, je dis 5. Si je suis le seul à pas avoir
> 5, c'est pas grave, logiquement les autres auront la présence d'esprit de dire 5 en voyant
> 98 numéros 5.

Justement, tu devrais garder ton nombre - et faire confiance aux autres prisonniers pour suivre la stratégie, ce qui va garantir que l'un des prisonnier va dire "5" dans le cas où le nombre que tu dois annoncer n'est pas celui que tu as.

Mais ta méthode peut peut-être se développer en une méthode qui a une bonne chance de succès et est simple à mettre en oeuvre - mais elle ne peut pas être développer en une stratégie qui gagne à tous les coups.

Le problème, à peu de prisonnier :

* à 4 prisonnier : si tu vois (2, 1, 1), alors il faut que tu réponde ton nombre ; parce que, si tu as toi aussi un "2" sur le front et que tout le monde répond le nombre qu'il voit le plus, alors tout le monde perd (ceux qui ont un 1 répondent "2", ceux qui ont un 2 répondent "1".

Si tu vois (1, 1, 1) et que tu est sensé répondre "2" : supposons que tu aies effectivement un 2 sur le front, alors les autres voient (2, 1, 1) - ils sont dans la situation juste au-dessus avant où ils ne faut surtout pas qu'ils répondent autre chose que leur nombre. Et dans ce cas ils perdent tous (puisque dans cette configuration c'est toi le seul gagnant). Il faut que tu répondes "2" pour garantir la victoire si tu as un 2 sur le front - et tu dois faire confiance aux autres pour appliquer la stratégie et gagner si tu as un 1 ou autre chose.

* A 5 prisonnier : si tu vois (1, 1, 2, 2), tu réponds quoi ? Mettons que tu vois (1, 1, 2, 3) ; si tu as un "2" sur le front, tu perds en répondant le nombre que tu vois le plus (ainsi que tous ceux qui le font), le dernier joueur voit (2, 1, 1, 2) et se plante qu'il réponde 1 ou 2. Il te faut donc suivre la stratégie.

Si tu vois (1, 1, 1, 2), que tu es sensé répondre "3" ; mettons que tu aies effectivement un 3, alors les autres sont dans la situation précédente où ils voient (1, 1, 2, 3) (et (1, 1, 1, 3)), en gros la même config que toi), situation où ils doivent suivre la stratégie, stratégie qui les fait perdre - puisque dans cette configuration c'est toi le seul gagnant.

Si tu vois (1, 1, 1, 1) et que tu es sensé répondre "2" ; mettons que tu aies effectivement un 2, les autres voient (1, 1, 1, 2) et sont dans la situation précédente où ils doivent répondre leur nombre, ce qui les fait perdre.


... Enfin je pense que tu vois le problème et comment ça se généralise en augmentant le nombre de prisonniers : il n'y a aucun moment où tu peut switcher de la stratégie gagnante à la stratégie "annoncer un nombre très présent" tout en préservant un 100 % de victoire.

En fait, quand j'y réfléchi, je me dis que partir de "si on ne voit que des X, alors on répond X" est la base pour concevoir une stratégie qui minimise les chance de victoire - parce que pour minimiser les chances de victoire il faut faire en sorte qu'un maximum de personne gagnent en même temps.

On a 25 chevaux, on veut trouver les 3 meilleurs. On ne peut organiser que des courses avec 5 chevaux à la fois, et les résultats ne sont pas comparables d'une course à l'autre. Combien de courses doit-on organiser ?

Ca veut dire quoi que les résultats ne sont pas comparables d'une course à l'autre?

Genre si Cheval 1 bat Cheval 2 dans la première course, et que Cheval 2 bat Cheval 3 dans une seconde course, ça ne veut pas dire que Cheval 1 battra Cheval 3 dans une troisième course?
Et si les trois chevaux courent ensemble, ça ne fait pas nécessairement 1>2>3?

Si c'est le cas, c'est juste du dénombrement (puisqu'il n'y pas de consistance, tu dois faire toutes les courses possibles), et c'est pas très rigolo

Liz Euse a écrit :

> Ca veut dire quoi que les résultats ne sont pas comparables d'une course à l'autre?

Ça veut dire qu'on ne peut pas faire courir 1 à 5 puis 6 à 10 et comparer les temps de 5 et 6 (par exemple).

> Genre si Cheval 1 bat Cheval 2 dans la première course, et que Cheval 2 bat Cheval 3 dans une
> seconde course, ça ne veut pas dire que Cheval 1 battra Cheval 3 dans une troisième course?

Si si.

> Si c'est le cas, c'est juste du dénombrement

Même pas. Si ç'avait été le cas, ça aurait voulu dire que « les trois meilleurs » n'est pas une notion bien définie.

So Alive a écrit :

> On a 25 chevaux, on veut trouver les 3 meilleurs. On ne peut organiser que des courses avec
> 5 chevaux à la fois, et les résultats ne sont pas comparables d'une course à l'autre. Combien
> de courses doit-on organiser ?



Je sais pas mais en ce moment les tiercé dans les pmu sont des rediffusion... ce qui permet de résoudre l'enigme du tiercé gagnant... avec un peu de mémoire...

So Alive a écrit :

> On a 25 chevaux, on veut trouver les 3 meilleurs. On ne peut organiser que des courses avec
> 5 chevaux à la fois, et les résultats ne sont pas comparables d'une course à l'autre. Combien
> de courses doit-on organiser ?

Je viens tenter une réponse au pif pour pas te laisser parler seul avec Artemise sur le mini chat, personne ne mérite ça ...
11 courses.

Tuxedo Mask a écrit :

> Je viens tenter une réponse au pif pour pas te laisser parler seul avec Artemise sur le mini
> chat, personne ne mérite ça ...

Merci !

> 11 courses.



Mais on peut faire mieux

So Alive a écrit :

> Mais on peut faire mieux

9 ?

Tuxedo Mask a écrit :

>> Mais on peut faire mieux

So Alive a écrit :

7 ...
Merci pour l'énigme, c'était bien fun au final. Je pensais qu'il n'y avais pas besoin de réfléchir mais en poussant un peu, on passe quand même de 11 à 7 !

Tu t'approches, mais ce n'est pas encore bon. Si les trois meilleurs sont A B et C ta méthode ne le voit pas.

Et comme ça ?

Draziel a écrit :

> Et c'est là que je réalise que la question est "les 3 meilleurs" et pas "les
> 3 meilleurs dans l'ordre" :p (si c'est ça, je n'ai pas de solution)

Mais si, en y réfléchissant 2 min de plus, tu verras que tu connais l'ordre ! Bravo !

So Alive a écrit :

> Mais si, en y réfléchissant 2 min de plus, tu verras que tu connais l'ordre ! Bravo !

Effectivement, A est premier, j'étais fatigué au moment où j'ai écris tout ça c'est évident pourtant :D merci !

Jeu à deux prisonniers : on leur donne une grille avec n cases, et une pièce sur chaque case. Chaque pièce peut être sur le côté pile ou le côté face sans distinction.

Sous la grille, une des cases contient une clé. Le prisonnier A sait quelle est cette case, le prisonnier B doit le deviner. Pour l'aide, le prisonnier A doit retourner exactement une pièce, puis le prisonnier B, en voyant le plateau doit deviner où est la clé. Question 1 : est-ce possible ? Question 2 : si oui, comment ?

Uncurieux a écrit :

Jeu à deux prisonniers : on leur donne une grille avec n cases, et une pièce sur chaque case. Chaque pièce peut être sur le côté pile ou le côté face sans distinction.

Sous la grille, une des cases contient une clé. Le prisonnier A sait quelle est cette case, le prisonnier B doit le deviner. Pour l'aide, le prisonnier A doit retourner exactement une pièce, puis le prisonnier B, en voyant le plateau doit deviner où est la clé. Question 1 : est-ce possible ? Question 2 : si oui, comment ?

Le prisonnier B ne voit pas quelle pièce le prisonnier A a retourné? Il voit juste le plateau changé?
Il y a une concertation préalable?

J'ai du mal à voir l'enjeu de l'énigme, parce que je ne vois pas à quel moment un plan peut être établi.

Par exemple s'il y a concertation préalable et que le prisonnier B voit la pièce retournée, il suffit de dire avant "je retourne la pièce où se trouve la clé". Ou "Je retourne la pièce à droite de la clé" s'il est interdit de retourne la pièce avec la clé. C'est en tous cas complètement trivial.
S'il n'y a pas de concertation préalable, c'est du pifomètre.
S'il y a concertation préalable et que le prisonnier B ne voit pas la pièce retournée, il y a peut-être une astuce, mais je ne perçois pas comment le prisonnier B peut savoir quelle pièce a été retournée (puisqu'a priori le plateau est aléatoire).

Liz Euse a écrit :

> 1/ Le prisonnier B ne voit pas quelle pièce le prisonnier A a retourné? 2/ Il voit juste le plateau changé? 3/ Il y a une concertation préalable?

1 Non
2 Oui
3 Oui

> S'il y a concertation préalable et que le prisonnier B ne voit pas la pièce retournée, il y
> a peut-être une astuce, mais je ne perçois pas comment le prisonnier B peut savoir quelle pièce
> a été retournée (puisqu'a priori le plateau est aléatoire).

Tu peux essayer d'y réfléchir avec deux cases, pour commencer. Malheureusement, ça ne se généralise pas facilement ensuite, mais tu devrais assez facilement établir que c'est faisable avec deux cases.

Avec deux cases c'est évident, mais c'est dû au fait que tu changes n-1 cases.
Si tu pouvais changer deux cases sur trois (ou 99 sur 100) par exemple, tu aurais la même facilité, à mon avis.

Je suis pas certain que ce soit possible pour 3 cases. Il est impossible d'avoir un mappage unique.

Supposons que tu aies un plateau avec toutes les pièces côté pile :
P P P
Tu peux obtenir trois plateaux différents :

P P F
P F P
F P P

Tu vas les attribuer à une issue différente.

P P F veut dire que c'est la case 1 qui a la clé
P F P veut dire que c'est la case 2 qui a la clé
F P P veut dire que c'est la case 3 qui a la clé

Notons que c'est complètement arbitraire.

Si le plateau est originellement :
F P F
On peut obtenir trois plateaux différents :
F P P (= case 3 a la clé)
F F F
P P F (= case 1 a la clé)

On en déduit que F F F doit représenter "Case 2 a la clé".

Si le plateau est originellement :
F F P

On peut obtenir trois plateaux différents :
F P P (= case 3 a la clé)
P F P (= case 2 a la clé)
F F F

On en déduit que F F F doit représenter "Case 1 a la clé".


Du coup, on note que F F F est ambigu et peut représenter deux choses différentes.

Il est donc nécessaire de pouvoir déterminer quelle pièce a été retournée pour savoir de quel "F F F" il s'agit.
Or, si on est capable de déterminer quelle pièce a été retournée, on en revient au fait qu'il suffit de retourner la pièce sous laquelle la clé se cache.


Toutefois, il est impossible de savoir, en regardant un plateau donné, quelle pièce a été retournée. Il s'agit donc d'une énigme où il y a une astuce rigolotte, mais tordue et pas très intéressante (du genre "Toutes les autres pièces sont parfaitement centrées sauf celle que tu retournes que tu mets tout à droite de la case, HA!").
Ou alors, le n doit être >3. Mais je suis convaincu qu'un argument similaire à celui que j'ai établi peut être construit pour d'autres n. Il y a probablement une histoire de dénombrement astucieux qui montre qu'il y a toujours par nécessité des ambiguités.

Liz Euse a écrit :

Ton analyse pour 2 et 3 cases est tout à fait correcte, bravo ! Effectivement c'est impossible avec 3 cases, et tu le démontres bien !

> Toutefois, il est impossible de savoir, en regardant un plateau donné, quelle pièce a été retournée.

Non, mais ce n'est pas l'objectif ! L'objectif n'est pas de trouver quelle pièce a été retournée, mais quelle case contient la clé. Tu notes qu'avec 2 cases non plus, on ne sait pas quelle pièce a été retournée, et ce n'est pas un problème.

> Il s'agit donc d'une énigme où il y a une astuce rigolotte, mais tordue et pas très intéressante
> (du genre "Toutes les autres pièces sont parfaitement centrées sauf celle que tu retournes
> que tu mets tout à droite de la case, HA!").

Oh, ce serait grossier de ma part. Si tu cherches dans mes enigmes précédentes (que j'ai postées sous le pseudo So Alive), tu verras que je n'utilise jamais ce genre d'astuces.

> Ou alors, le n doit être >3. Mais je suis convaincu qu'un argument similaire à celui que
> j'ai établi peut être construit pour d'autres n. Il y a probablement une histoire de dénombrement
> astucieux qui montre qu'il y a toujours par nécessité des ambiguités.

En fait, il y a des 'n' pour lesquels ça marche, et des 'n' pour lesquels ça ne marche pas (jusque là, je ne t'apprends rien, tu sais que 2 et 3 sont des exemples). Sans donner la solution, je rajoute qu'il existe une infinité de n dans les deux catégories, et il y a un critère simple pour savoir si un n est dans l'une ou l'autre. On peut dériver de ta démonstration une démonstration pour tous les cas impossibles, mais je préfère te laisser chercher encore un peu si tu veux bien, tu as déjà beaucoup avancé ! Si tu bloques, dis-le moi et je rédigerai un bout de piste (et sinon, au plaisir de te lire !).

Petite indication : imaginons qu'il y a 4 cases qu'on va astucieusement baptiser 00, 01, 10 et 11. On peut faire des remarques intéressantes sur le XOR des cases pour lesquelles la pièce est sur le côté pile.

Je suis curieux de voir la résolution de cette énigme si quelqu'un y parvient, ça m'apprendra des choses, car là même avec l'indice je ne sais même pas comment commencer !

Draziel a écrit :

Rappel :
Situation initiale : Plateau avec des pièces mises n'importe comment, et une case contient une clé.
Joueur 1 : Retourne exactement une pièce
Joueur 2 : Arrive, regarde le plateau et devine où se situe la clé.

L'indication que je donnais, c'est ce que doit faire le joueur 2 (en voyant le plateau, il fait un calcul de XOR et en déduit où se situe la clé). Ce qu'il faut montrer, c'est que cette fonction permet effectivement de gagner à tous les coups, autrement dit que quelque soit la situation intiale, le joueur 1 peut, en retournant une pièce, se débrouiller pour que joueur 2 trouve la clé. On dira qu'un plateau "désigne" la case obtenue par XOR des cases avec des pièces à pile.

Voilà un exemple pour aider à comprendre comment ça marche :


Reste à déterminer comment ça peut se généraliser pour d'autres valeurs que 4, puis à montrer qu'il n'y a pas de solution dans les autres cas !

Je n'ai clairement pas le niveau :D

Draziel a écrit :

> Je ne comprend pas comment le XOR permet de désigner une case, par exemple quand tu
> dis "Par exemple, si le plateau est P, F, P, P, Joueur 1 calcule le XOR de 00, 10, et
> 11, et en déduit que le plateau "désigne" la case 01." ce que je vois c'est
> que XOR de 00=0, XOR de 10=1, XOR de 11=0...

Ah, j'ai utilisé un raccourci : quand on parle de faire du XOR de nombres à plusieurs bits, on fait généralement du XOR bit-à-bit : autrement dit un XOR de tous les premiers bits ensemble, puis un XOR de tous les deuxièmes bits ensemble.

Avec 00, 10 et 11, cela donne (0 ⊕ 1 ⊕ 1 = 0), (0 ⊕ 0 ⊕ 1 = 1) donc 01.

Le XOR-bit-à-bit entre deux nombres à plusieurs bits (que je note aussi ⊕) conserve les propriétés intéressantes du XOR, par exemple, si A et B sont deux nombres en binaire : A ⊕ B ⊕ B = A

Or justement, dans cette situation, si le plateau désigne A, tu voudrais qu'il désigne B. Il suffit alors de voir que A ⊕ (A⊕B) = B (autrement dit, en retournant la pièce (A⊕B) d'un plateau qui désigne A, le plateau va désigner B).

Merci des éclaircissements ! Effectivement je comprend beaucoup mieux comme ça !

Uncurieux a écrit :


il me semble que la méthode se généralise à tous les entiers qui sont une puissance de 2 : on numérote les case en binaire, le XOR des case avec un Pile fait un certain nombre, et on est capable de changer n'importe quel digit de ce XOR en changeant de sens la pièce de la case désignée par ces digits (plus précisément, la case qui a des 1 sur ces digit et des 0 sur les autres). Pouvant changer n'importe quelles digits, on peut désigner n'importe quelle case du plateau avec un seul changement de sens, pour toute les positions initiales.

une peu de formalisme pour ceux qui tenteraient de continuer le problème (personnellement j'abandonne) :

1/ ce que voit le second joueur, c'est un plateau dans un certain état ; il n'a pas d'autres informations (il ne sait pas l'état initial, quelle pièce a été retournée etc). A partir de cet état, il doit choisir une case. L'enjeu est donc de créer une fonction f prenant en argument un état du plateau X et renvoyant une case.

Un état du plateau est un élément de {F,P}^n (une suite de n P et F). Il contient 2^n élément.

On a n cases, qu'on peut par exemple numéroter de 0 à n-1 (pour rester raccord avec l'exemple à 4 cases, où les cases sont numérotées de 0 à 3, et leur nombre noté en binaire).

On veut donc créer une fonction f: {F,P}^n -> les entiers de 0 à n-1.


2/ évidemment ce n'est pas la seule contrainte pour f. On a, par ailleurs, n mouvements élémentaire qu'on peut noter m0, m1,... m_(n-1), m_i consistant à retourner la pièce de la case i. Pour un état donné du plateau noté X, on peut noter X+m_i l'état du plateau après avoir effectué le mouvement m_i.

Par exemple, si X = FFF, X+m2 = FPF, X+m2+m1 = PPF, X+m2+m1+m2 = PFF, etc.

L'ordre des mouvements n'importe pas (c'est pour ça que j'ai utilisé la notation "+" : X+m1+m2 = X+m2+m1). Faire deux fois le même mouvement revient à la position initiale (X+m1+m1=X).

le premier joueur voit le plateau dans un état X quelconque, et doit pouvoir désigner n'importe quelle case avec un unique mouvement. En d'autres termes, pour tout X fixé, la fonction qui a un mouvement m associe la case f(X+m) doit être surjective. Puisque par ailleurs, on a autant de mouvements que de cases, il faut que cette fonction soit bijective.

On peut noter f_X la fonction qui, à un mouvement m donné, associe f(X+m). La contrainte s'écrit alors pour pouvoir résoudre le problème :
pour toute position X, f_X définie par f_X(m) = f(X+m) est une bijection de l'ensemble des mouvements vers l'ensemble des cases.


3/ De ceci, on peut facilement établir que deux état du plateau séparés de deux mouvements désignent forcément une case différente par f. En effet, les état X+mi+mj et X sont a un mouvement de X+mi, et f_(X+mi) étant injective, f(X) = f_(X+mi)(mi) est différent de f(X+mi+mj)=f_(x+mi)(mj).


3a/ de là on déduit rapidement que le problème n'a pas de solution pour n=3. En effet, si f est une telle solution et X est un état, alors f(X+m1+m2+m3) doit être différent de f(X+m1), f(X+m2) et f(X+m3) ; mais f_x étant surjective, f(X+m1), f(X+m2) et f(X+m3) désignent les 3 cases du plateau. f(X+m1+m2+m3) ne peut donc désigner aucune case.


... Et de là je bloque. on peut montrer que le système n'a pas de solution pour n=5 et n=6 (en vrai ça ne demande pas de creuser loin dans la combinatoire), de là je conjecture qu'il n'y a de solution que si n est une puissance de 2, mais j'arrive pas à trouver de méthode qui se généralise.

Gonzo a écrit :

Wow, c'est impressionnant ! Merci d'avoir pris le temps de rédiger tes recherches !

Donc déjà, pour n puissance de 2, tu as parfaitement raison, la généralisation se fait bien.

Pour les autres cas, voici le petit truc qui te manquait, et je précise un peu le vocabulaire : on parle en fait d'un graphe : chaque sommet est un plateau, deux sommets sont reliés si on peut passer d'un à l'autre avec exactement un déplacement, et l'objectif est donc de faire en sorte que chaque sommet ait un voisin associé à n'importe quelle case du plateau.

Or un sommet a toujours exactement n voisins. Un sommet associé à 1 permet donc de couvrir exactement n sommets (il permet à n sommets d'avoir un voisin associé à 1, quoi). Il faut donc 2^n / n sommets associé à 1 pour tous les couvrir, au moins. De même, il faut 2^n / n sommets associés à 2, etc. Et le seul moyen d'avoir ça, c'est que 2^n soit divisible par n, ce qui arrive très exactement si n est une puissance de 2.

(en espérant que ce soit clair)

Uncurieux a écrit :

> (en espérant que ce soit clair)

Oui ça l'est.

Pour ceux qui préfèrent une démonstration uniquement en combinatoire, sans graphe (c'est exactement la même démo, c'est juste les outils qui changent) :

Déjà en reprenant les notations que j'ai introduite, on considère qu'il existe une fonction f résolvant le problème. On va noter E l'ensemble de toutes les positons du plateau (il a 2^n éléments), et E_i = {Y | f(Y) = i}. On va montrer que le cardinal de E_i est exactement 2^n/n (ce qui prouvera que 2^n/n est entier : un cardinal est toujours entier).

On choisit un i. pour n'importe quel Y dans E_i, {X | X est à un mouvement de Y} a pour cardinal n (on a n mouvements, qui mènent à les position différentes). Par ailleurs, la réunion suivante :
U_(Y élément de E_i) {X | X est à un mouvement de Y}
est égale à E : toute position est à un mouvement d'une position renvoyant i. Le cardinal d'un union est inférieur à la somme des cardinaux :
somme_(Y élément de E_i) card {X | X est à un mouvement de Y} >= 2^n
et somme_(Y élément de E_i) card {X | X est à un mouvement de Y} = somme_(Y élément de E_i) n = n * card E_i
L'on en ressort n * card E_i >= 2^n, soit card E_i >= 2^n/n.

Par ailleurs, U_i E_i = E, et il s'agit d'une union disjointe ; le cardinal de E est donc exactement la somme des cardinaus des E_i :
2^n = somme_(i entre 0 et n-1) card E_i >= somme_(i entre 0 et n-1) 2^n/n = n* 2^n/n = 2^n
Le seul cas d'égalité possible dans la précédente inégalité correspond au cas où chaque card E_i vaut exactement 2^n/n.

On a donc établi que 2^n/n est entier. La fin est de l'arithmétique de base : les seuls diviseurs de 2^n sont les puissance de 2.

Bien que vraiment pas fan de problèmes d'échec, en voilà un mignon :

« Blanc joue et ne gagne pas immédiatement. »



Indication :

Uncurieux a écrit :

1/ le roi noir ne peut pas bouger : sur les 6 cases libres il se fait manger par un pion (qui ne peuvent pas bouger et seront donc à la même place à la fin du tour blanc), et s'il mange le pion au-dessous de lui il est mangé par un cavaliers (qui sont deux, l'un des deux sera donc toujours là à la fin du tour blanc).

1a/ cela signifie donc que si blanc met noir en échec, c'est forcément un mat et la partie est finie.

2/ listions les mouvement blancs possibles :
2a/ les cavaliers, dont le seul mouvement possible mets noir en échec.
2b/ le fou en haut à gauche, dont le seul mouvement possible (manger la tour) met noir en échec.
2c/ le fou et la tour en haut à droite ne peuvent pas bouger.
2d/ la tour un peu moins en haut, si elle bouge, libère le fou qui met noir en échec.
2e/ il ne reste donc que le roi.

3/ le roi blanc ne peut pas descendre (la tour noire le mettrait en échec), tout ce qu'il peut faire est d'aller à gauche.

Gonzo a écrit :

3/ le roi blanc ne peut pas descendre (la tour noire le mettrait en échec), tout ce qu'il peut faire est d'aller à gauche.

Non, il y a le fou qui met aussi le Roi blanc en échec.

Gonzo a écrit :

> 1a/ cela signifie donc que si blanc met noir en échec, c'est forcément un mat et la partie
> est finie.

Non, c'est faux, il y a une autre condition nécessaire pour que l'échec soit mat.

Uncurieux a écrit :

> Non, c'est faux, il y a une autre condition nécessaire pour que l'échec soit mat.

Oui, effectivement, Liz Euse a répondu juste au=sn autre côté, comme la tour a plusieurs mouvement possible, la solution n'est pas unique...

La solution est bien unique, comme je l'avais dit dans ma première indication. Regarde mieux

C'est ça qui rend la solution unique, Gonzo.

j'ai trouvé cette vidéo, elle semble décrire une énigme donnée récemment (pas la dernière) https://www.youtube.com/watch?v=wTJI_WuZSwE ^^

Draziel a écrit :

> j'ai trouvé cette vidéo, elle semble décrire une énigme donnée récemment (pas la dernière)
> https://www.youtube.com/watch?v=wTJI_WuZSwE ^^

Oui, c'est ça qui m'a rappelé cette énigme. Je l'avais découverte en thèse, on avait joué avec un camarade à faire ça avec 8 pièces, ça marchait pas mal.

On sonne chez des ami.e.s, dont on sait qu'ils/elles ont deux enfants. C'est une fille qui ouvre la porte. Quelle est la probabilité que l'autre enfant soit une fille ?

Uncurieux a écrit :

Quelle est la probabilité que l'autre enfant soit une fille ?

En supposant une binarité du genre, et une équirépartition des genres, une chance sur 3.
Foutus gobelins.

Liz Euse a écrit :

> En supposant une binarité du genre, et une équirépartition des genres, une chance sur 3.

En supposant une binarité du genre, une équirépartition des genres, la réponse n'est pas 1/3

Edit: question annexe : si la réponse était 1/3, que pourrait-on en conclure ?

Je suis circonspect.
Je doute que la réponse soit 1/2. Ce serait difficilement une énigme mais bon moi j'ai cherché compliqué alors ça peut marcher comme attrape-nigauds.

Si on a deux enfants, on a :
1/4 que ce soit deux garçons
1/2 que ce soit un garçon et une fille
1/4 que ce soit deux filles

Si on sait que l'un d'eux est une fille, on exclut automatiquement la première option.
Il reste trois alternatives, deux d'entre elles sont garçon+fille et la dernière est fille+fille.

D'où le 1/3.

Mais bon, j'admets bien volontiers que j'ai jamais été bon en probabilité.

Liz Euse a écrit :

En fait, la réponse est bien 1/2, et il y a une erreur dans ton raisonnement. Mais la raison pour laquelle je pose la question, c'est qu'on voit très souvent ce raisonnement erroné (y compris de la part de collègues profs de maths). Et accessoirement, ça a créé un peu de drama pendant notre repas de Noël familial.

Le début est juste : il y a 4 situations équiprobables : FF, FG, GF, et GG. Mais ensuite, tu ne sais pas uniquement qu'il y a au moins une fille. Tu sais que c'est une fille qui t'ouvre la porte. On peut donc prolonger la situation :

FF => si un enfant ouvre, c'est forcément une fille.
FG => une chance sur deux que ce soit une fille ou un garçon qui ouvre
GF => idem
GG => forcément un garçon

Autrement dit, si on note FO (une fille ouvre la porte) et GO (un garçon ouvre la porte), l'arbre ressemble à :

FF [1/4] 
 => FO [1]
FG [1/4]
 => FO [1/2]
 => GO [1/2]
GF [1/4]
 => FO [1/2]
 => GO [1/2]
GG [1/4]
 => GO [1]

Au final, la probabilité qu'une fille ouvre est de 1/2, et la probabilité de FF sachant FO est de 1/2 (25% / 50%).

Note que si on suppose que c'est toujours l'aîné qui ouvre, la proba reste 1/2 avec l'arbre :

FF [1/4] 
 => FO [1]
FG [1/4]
 => FO [1]
GF [1/4]
 => GO [1]
GG [1/4]
 => GO [1]

On atteint une proba 1/3 si on suppose que dans une famille fille/garçon, c'est forcément une fille qui ouvre la porte. Ou si on sait seulement que la personne a une fille sans rien qui permette de la distinguer (ici, ce qui la distingue, c'est d'ouvrir la porte).

De manière amusante, on peut créer des distinctions partielles. Ainsi, si l'énoncé était "la personne a une fille née dans la première moitié de l'année, quelle est la proba que l'autre enfant soit une fille ?", alors la réponse n'est ni 1/2 ni 1/3.


Et c'est là que les gobelins reviennent parce que :
=> la proba que l'autre enfant soit une fille sachant qu'on a une fille née au premier semestre est de 3/7
=> la proba que l'autre enfant soit une fille sachant qu'on a une fille née au deuxième semestre est de 3/7
=> Mais la proba que l'autre enfant soit une fille sachant qu'on a une fille dont on ne connait pas le semestre de naissance est de 1/3

En exercice : en supposant équirépartition des jours de naissance, calculer la proba que l'autre enfant soit une fille sachant qu'on a une fille née un mercredi.

Uncurieux a écrit :

(y compris de la part de collègues profs de maths).

J'avais bien le bon arbre au début. Mais j'étais convaincu que le raisonnement n'était pas bon, parce que 1/2 est la réponse évidente, et que normalement une énigme piège le néophyte .


De tête, j'obtiens 13/27 pour l'exercice. Plus on donne une information précise sur une variable, plus l'indépendance des deux variables se voient, et plus on tend vers 1/2?

Liz Euse a écrit :

> De tête, j'obtiens 13/27 pour l'exercice.

Yes [6E§+]

> Plus on donne une information précise sur une variable,
> plus l'indépendance des deux variables se voient, et plus on tend vers 1/2?

Ma vision intuitive des choses, c'est que plus tu donnes des infos sur la variable, et plus tu réduis la possibilité que tu sois en train de parler des deux à la fois. Si tu regardes le calcul, la proba d'avoir une fille qui est née un mercredi quand il y a deux filles, c'est Proba(1 fille née un mercredi) + Proba(1 fille née un mercredi) - Proba(2 nées un mercredi) = 1/7+1/7-1/49 = 13/49. Sans le dernier terme, tu retomberais pile sur une proba finale de 1/2. 'fin bon, je trouve ça rigolo, quoi, merci d'avoir cherché (et t'es pas néophyte du tout, te laisse pas faire !)

Question subsidiaire : tu es à la kermesse du lycée de tes enfants, et tu sais qu'un autre parent d'élève a deux enfants, tous les deux dans ce lycée. A un moment tu vas aux chiottes, et les chiottes des hommes et des femmes sont évidemment séparée. Et donc, dans les chiottes, tu croises l'un des enfants de cet autre parent d'élève (que tu reconnais parce qu'il a exactement la même tronche que ses parents) ; cet enfant est donc du même sexe que toi (si tu es un homme, tu es allé dans les chiottes des hommes, et donc tu n'as pu y croiser qu'un garçon).

Quelle est la probabilité que l'autre enfant soit du même sexe ?

Indice : ici on a P(avoir croisé un enfant de l'autre sexe dans les chiottes) = 0.


Explication intuitive, sans gobelin des maths : c'est quand même un sacré hasard d'avoir croisé un des enfants de ce parent d'élève aux chiottes. D'un autre côté, s'il a deux enfants du même sexe, y avait deux fois plus de chance que ce hasard "inouï" arrive que s'il a deux enfants de sexe différent.

En somme, si l'obtention de l'info repose sur un heureux hasard, alors cet heureux hasard avait plus de chance de se produire dans certaines configuration que dans d'autres. Il me semble qu'on peut construire des situations où P(deux enfants de sexe différents) approche 0, mais je sais plus comment et je sais plus le raisonnement qui permet de casser cette proba à 1/3 x) (a priori faut rendre le hasard d'obtention de l'info de plus en plus incroyable - genre obtenir par hasard que l'un des enfant est de même sexe et est né exactement le même jour que nous. Genre, être dans le club des hommes nés le 29 février - on pouvait pas y croiser la fille de notre ami, mais c'était quand même extrêmement improbable d'y rencontrer son fils).

A noter que la situation que j'ai décrit est plus réaliste que d'autres façons de poser le problème (qui en vrai rendent le problème mal posé) : le coup de "j'ai deux enfants, l'un d'eux est une fille née un mercredi", personne dit ça ; et si l'info est obtenue dans une conversation du style "j'ai deux enfants - OK, est-ce que tu peux me dire le sexe et le jour de naissance de l'un d'eux ? - Oui, j'ai une fille née un mercredi", alors le jour de naissance n'ajoute strictement aucune info, et la proba que l'autre soit une fille reste à 1/2 (dit autrement, le type avait une fille née un mercredi et un garçon né un mardi, il avait une chance sur deux de choisir chacun, pareil pour chaque sexe et chaque jour de naissance... Faites votre arbre avec les 4*7*7 possibilités si ça vous chante, le raisonnement intuitif est ici bien plus efficient) : il faut que l'info supplémentaire soit obtenue par hasard aussi pour que les probabilités se décalent (elles se décalent par le fait que ce hasard est moins incroyable si le type a deux enfants de même sexe), ce qui rend la façon habituelle de poser ce problème mal posée (1/2 reste généralement une réponse valable, selon la façon dont on interprète comment l'info a été obtenue).

En passant, pour le "gobelin des maths" du monthy hall (les trois porte avec les chèvres et la voiture) : 1/2 de gagner et 2/3 de gagner en changeant de porte sont deux réponses valable pour beaucoup de façon de poser le problème. Il existe des façon de poser le problème forçant la réponse à 2/3 ; mais tant qu'on ne précise pas explicitement que le présentateur sait où se trouve la voiture et ouvre systématiquement une porte avec une chèvre, alors l'interprétation "le présentateur ouvre une porte au hasard, et dans le cas donné dans le problème c'était par hasard une chèvre derrière" est valable, et met la proba de gagner en changeant de porte à 1/2 (parce qu'il faut prendre en compte dans l'arbre de proba les cas où le présentateur ouvre une porte avec la voiture derrière).

C'est dans le cas où le présentateur connaît la bonne porte et ouvre exprès une mauvaise qu'on gagne une info donnée par le présentateur, et c'est cette info qui décale la proba.


Bref : rien de magique ni de gobelins des maths. Juste des questions d'infos supplémentaire et, souvent, de problèmes mal posés avec des gens qui assurent malgré tout qu'il n'y a qu'une seule réponse. Dans les problème de ce genre, pour comprendre la "magie", essayez de comprendre à quel moment on a gagné une info (connaissance du présentateur dans le Monthy Hall, hasard d'obtenir l'info dans les deux enfants, autre dans d'autres problèmes).


Et edit au post précédent : en fait je suis vraiment pas sûr qu'on puisse faire chuter la proba de "deux enfants de sexe différents" à zéro... Je sais plus T_T .

Gonzo a écrit :

Bref : rien de magique ni de gobelins des maths.

Non?

le raisonnement intuitif est ici bien plus efficient

C'est-à-dire?

Quelle est selon toi la réponse à donner, et en quoi est-elle plus efficiente?

Déjà j'ai l'impression que je me suis planté : quelle que soit la façon dont on a obtenu l'info sur le sexe du premier enfant, la proba que l'autre soit du même sexe est toujours entre 1/3 et 1/2.

En gros : vous faites un sondage "pensez à un couple d'amis qui ont deux enfants, dont une fille. L'autre enfant est-il une fille ?", vous êtes sensé obtenir 1/3 de réponses positive. Vous faites un sondage "pensez à une fille, qui a soit un frère soit une soeur. Est-ce qu'elle a une soeur ?", vous êtes sensé obtenir 1/2 de réponses positives. Sauf que ni dans un cas, ni dans l'autre, vous n'obtiendrez le résultat escompté (ne serait-ce que parce que certaines personnes vont répondre à l'autre question : il y a de très fortes chance que si vous posiez la première question à quelqu'un de 12 ans, il commence par penser à une de ses camarade de classe qui a un frère ou soeur, puis passe à ses parents en tant que le couple qui répond à la question, et réponde ainsi à la seconde question. Inversement, chez les gens plus âgés, certains vont répondre à la première question au lieu de la seconde...). Hourrah pour les proba qui ne représentent rien ! o/ Et c'est justement incroyablement difficile de faire un problème bien posé sur des probas qui ne représentent rien, mais qu'on veut quand même poser en terme humains (et pas juste sous la forme "on a 4 événements équiprobables, et leur proba sachant un autre événement est...")

Bref, en gros on a besoin de pF la proba que l'événement montrant que le pote a une fille se réalise, pG pareil pour un garçon, et pFF (la proba qu'il se réalise avec deux filles) et pGG. Dans le cas des chiottes, on a pF = 0 (en imaginant que je soit un garçon, donc j'ai pu rencontrer qu'un garçon dans les chiottes), pGG (la proba de rencontrer les deux garçons dans les chiottes) = pG^2 (on peut estimer une indépendance).
ça donne :

P(il a deux garçons | j'ai rencontré un enfant de mon pote aux chiottes) =
= P(il a deux garçons et j'ai rencontré un enfant de mon pote aux chiottes)/P(j'ai rencontré un enfant de mon pote aux chiottes)
= P(j'ai rencontré un enfant de mon pote aux chiottes | il a deux garçons)*P(il a deux garçons)/P(j'ai rencontré un enfant de mon pote aux chiottes)
or:
$ P(j'ai rencontré un enfant de mon pote aux chiottes | il a deux garçons) = 2*pG - pGG
$ P(il a deux garçons) = 1/4

donc
P(il a deux garçons | j'ai rencontré un enfant de mon pote aux chiottes) = 1/4*(2*pG - pGG)/P(j'ai rencontré un enfant de mon pote aux chiottes)

et de la même façon :
P(il a un garçon et une fille | j'ai rencontré un enfant de mon pote aux chiottes) =
= 1/2*pG/P(j'ai rencontré un enfant de mon pote aux chiottes)

On pourrait croire qu'on est bloqué parce qu'on ne connait pas P(j'ai rencontré un enfant de mon pote aux chiottes), sauf qu'on s'en fout : on sait que la somme des deux probas fait 1, et leur division est désormais connue :
P(il a deux garçons | j'ai rencontré un enfant de mon pote aux chiottes)/P(il a un garçon et une fille | j'ai rencontré un enfant de mon pote aux chiottes) = 1 - 1/2*pGG/pG = 1-1/2*pG

Et on sait résoudre ce genre de système, si je me suis pas planté (et j'ai l'impression que si... ) ça donne un truc qui vaut 1/3 quand pG vaut 1 et qui approche 1/2 à mesure que pG approche 0 (en gros, si c'était sûr et certain que j'allais rencontrer un de leur fils s'ils en ont un, et que je l'ai effectivement rencontré, alors ils ont deux chance sur trois d'avoir une fille - je crois qu'elle est là, l'info gagnés : j'étais sûr de rencontrer leur fils s'ils en ont un).




Liz Euse a écrit :

>

le raisonnement intuitif est ici bien plus efficient

> C'est-à-dire?
>
> Quelle est selon toi la réponse à donner, et en quoi est-elle plus efficiente?

Bah justement, le problème est "comment ai-je appris qu'ils ont une fille née un mercredi, et est-ce que ça me donne une inf de façon plus ou moins indirecte ?"

Si le mec te dit "j'ai deux enfant. L'une est une fille née un mercredi", alors tu n'as aucune info : il a deux enfant, il en a choisit un pour te donner des infos dessus, ça ne donne pas d'info sur le second. Tu peux réfléchir en d'autres termes : je te dis ça, à ce stade je te propose de miser 2 euros, tu en gagnes 1.5 (et reprends ta mise) si mon deuxième enfant est un garçon, sinon je garde tes deux euros. Si tu estime ta proba de gagner à 2/3, alors tu devrais jouer (espérance de gain : 2/3*1.5 -2*3 >0) (parce que c'est sensé être ça, des probas dans un tel contexte : une façon de calculer ton gains si tu répètes ce jeu avec plein de gens) (et oui, c'est bien beau de faire des problèmes de proba en termes humains plutôt qu'en logique formelle, mais alors faudrait veiller à ce qu'on pense à les appliquer dans ce à quoi quoi elles servent quand on les exprime ainsi : évaluer des espérances de gains, entre autre). Est-ce que tu joues, ou est-ce que tu estimes que tu n'as aucune info sur le second enfant et que donc ta chance de gagner est 1/2 ?

A l'inverse, si j'apprend par hasard que tu as une fille et qu'elle vérifie un événement particulièrement improbable ("OK, juste une seule question : est-ce que tu as une fille né le 29 février ? - ça alors, oui !"), alors j'ai la sensation que cet événement improbable avait bien plus de chances de se réaliser si tu as deux filles plutôt qu'une fille et un garçon, et que je peux donc miser sur deux filles... Sauf que mes calculs ont pas l'air de montrer ça :/ . Mais bref, dans ce genre de cas, oui il y a une altération des probas, parce que le fait de découvrir un truc improbable par hasard (en gros, de réaliser un autre événement aléatoire) altère les probas.

Mais bref, le raisonnement intuitif commence par se demander "qu'est-ce que j'ai appris comme nouvelle info ?", et de ne se lancer dans les calculs que si on pense avoir une nouvelle info, ou a minima si on n'est pas sûr. Si la réponse est "aucune nouvelle info", on répond "1/2" sans calcul, jusqu'à ce que quelqu'un nous "montre" le contraire, auquel cas on y regarde sa démonstration (et soit on y trouve une erreur, soit on y trouve une hypothèse implicite qui permet d'ajouter effectivement de l'info, soit on y trouve l'info qu'on avait loupé - c'est exactement comme ça que fonctionne le Monthy Hall, en déroulant la démo on y trouve que le présentateur a révélé une info qu'il avait, et ensuite soit on se rend compte l'énoncé était clair, soit que c'est une hypothèse implicite prise dans la démo sans qu'elle soit dans la formulation. Et le problème des deux enfants, comme en général la façon dont a été trouvée l'info du jour de naissance ou autre n'est pas révélée dans l'énoncé, "1/2" est toujours une réponse valable : on peut partir du principe qu'on a juste quelqu'un qui a pris un de ses enfants au hasard pour donner des infos dessus, ça ne dit rien sur le second).

1-1/2*p
c'est manifestement entre 1/2 et 1 et, enfin, on se rappelle que la somme de ces deux nombre vaut 1.
1/2 < x/y = 1-1/2*p < 1
x+y = 1
1/2 < x/(1-x) < 1
1/2 - 1/2*x < x < 1 - x
1/2 - 1/2*x < x < 1 - x
3/2*x > 1/2
2*x < 1
1/3 < x < 1/2

flute j'ai laissé mon brouillon de calcul à la fin du post précédent x) .

Je ne souscris pas à la théorie "Selon comment l'information est obtenue, ça modifie le résultat théorique".
Outre le fait que de ton propre aveu les mathématiques ne semblent pas te soutenir, ça ne fait simplement pas sens. (Est-ce que le dialogue "-Donne-moi une information -J'ai une fille née un 29 Février donne fondamentalement moins d'information que -Est-ce que tu as une fille née le 29 Février? -Oui ? C'est franchement pas clair.)

Qu'on m'ait donné l'information ou que je l'ai devinée, je vérifie les mêmes événements aléatoires.

Sauf que ni dans un cas, ni dans l'autre, vous n'obtiendrez le résultat escompté

Tu as donné une raison ("l'énoncé peut être mal compris").
Mais cette raison me semble très douteuse. Il suffit de demander aux gens s'ils connaissent un couple ayant exactement deux enfants, et de demander la répartition des genres.
Puis de regarder combien ont deux filles divisés par combien ont au moins une fille (et d'ignorer ceux ayant répondu garçon-garçon)

Du coup l'excuse de "L'énoncé peut induire en erreur", elle s'en va.

Que reste-t-il? Pourquoi est-ce que NECESSAIREMENT on aurait pas 1/3 (Ok, pas "1/3", mais pourquoi on ne serait pas dans l'intervalle de fluctuation?)

Je suis certain que tu peux trouver moult problèmes de mise en action du sondage ("On a demandé à une seule personne" ou "Tout le monde a pensé à un même couple" ou encore "En réalité la répartition des enfants par sexe n'est pas 50/50"). Mais c'est évidemment pas ça que je demande.

Si le mec te dit "j'ai deux enfant. L'une est une fille née un mercredi"[...] Si tu estime ta proba de gagner à 2/3,

Non, j'estime ma proba de gagner à 14/27 en pariant sur un garçon. (cF messages plus haut)
Ce qui est sacrément proche de 1/2 et du coup mon espérance est négative.

Si on suppose que c'était 2€ de récompense, je passerai mon tour parce qu'il me faudrait beaucoup de temps (ne serait-ce que pour trouver des couples avec exactement deux enfants qui voudraient participer ) pour réussir à avoir des gains notables.




Je comprends que l'idée qu'une information a priori sans rapport puisse changer la probabilité est déconcertante.
Je te proposerai bien des gobelins comme explication, mais tu as nié leur existence avec force précédemment.

Liz Euse a écrit :

> Je ne souscris pas à la théorie "Selon comment l'information est obtenue, ça modifie le
> résultat théorique".
> Outre le fait que de ton propre aveu les mathématiques ne semblent pas te soutenir, ça ne fait
> simplement pas sens. (Est-ce que le dialogue "-Donne-moi une information -J'ai une
> fille née un 29 Février donne fondamentalement moins d'information que -Est-ce
> que tu as une fille née le 29 Février? -Oui ? C'est franchement pas clair.)
>
> Qu'on m'ait donné l'information ou que je l'ai devinée, je vérifie les mêmes événements aléatoires.

Non, elle est là l'erreur : le mec a deux enfants (c'est une donnée du problème), chacun d'eux a un sexe (/genre ?) et une date de naissance. Si le mec te livre l'info sur l'un... Bah il te livre l'info sur l'un. Et rien sur l'autre. Si tu veux faire ton arbre de proba, il faut que tu prennes en compte :
* les combinaison de 2^2 combinaisons de sexes (/genres ?) et de dates de naissance différents.
* et le choix fait pas l'interlocuteur : il te livre les info sur l'un ou sur l'autre.
Et tu déroule les calculs, et tu trouve : rien de spécial sur le second enfant, donc une chance sur deux pour chaque sexe.

En revanche, si tu découvres l'info par hasard, là on est dans le cas décrit par Un curieux :

Uncurieux a écrit :

> De manière amusante, on peut créer des distinctions partielles. Ainsi, si l'énoncé était "la
> personne a une fille née dans la première moitié de l'année, quelle est la proba que l'autre
> enfant soit une fille ?", alors la réponse n'est ni 1/2 ni 1/3.
>


Note qu'il n'a pas pris en compte, dans son arbre, la chance sur deux que l'interlocuteur ait parlé du premier enfant, et la chance sur deux qu'il ait parlé du second. En te livrant l'info, ton interlocuteur ne te délivre aucune info sur le second enfant et c'est le choix arbitraire (pas forcément "aléatoire", mais dans la modélisation on se contentera d'un événement aléatoire) qu'il a fait entre "livrer les infos sur le premier ou le second" qui ramène à 1 chance sur deux pour le second dans les calculs. En découvrant l'info d'une autre façon, d'un seul coup l'événement "avoir réalisé cet événement aléatoire" vient changer les calculs.

Sauf que ni dans un cas, ni dans l'autre, vous n'obtiendrez le résultat escompté

> Tu as donné une raison ("l'énoncé peut être mal compris").
> Mais cette raison me semble très douteuse. Il suffit de demander aux gens s'ils connaissent
> un couple ayant exactement deux enfants, et de demander la répartition des genres.
> Puis de regarder combien ont deux filles divisés par combien ont au moins une fille (et d'ignorer
> ceux ayant répondu garçon-garçon)
>
> Du coup l'excuse de "L'énoncé peut induire en erreur", elle s'en va.
>
> Que reste-t-il? Pourquoi est-ce que NECESSAIREMENT on aurait pas 1/3 (Ok, pas "1/3",
> mais pourquoi on ne serait pas dans l'intervalle de fluctuation?)

Parce que j'ai déjà vu l'expérience tentée, et ça donnait dans les faits un résultat entre 1/3 et 1/2.

Parce que quand on pose la question dans les faits, les gens ne réagissent pas nécessairement par filtrage (penser à un couple à deux enfant, éliminer et passer à un autre couple à deux enfants s'il n'y a pas de fille), et ce, quelle que soit la façon dont tu rédige la question, parce que les gens ne raisonnent pas de façon purement mathématiques (en fait la plupart des gens ne voient même pas la différence entre la première et la seconde question).

Ce que tu proposes, c'est de faire le filtrage toi-même en dépouillant le sondage, au lieu de le mettre dans la question. Et je suis d'accord : ça marche parce que ton formalisme mathématique devient très précis ; on est clairement face à un filtrage des parents (et non des enfants), donc 1/3 (oui, c'est 1/3 si tu filtre sur les parents, vu que tu ne gardes que les résultats FF, FG, GF, et 1/2 si tu filtre sur les enfants, puisque tu ne gardes que les résultat FF et FG - le premier enfant étant par définition celui qui a servi a faire le filtrage). Mais on n'est plus du tout dans le cas de la formulation "humaine" du problème, "un couple a deux enfants, l'un des deux est une fille, quelle est la proba que le second soit une fille ?" (qui lui est un problème mal posé). "Un couple a deux enfant, vous sonnez et c'est une fille qui ouvre" est plus ou moins bien posé (il faut mettre à 0 la proba que les deux enfants ouvrent ensemble, ce que je suis prêt à admettre dans le cas d'un problème de maths, mais qui n'est pas une situation impossible ; ça m'est déjà arrivé), mais c'est loin d'être le cas de "un couple a deux enfant, l'un des deux est une fille née le 29 février" (ou le premier semestre etc).


(et mon erreur, c'était de penser qu'on puisse dépasser les bornes 1/3 et 1/2, et je suis encore en train de me demander si j'ai pas une erreur dans mon analyse d'erreur :p . Mais certainement pas le fait qu'on puisse faire varier la proba entre 1/3 et 1/2 selon la façon dont l'info a été récupérée - et donc, selon l'interprétation de l'énoncé : ça c'est c'est ce que je trouve sans aucun problème par le calcul).