Un Peu De Logique

[matthias]

Oui c'est bien un croisement.
Et comme quand il reste 2 cartes, on se trouve nécessairement dans le cas que décrit kNz, on a une méthode qui donne au moins 19 points

Mais on peut faire mieux
-----

[invitef4181796]

Oui c'est bien un croisement.
Et comme quand il reste 2 cartes, on se trouve nécessairement dans le cas que décrit kNz, on a une méthode qui donne au moins 19 points

Mais on peut faire mieux

Moi ça m'énerve, je trouve jamais

[invitea2d336f8]

Ca me rappelle un tour qu'on faisait avec un copain :
n'importe quelle carte tirée au hasard était devinée.
L'assistant voyait la carte et donc, pour les chiffres on avait déterminé le doigt qui correspond (main droite si>5 sinon main gauche), le doigt choisi pointait vers un coin de la carte pour désigner la couleur, pour les têtes, on avait sélectionné 4 paires de doigts .
L'indication digitale portait sur le dos de la carte, naturellement, pendant que la valeur eétait montrée à tout le monde
Simple à indiquerà pour l'assistant, et simple à interpréter pour le "magicien".
Effet garanti ))

[yat]

Mais on peut faire mieux

Bon, juste pour voir, j'ai calculé le nombre de combinaisons pour un paquet de 36 cartes avec 9 cartes de chaque couleur. Le résultat nécessite...

64 bits

Par contre, pour avoir mieux que 19 points, je commence à sécher sérieusement... est-ce que il faut se baser sur une solution ou on code la moitié des cartes sur deux bits, puis changer de stratégie à la fin ? Parce qu'à part les deux dernières cartes, j'ai du mal à voir une manière certaine d'augmenter son score minimum : l'antépénultième n'utilise pas pleinement ses deux bits parce qu'il n'y aplus que trois possibilités au maximum à ce moment là, mais je ne vois pas comment les récupérer. Pour le reste, mes mésaventures avec la compression Huffmann me poussent à essayer de mettre moins de bits pour les couleurs les plus probables, mais j'ai l'impression qu'à chaque tentative je n'aboutis qu'à améliorer l'espérance du résultat, mais jamais le score minimum, qui a l'extrème éfronterie de redescendre à 18 dès que je bricole un peu trop.

Dès que je vois un chat passer, il va avoir à bouffer.

[matthias]

Bon alors pour l'instant, tu sais déterminer les deux dernières cartes, et toutes les cartes paires parmi les 34 premières.
En reprenant une de tes idées, est-ce que tu ne pourrais pas sacrifier quelques cartes au début pour donner une indication sur les cartes impaires, ce qui éviterait au magicien de donner une réponse complètement au hasard ?

[invite788778a8]

Bonsoir,

Ne pouvant rester ce soir, Je laisse le soin à matthias de vous aider.

A+

[yat]

En reprenant une de tes idées, est-ce que tu ne pourrais pas sacrifier quelques cartes au début pour donner une indication sur les cartes impaires, ce qui éviterait au magicien de donner une réponse complètement au hasard ?

Alors tentons... je sacrifie les deux premiers bits pour indiquer la couleur la plus présente dans les cartes impaires qui suivent, sauf l'avant dernière. Comme ça représente 16 cartes, ça m'assure 4 bonnes cartes en plus. Il me reste 16 cartes paires à donner, plus les deux dernières qui de toutes façons ne consomment que l'information qu'elles représentent, ce qui m'amène à un total de 22.

Faut vraiment me mettre le nez sur la solution.

Je suis encore loin ?

[invite35452583]

