Le tour de cartes

(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)





Posted by: raptor77

Bonjour
Un paquet de 36 cartes est composé de 9 cartes de chaque couleur (pique, coeur, carreau et trèfle) et le dos de chaque carte a pour unique motif une grande flèche. Le paquet est mélangé par une personne dans le public puis est récupéré par l’assistant du magicien qui a le temps de prendre connaissance du contenu des cartes sans en modifier l’ordre. Le magicien demande alors à son assistant de lui montrer successivement le dos de chacune des cartes en partant de celle qui au-dessus du paquet. A chaque fois, le magicien prédit la couleur de la carte. L’assistant retourne la carte, annonce sa couleur et la met de côté. Le magicien marque un point quand sa prédiction est correcte. Le processus se poursuit jusqu’à épuisement du talon.

En supposant que l’assistant du magicien est assez habile pour orienter discrètement la flèche visible sur le dos des cartes dans un sens convenu avec le magicien, quel est le score maximum que le magicien est certain d’atteindre ?

Bonne chance


Posted by: Flodelarab

36

Ou alors c que l'assistant est pas si habile.

A chaque tour, il peut indiquer une des 4 couleurs


Posted by: raptor77

Citation:
Posté par Flodelarab
36

Ou alors c que l'assistant est pas si habile.

A chaque tour, il peut indiquer une des 4 couleurs


Non, la bonne réponse est beaucoup plus subtile.


Posted by: Flodelarab

????

A koi ça sert d'etre plus subtil puisque g le score maximum !


Posted by: raptor77

Citation:
Posté par Flodelarab
????

A koi ça sert d'etre plus subtil puisque g le score maximum !



Non je t'ai dis que ce n'était pas le score maximum.
Aviateur ou Nekros vous pouriez pas nous aider s'il vous plaît?


Posted by: Flodelarab



ya 36 cartes dans le paquet, il gagne 1 point par carte et 36 n'est pasle maxi ??????

kétudi ?
soit plus clair


Posted by: nekros

Citation:
Posté par raptor77
Aviateur ou Nekros vous pouriez pas nous aider s'il vous plaît?




Plutôt aviateurpilot, parce que le maximum est bien 36

M'enfin jsuis pas une référence non plus, loin de là...

A+


Posted by: BancH

Citation:
Posté par Flodelarab
A chaque tour, il peut indiquer une des 4 couleurs
Comment-ça ? Il peut présenter la carte sur sa longueur ?


Posted by: Flodelarab

Oui, c la solution la plus évidente.

Mais si on ne considère que la position verticale, alors une autre solution est possible:
N'oublions pas que le magicien voit 2 cartes: celle présentée et celle du paquet ....

2^2=4 couleurs désignables


Posted by: BancH

Non, il ne voit pas celle sur le paquet je pense.

Citation:
Le magicien demande alors à son assistant de lui montrer successivement le dos de chacune des cartes en partant de celle qui au-dessus du paquet.



Posted by: Flodelarab

Rien de contradictoire.

Mais je n'aime pas ce genre d'énoncé car le moindre indicateur binaire permet de multiplié par 2 le nombre de possibilité.
Par exemple: Horizontal/Vertical; carte main gauche/droite; Paquet vers le haut/bas; yeux de l'assistant vers le haut/bas; nombre de doigts sur la carte ... etc ...


Posted by: BancH

Ca ne serait pas 35 la réponse ?

Il se peut que le magicien puisse être sûr de deviner la couleur de la carte seulement après que la première soit passée...


Posted by: BancH

Sinon, pour 18 c'est simple, une carte sur deux l'assistant indique la couleur "noir ou rouge", et sur les autres, il indique "trèfle ou carreau" ou "coeur ou pique".


Posted by: raptor77

Citation:
Posté par BancH
Sinon, pour 18 c'est simple, une carte sur deux l'assistant indique la couleur "noir ou rouge", et sur les autres, il indique "trèfle ou carreau" ou "coeur ou pique".



Ce n'est ni 18, ni 35, ni 36.


Posted by: BancH

Il voit deux cartes le mage ? celle que l'assistant lui montre et celle sur le paquet ?


Posted by: nox

Citation:
Posté par Flodelarab
Rien de contradictoire.

Mais je n'aime pas ce genre d'énoncé car le moindre indicateur binaire permet de multiplié par 2 le nombre de possibilité.
Par exemple: Horizontal/Vertical; carte main gauche/droite; Paquet vers le haut/bas; yeux de l'assistant vers le haut/bas; nombre de doigts sur la carte ... etc ...



jsuis totalement d'accord...d'ailleurs si c'est faux j'aimerais bien savoir pourquoi...dire "nan c'est pas ça" c'est bien gentil mais faudrait un contre-argument ^^


Posted by: BancH

C'est pas très réaliste mais l'énoncé sert juste à modéliser le problème.


Posted by: Patastronch

C'est pas parceque tu as un ennoncé qu'il doit a tout prix être dans olympiade ... L'enigme des enfants de Diophante n'est clairement pas une olympiade vu son faible niveau. Et celle ci vu l'imprécision totale de l'ennoncé est sans aucun interet.

