Discussion:
Devinette
(trop ancien pour répondre)
Zarake
2017-05-30 10:24:09 UTC
Permalink
Raw Message
On dispose 20 cartes en une rangée sur une table, les figures contre la
table (seuls les dos sont visibles).

On retourne une des cartes dont le dos est visible, et également la
carte immédiatement à sa droite (que le dos ou la figure soit visible).

on répète ce processus.

Montrer que quelle que soit le choix des cartes retournées à chaque
tour, le processus se termine.
Jacques Mathon
2017-05-30 11:49:55 UTC
Permalink
Raw Message
Post by Zarake
On dispose 20 cartes en une rangée sur une table, les figures contre la
table (seuls les dos sont visibles).
On retourne une des cartes dont le dos est visible, et également la
carte immédiatement à sa droite (que le dos ou la figure soit visible).
on répète ce processus.
Montrer que quelle que soit le choix des cartes retournées à chaque
tour, le processus se termine.
Peut-être serait-il utile de "clarifier" la "règle" du jeu. ;)

En précisant que rangée signifierait deux extrémités...

Que se passe-t-il si on retourne la carte la plus à droite ?
Est-ce un coup autorisé ?
Si oui, ce coup se suffit-il à lui même ?
Faut-il retourner la carte la plus à gauche ?
Autre chose ?

Que signifie le processus se termine ?
On est "bloqué" (mais la carte de droite n'est pas retournée) ?
Toutes les cartes sont retournées ?
Autre chose ?

La possibilité que j'ai explorée (parmi celles évoquées explicitement
ci-dessus) permet de conclure. Il suffit d'expliciter la condition
d'arrêt pour montrer par récurrence (sur le nombre de carte avec
lesquelles il est encore possible de jouer) que le processus se termine.

Amicalement
--
Jacques
Zarake
2017-05-31 17:56:55 UTC
Permalink
Raw Message
Post by Jacques Mathon
Que se passe-t-il si on retourne la carte la plus à droite ?
Est-ce un coup autorisé ?
Non car il faut retourner 2 cartes,
- une qui n'a pas encore été retournée
- celle qui est à sa droite quel que soit sont état (retournée ou pas)

s''il n' y a pas de carte à droite, le coup n'est pas valable
Post by Jacques Mathon
Faut-il retourner la carte la plus à gauche ?
A la fin du processus les 20 cartes doivent être retournées
Post by Jacques Mathon
Que signifie le processus se termine ?
Toutes les cartes sont retournées

Mais attention, le pb est de montrer que quel que soit la carte choisie
à chaque tour (celle que l'on va retourner), le processus se termine.
Olivier Miakinen
2017-05-31 22:44:53 UTC
Permalink
Raw Message
Post by Zarake
On dispose 20 cartes en une rangée sur une table, les figures contre la
table (seuls les dos sont visibles).
On retourne une des cartes dont le dos est visible, et également la
carte immédiatement à sa droite (que le dos ou la figure soit visible).
on répète ce processus.
Montrer que quelle que soit le choix des cartes retournées à chaque
tour, le processus se termine.
Post by Jacques Mathon
Que se passe-t-il si on retourne la carte la plus à droite ?
Est-ce un coup autorisé ?
Non car il faut retourner 2 cartes,
- une qui n'a pas encore été retournée
- celle qui est à sa droite quel que soit sont état (retournée ou pas)
S'il n' y a pas de carte à droite, le coup n'est pas valable
Dans ce cas, voici ma réponse.

Soit D une carte dont on voit le dos et F une carte dont on voit la
figure.

Au début, la situation est :
DDDDDDDDDDDDDDDDDDDD

À chaque coup, deux cas sont possibles :
(1) soit on remplace un DD par un FF
(2) soit on remplace un DF par un FD

Le cas (1) diminue de deux le nombre de D. Quant au cas (2), il ne
change pas le nombre de D, mais c'est comme s'il déplaçait un D vers
la droite, en l'échangeant avec un F.

Il est clair qu'après avoir appliqué dix fois le cas (1), quel que
soit le nombre de fois où on aura fait (2), on sera dans la
situation :
FFFFFFFFFFFFFFFFFFFF

Or, tant qu'on ne fait pas (1) on est obligé de faire (2), ce qui
déplace un D vers la droite. Après un nombre fini de (2) sans faire
de (1), on finira obligatoirement par avoir tous les D le plus à
droite possible, ce qui nous obligera à faire un (1).

Inversement, tant qu'il reste des D et qu'on n'en a pas deux côte
à côte pour faire un (1), cela veut dire qu'on a au moins un DF
qui nous permet de faire un (2).

En conclusion, en partant de 20 cartes D, après dix coups (1)
éventuellement séparés par un certain nombre de coups (2), on se
retrouvera avec 20 cartes F et le processus devra alors se
terminer.

On peut bien sûr le généraliser : en partant de 2n cartes D on
finira avec 2n cartes F après n coups (1) et un nombre indéterminé
de coups (2) ; mais en partant de 2n+1 cartes D on finira avec 2n
cartes F suivies d'une seule carte D, là encore après n coups (1).
--
Olivier Miakinen
Zarake
2017-06-01 10:12:51 UTC
Permalink
Raw Message
Post by Olivier Miakinen
Soit D une carte dont on voit le dos et F une carte dont on voit la
figure ... [CUT]
Le mieux est d'affecter un "1" à une carte dont on voit le dos et un "0"
à une carte dont on voit la figure.

Alors au départ on a 20 "1" qui forment un nombre binaire (poids fort à
gauche) qui vaut 2^20 - 1 en décimal.

Il est facile de se convaincre que pour un état quelconque des 20
cartes à un moment donné, et quelque soit le coup suivant, on obtient
un nombre strictement inférieur au précédent. En conséquence, de quelque
façon qu'on choisisse les cartes à retourner, on a une suite de nombres
positifs strictement décroissante qui atteint donc 0, soit l'état ou
toutes les cartes sont retournées. CQFD
Olivier Miakinen
2017-06-01 12:49:33 UTC
Permalink
Raw Message
Post by Zarake
Le mieux est d'affecter un "1" à une carte dont on voit le dos et un "0"
à une carte dont on voit la figure.
Alors au départ on a 20 "1" qui forment un nombre binaire (poids fort à
gauche) qui vaut 2^20 - 1 en décimal.
Il est facile de se convaincre que pour un état quelconque des 20
cartes à un moment donné, et quelque soit le coup suivant, on obtient
un nombre strictement inférieur au précédent. En conséquence, de quelque
façon qu'on choisisse les cartes à retourner, on a une suite de nombres
positifs strictement décroissante qui atteint donc 0, soit l'état ou
toutes les cartes sont retournées. CQFD
En effet. Solution rapide et efficace ; en un mot : élégante.

Pour la généralisation à un nombre quelconque de cartes au départ,
on finit par atteindre 0 si on part de 2^(2n)-1, mais on finit par
atteindre 1 si on part de 2^(2n+1)-1.
--
Olivier Miakinen
Samuel DEVULDER
2017-06-01 13:33:11 UTC
Permalink
Raw Message
Post by Zarake
Le mieux est d'affecter un "1" à une carte dont on voit le dos et
un "0".....

Oh que voilà une solution simple , directe, bref jolie. Bravo pour
cette trouvaille!

Loading...