Le tour de cartes

[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

[BancH]

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

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

[nekros]

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

[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.