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.

___

Desproges disait que le jour de la mort de Brassens, il avait pleuré comme un gamin. Et bien moi, c'est étrange, mais le jour de la mort de Chirac, j'ai repris deux fois des moules.

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.

___

Desproges disait que le jour de la mort de Brassens, il avait pleuré comme un gamin. Et bien moi, c'est étrange, mais le jour de la mort de Chirac, j'ai repris deux fois des moules.

Gâterie a écrit :



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.

___

Desproges disait que le jour de la mort de Brassens, il avait pleuré comme un gamin. Et bien moi, c'est étrange, mais le jour de la mort de Chirac, j'ai repris deux fois des moules.

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.

___

Desproges disait que le jour de la mort de Brassens, il avait pleuré comme un gamin. Et bien moi, c'est étrange, mais le jour de la mort de Chirac, j'ai repris deux fois des moules.

(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 ?

___

Desproges disait que le jour de la mort de Brassens, il avait pleuré comme un gamin. Et bien moi, c'est étrange, mais le jour de la mort de Chirac, j'ai repris deux fois des moules.