Salut,
je n'avais pas compris que l'assistant connaissait toutes les cartes
ça m'apprendra à bien lire un énoncé
malheureusement y'a du boulot encore
Une piste que j'entraperçois est :
au lieu de codifier (0,0)...(1,1) les couleurs une fois pour toutes, on peut codifier ainsi après qu'une couleur ait été trouvée (ou au tout début)
on fait deux paquets, le premier contenant la couleur la plus nombreuse restant (arbitré par l'ordre sur les couleurs) et un couleur moins nombreuse, un deuxième avec le deuxième couleur la plus nombreuse et la quatrième couleur. La flèche vers le haut indique le premier ensemble et le magicien nomme la couleur la plus nombreuse, la flèche vers le bas désigne le deuxième ensemble et le magicien désigne la couleur la deuxième plus nombreuse (la plus nombreuse de cet ensemble).
Si la couleur était adapté elle est trouvée et on reprend tout de suite le même procédé.
Si la couleur n'était pas adapté, la désignation de l'ensemble concerne l'info sur la carte suivante selon un code quelconque (par exemple flèche répétée=même couleur(la+nombreuse), inversion de flèche c'est l'autre couleur.
Pourquoi ça me semble améliorer :
soit on réduit le nombre de carte de 2 à 1 pour désigner une couleur et on augmente le nombre de cartes trouvées
soit on n'a temporairement pas de bol et la carte est de la couleur déjà sortie mais cela accélère l'arrivée vers une situation où il n'y a plus que 3 puis 2 couleurs.
J'essaie de voir comment mener un calcul déterminant un minimum de cartes trouvées et de calculer ce minimum.
C'est tiré par les cheveux?

[matthias]

Alors tentons... je sacrifie les deux premiers bits pour indiquer la couleur la plus présente dans les cartes impaires qui suivent, sauf l'avant dernière. Comme ça représente 16 cartes, ça m'assure 4 bonnes cartes en plus. Il me reste 16 cartes paires à donner, plus les deux dernières qui de toutes façons ne consomment que l'information qu'elles représentent, ce qui m'amène à un total de 22.

Oui ça marche
Mais on est plus obligé de se soucier des deux dernières cartes en fait. On sacrifie les deux premières et ensuite on utilise la méthode de désignation des cartes paires jusqu'au bout.
Du coup on trouve 17 cartes paires et au moins 5 impaires, donc 22 en tout.

Je suis encore loin ?

On se rapproche

[yat]

Mais on est plus obligé de se soucier des deux dernières cartes en fait. On sacrifie les deux premières et ensuite on utilise la méthode de désignation des cartes paires jusqu'au bout.
Du coup on trouve 17 cartes paires et au moins 5 impaires, donc 22 en tout.

Ce qui revient donc au même, sauf que j'ai une meilleure espérance

On se rapproche

Ca commence à devenir serré, là...
Je pense qu'on peut insérer un signal supplémentaire au milieu du flux pour passer à une autre phase.. par exemple, donner une fausse couleur pour une carte paire... ça pourait par exemple permettre de remplacer la couleur par défaut des cartes impaires (en bricolant un tout petit peu : si la couleur qu'on veut préciser est bien celle de la carte qu'on montre, alors on donne le code de l'ancienne couleur par défaut). Mais là encore, pas moyen d'améliorer quoi que ce soit pour le cas le moins avantageux, et j'ai perdu une carte.

Ou alors on peut prendre 4 bits pour coder le nombre de cartes impaires de la couleur indiquée, mais ça ne sert à rien et ça coute 2 cartes...

Je pense que je vais laisser passer la nuit là dessus... demain est un autre jour

[matthias]

Je pense que je vais laisser passer la nuit là dessus... demain est un autre jour

Ca me laissera le temps d'aller revoir la méthode pour faire mieux, si je me souviens bien ça commence à devenir compliqué
Le pire c'est que je n'ai pas de démo qui dise que la méthode est optimale.

Mais bon quand même, pour te laisser de quoi réfléchir pendant tes heures d'insomnies, voici une piste.
Que se passe-t-il si on adopte la stratégie de base suivante : tous les 2 bits, le magicien propose la couleur correspondante par pour une seule carte, mais pour deux cartes consécutives ? Si l'assistant ne fait pas n'importe quoi, le magicien gagne au moins un point sur les tours 2 et 3, au moins un sur les tours 4 et 5, etc. L'intérêt de cette approche est qu'elle peut dans certains cas laisser un choix à l'assistant, et qu'il peut utiliser ce choix pour coder de l'infomation ...