Car oui 36 est un score minimum accessible (et donc maximum) facilement. Mais si tu dis que ce n'est pas la bonne réponse, tu ne dit pas en quoi les raisonnements sont faux ce qui est absurde.

Par exemple fleche a gauche => coeur, droite => pique, haut=> trefle et bas=> carreau. Ca permet d 'avoir un score de 36. Alors qu'est ce qui est faux ? quelle partie de ton ennoncé interdit un tel raisonnement ?

Bon tout ca pour dire que les olympiades c'est un peu plus serieu que tes ennoncés sorti de ton télé 7 jours.


Posted by: Flodelarab

OHHHH!

Je suis choqué! Comment peut on dénigrer pareillement Télé7jours! !



Posted by: Patastronch

Suffit de ne pas avoir la télé :)


Posted by: raptor77

Solution

Remarques liminaires

le sens S des cartes est repéré par les chiffres 0 et 1
on établit une hiérarchie dans la couleur des cartes et par convention on dit que P(trèfle) < P(carreau) < P(cœur) < P(pique)
A) Le magicien peut prédire au moins 19 cartes :

Avec les dos de deux cartes consécutives, on a quatre configurations possibles selon les sens choisis par l’assistant du magicien avec = 00, 01, 10 et 11 ce qui permet à chaque tirage de rang pair d’annoncer la bonne couleur de la 2 ème carte. Par exemple, il suffit de convenir 00 = Trèfle, 01 = Carreau, 10 = Cœur, 11 = Pique.

Lorsqu’il reste deux cartes dans le paquet, il y a au maximum deux couleurs. Si les couleurs sont identiques, le magicien qui a mémorisé les cartes déjà tirées n’a aucune difficulté à annoncer la couleur des deux dernières cartes. Si les couleurs sont différentes, le sens de la 35 ème carte sert à désigner la couleur de la 35 ème carte de poids P le plus faible. Si =0, la couleur de la 35 ème carte sera de poids le plus faible, si =1, ce sera l’inverse.

Le magicien est donc certain de deviner correctement toutes les cartes de rang 2, 4, 6, ….,34, 35 et 36 soit au total 34/2 + 2 = 19 cartes.

B) Le magicien peut améliorer son score et deviner au moins 22 cartes :

On garde le même algorithme de détermination des cartes de rang pair mais on introduit une autre clé pour déterminer la couleur de certaines cartes de rang impair.

Il y a dans le paquet 18 cartes de rang impair. Deux couleurs au moins sont représentés. Il y a au maximum neuf cartes de la même couleur et au minimum cinq cartes. Ce minimum m ne peut pas être inférieur à 5 car d’après le principe des tiroirs, il y aurait 18 cases pour 4m cartes avec 4m 16 ce qui est impossible. Dès lors l’assistant utilise les deux premières cartes du paquet pour désigner la couleur la mieux représentée dans les tirages de rang impair. En désignant systématiquement cette couleur à tous les tirages de rang impair de 3 à 35, le magicien est sûr de désigner correctement la couleur d’au moins cinq cartes.

A partir du 3 ème tirage et jusqu’au 36 ème tirage, on reprend l’algorithme de détermination des cartes de rang impair. Cette fois-ci, le nombre des cartes de rang pair dont la couleur est correctement déterminé est réduit à 17 mais au total le score de 17 + 5 = 22 cartes marque une amélioration significative.

C) Encore un effort d’imagination et le magicien porte le nombre de cartes dont la couleur est correctement devinée à 24 :

Dans l’algorithme décrit en A) et qui garantit la bonne couleur des cartes quand elles sont de rang pair, on s’aperçoit que les rangs 2,4,6,8,10,…. n’apportent aucune information supplémentaire. La nouvelle méthode consiste à définir une séquence d’entiers a, b, c, d, e ,f… telle que les couples (a,b) (c,d) (e,f),… donnent une information double.

On y parvient de la manière suivante : le sens des deux premières cartes donne au magicien la couleur qu’il désigne deux fois de suite lorsque successivement les cartes n°2 et n°3 sont tirées. L’assistant s’assure bien entendu que l’un au moins des deux tirages est le bon. On poursuit le processus jusqu’aux cartes n° 32 et 33. Pour chaque couple de cartes (2k,2k+1), le magicien désigne toujours la même couleur qui est définie par le sens des cartes (2k-1,2k). Seize bonnes réponses sont ainsi garanties. Avec le sens des cartes n°33 et 34, le magicien identifie sans erreur la couleur de la carte n°34 puis selon la méthode décrite en A), il repère sans se tromper la couleur des cartes n°35 et n°36 de telle façon qu’au total 19 bonnes réponses au moins sont données par le magicien. A ce stade, le score n’est pas meilleur qu’en A).