[yat]

Mais bon quand même, pour te laisser de quoi réfléchir pendant tes heures d'insomnies, voici une piste.
Que se passe-t-il si on adopte la stratégie de base suivante : tous les 2 bits, le magicien propose la couleur correspondante par pour une seule carte, mais pour deux cartes consécutives ? Si l'assistant ne fait pas n'importe quoi, le magicien gagne au moins un point sur les tours 2 et 3, au moins un sur les tours 4 et 5, etc. L'intérêt de cette approche est qu'elle peut dans certains cas laisser un choix à l'assistant, et qu'il peut utiliser ce choix pour coder de l'infomation ...

Maaaais-euh ! C'est pas juste, je venais de trouver...


Bon, j'en suis à 24, mais je crois que j'ai gratté un bit là ou il n'y en avait pas, faut que je vérifie que ça me permet de rester à 24. J'arrive.

[yat]

Voilà ma réponse, corrigée (je m'étais offert un bit à la première carte, je ne sais pas trop pourquoi) :

J'ai peut-être un truc, mais c'est un peu tiré par les cheveux.

Je me base sur l'idée que j'avais émise plus haut, de donner une information supplémentaire en me basant dur le fait de donner un faux code. Là c'est un peu plus tordu... le code que je donne avec les cartes 1 et 2 me donne une couleur valable pour les cartes 2 et 3. Donc pour la carte 2 et 3, le magicien annoncera la couleur que je lui ai indiquée. Dans le cas standard, il va se planter une des deux fois. Mais comme c'est moi qui choisis si je donne la couleur de la carte 2 ou 3, je peux lui donner un bit d'information supplémentaire pour chaque couple de cartes.

Avec cette technique, je continue donc de lui nommer une carte sur deux (au rang 2n+1 il aura donc au minimum n bonnes réponses), mais j'accumule des bits supplémentaires (au même rang, j'en ai au maximum n). Si deux cartes d'un couple sont de même couleur, je ne gagne pas de bits d'information à cette étape, mais je gagne un point supplémentaire, ce qui se compense exactement, puisque chaque bit supplémentaire que j'ai accumulé pourra me servir, dans une deuxième phase, et couplé avec le sens de la flèche au dos de la carte, à deviner avec certitude toutes les cartes.

Du coup, voilà ce que ça me donne :

au tirage 2n+1, j'ai gagné n+p points, avec p le nombre de paires de même couleur. J'ai également accumulé n-p bits.
Il me reste 35-2n cartes à tirer, dont 2 qui ne nécessitent rien d'autre que leur propre information. Dès que n-p est supérieur ou égal à 33-2n (c'est à dire que 3n-p est supérieur ou égal à 33), je passe en deuxième phase. Les n-p bits que j'ai accumulé vont me fournir chacun un point, à quoi s'ajouteront les 2 points offerts par les deux dernières cartes.

Si p=0, 3n>=33, je passe donc en deuxième phase quand n=11, j'ai gagné 11 points, accumulé 11 bits, il reste 13 cartes que je vais pouvoir trouver, je me garantis 24 points.

Avec p=1, n=12, j'ai 13 points et 11 bits, il reste 11 cartes, 24 points.
Avec p=2, n=12, j'ai 14 points et 10 bits, il reste 11 cartes, 25 points.
Avec p=3, n=12, j'ai 15 points et 9 bits, il reste 11 cartes, 26 points.
Avec p=4, n=13, j'ai 17 points et 9 bits, il reste 9 cartes, 26 points.

Et manifestement, le score va continuer de progresser ainsi jusqu'au coup de bol complet ou je vais pouvoir deviner toutes les cartes parce qu'elles sont par paires de même couleur pendant toute la première phase, 35 points, plus un éventuel coup de bol sur la première. J'ai donc bien un minimum de 24.

Ouf... j'espère que c'est bon. On peut aller plus loin ?

[matthias]

Ouf... j'espère que c'est bon. On peut aller plus loin ?

Ca a l'air de marcher. Et je ne connais pas de méthode pour faire mieux que 24.

Mais tu peux préciser comment le magicien va prendre en compte les infos supplémentaires ?

[yat]

Mais tu peux préciser comment le magicien va prendre en compte les infos supplémentaires ?

Bah ça fait longtemps qu'on n'en est plus là...

Bref, à chaque carte, il prend le bit de la carte et le prochain bit en réserve, ça lui fait deux bits, donc une couleur.

Plus concrètement, par exemple on peut dire que le sens de la flèche indique rouge vers le haut et noir vers le bas, avec le bit gardé en réserve, 0 veut dire pique ou coeur, et 1 veut dire carreau ou trèfle.

En mettant par exemple en première phase, que si la première carte est bonne on met un 0, si c'est la deuxième on met un 1.

C'est plus clair comme ça ?

[matthias]

Bah oui, mais on pourrait aussi faire autrement. Par exemple dire que les bits en réserve servent pour coder les impaires à partir d'un certain rang.
Je posais la question juste pour que ta méthode soit décrite complètement ...

[invite35452583]

Après vérif je me suis fourvoyé, j'ai fait compliqué sans aboutir.
Bravo à Yat vraiment meilleur que moi dans ce genre d'exercice de style.

[invite788778a8]

Bonjour

Bravo YAT

Voici la réponse qui était donnée avec ce casse tête

ATTENTION JE VAIS DEVOIR FAIRE PLUSIEURS FICHIERS

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.

[invite788778a8]

Voici comment arriver à 24 cartes

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.

[kNz]

à yat et joli problème !

Pour ce tour là, le magicien doit avoir une sacrée mémoire quand même

[invite788778a8]

Bonjour,

Trouvez un entier N à 6 chiffres dont 5 chiffres sont pairs et dont la racine carrée est constituée uniquement de chiffres pairs et que si je vous indiquais la position du chiffre impair dans N vous trouvez la réponse.

Bon courage.

[yat]

200704 .

[matthias]

Je trouve pareil. Yat, tu l'as fait bourrin où avec une super astuce ?

[invite788778a8]

bravo YAT

Pour les autres : pourquoi 200704

[matthias]

Pour les autres : pourquoi 200704

Parce que c'est le seul qui marche, quelle question ...
Le nombre impair ne peut pas être en 1ère position à partir de la droite (car pair). Pas en 2ème (664 et 804), pas en 4ème (640 et 802), pas en 5ème (480 et 662), pas en 6ème (400 et 408).
Reste 448 avec le nombre impair en 3ème position.

[yat]

Je trouve pareil. Yat, tu l'as fait bourrin où avec une super astuce ?

Bah... bourrin, bourrin, c'est un bien grand mot. Des nombres de trois chiffres tous pairs, il y en a 125, c'est pas la mer à boire... si ?

Bon, ok, j'avoue, j'ai fait un programme.

[invite788778a8]

Bonjour matthias

Je voulais dire : comment avez vous fait pour trouver 200704.

Sinon, il y a 75 valeurs possibles mais seulement 17 qui possédent un chiffre impair et non pas 9 comme semble dire matthias

[yat]

Je voulais dire : comment avez vous fait pour trouver 200704.

Personnellement, en énumérant.

Sinon, il y a 75 valeurs possibles mais seulement 17 qui possédent un chiffre impair et non pas 9 comme semble dire matthias

Je pense que les résultats donnés par matthias l'étaient à titre d'exemple, juste pour montrer qu'il y a au moins deux possibilités pour chacunes des autres positions.

[matthias]

Personnellement, en énumérant.Je pense que les résultats donnés par matthias l'étaient à titre d'exemple, juste pour montrer qu'il y a au moins deux possibilités pour chacunes des autres positions.

Oui évidemment. Je n'ai d'ailleurs pas fait de programme pour résoudre le problème et si on est pas trop bourrin, il n'y a pas tant de tests que ça à faire. Par exemple, une fois qu'on en a trouvé 2 avec le chiffre impair en 6ème position, ce n'est plus la peine de tester ceux dont le carré est entre 100000 et 200000, entre 300000 et 400000, etc.