Mais avec ce nouvel algorithme, le rang des cartes dont la couleur est correctement désignée n’est pas aussi régulier que dans A). C’est ainsi que sur les cinq premières cartes tirées, dans le pire des cas, c’est à dire quand le magicien dit seulement vrai une fois sur deux, les bonnes couleurs peuvent être annoncées avec les tirages (2,4) ou (2,5) ou (3,4) ou (3,5). Avec les tirages n°6 à 9, toujours dans le pire des cas, ce sont les couples de tirages (6,8) ou (6,9) ou (7,8) ou (7,9) puis avec les tirages n°10 à 13 ce sont les couples (10,12) ou (10,13) ou (11,12) ou (11,13) puis avec les tirages n°14 à 17 ce sont les couples (14,16) ou (14,17) ou (15,16) ou (15,17), avec les tirages n°18 à 21 ce sont les couples (18,20) ou (18,21) ou (19,20) ou (19,21) etc…..

On observe que quatre configurations sont possibles pour tout quadruplet de tirages 4n-2,4n-1,4n,4n+1 avec n=1,2,3,4,5,…. A chacune de ces quatre configurations, on va associer une couleur bien déterminée, par exemple :

Trèfle pour les tirages (2,4), (6,8), (10,12), (14,16), (18,20) …
Carreau pour les tirages (2,5), (6,9), (10,13), (14,17), (18,21) …
Cœur pour les tirages (3,4), (7,8), (11,12), (15,16), (19,20) ….
Pique pour les tirages (3,5), (7,9), (11,13), (15,17), (19,21) …
Avec n quadruplets de tirages, l’assistant peut donc faire passer au magicien une information très précise sur la couleur de n nouvelles cartes.

De quelles cartes nouvelles s’agit-il ? Quelle est la valeur optimale de n ? Cette valeur est 5 et le mode opératoire qui précise les nouvelles cartes est le suivant :

Jusqu’au tirage de la carte n°21, le magicien désigne à chaque couple (2k,2k+1) la couleur définie par le sens des cartes (2k-1,2k). Au passage, il note pour chaque quadruplet [4n-2,4n-1,4n,4n+1] les numéros des tirages où il a donné une réponse correcte. Dans le pire des cas, il obtient deux bonnes réponses et note les numéros correspondants. S’il a une ou deux bonnes réponses supplémentaires, c’est un bonus qui vient compenser l’impossibilité de désigner un couple unique de bonnes réponses à l’intérieur du quadruplet.

Jusqu’à présent 10 bonnes réponses au minimum ont été obtenues et toujours dans le pire des cas, le magicien enregistre cinq couples de bonnes réponses auxquels il associe cinq nouvelles couleurs C(n) pour n=1,2,3,4,5.

S’il obtient X fois trois ou quatre bonnes réponses à l’intérieur des différents quadruplets, le nombre total de bonnes réponses est N 3X+2(5-X) = 10+X et le magicien ramène le nombre n de couleurs à mémoriser à n=5-X.

A partir de la 22 ème carte tirée jusqu’à la 34 ème , le magicien utilise l’algorithme A) qui consiste à donner la couleur des cartes de rang pair 22,24,26,28,30,32,34 sur la base des sens des cartes (21,22) puis (23,24),….

Sept bonnes réponses sont assurées. Le nombre cumulé de bonnes réponses est alors de 17 au minimum.

Les cinq couleurs C(n) pour n=1,2,3,4,5 sont utilisées pour désigner les cartes n°25,27,29,31,et 33. Soit cinq bonnes réponses supplémentaires et 22 bonnes réponses en cumulé. Si on utilise un nombre plus réduit n = 5-X, le nombre de bonnes réponses est toujours (10+X) + 7 + (5 – X)=22

Enfin le magicien détermine de manière certaine les cartes n°35 et n°36. Soit deux bonnes réponses supplémentaires.

Au total (10+X) + 7 +(5-X) + 2 = 24 bonnes réponses au minimum quel que soit X compris entre 0 et 5.


ps : cette solution n'a pas été faite par moi


Posted by: BancH

Parce qu'après que le magicien ait fait sa prédiction l'assistant lui montre la carte ?????


Posted by: Patastronch

Sans donner la réponse tu aurais pu juste préciser que la fleche ne pouvait avoir qu'un sens binaire et qu'elle etait l'unique moyen de communication entre l'assistant et le magicien, pour contre-argumenter les réponses proposées. L'ennoncé serait devenu interessant.

Par contre ce qui me gène dans ta résolution, c'est qu'en aucun cas on prouve que ce minimum certain est maximum. Alors que l'ennoncé stipule clairement de donner le maximum du minimum certain non ?


Posted by: nekros

Mouais je ne comprends pas trop certains points de la solution...


Posted by: BancH

J'ai pas lu ta solution, elle est trop longue..

Mais j'ai 22 avec une solution simple.

On divise le paquet en trois groupe: Les deux premières cartes (A), les 17 suivantes(B) et les 17 dernières(C).

Avec B, l'assistant indique la couleur de C "rouge" ou "noir".
Avec C il indique "trèfle ou coeur" ou "pique ou carreau".
Avec A il apprend au magicien quelle type de carte se trouve en majorité dans B.

Le magicien aura alors deviné toutes les cartes de C, et au moins cinq cartes de B.










-