Trouver le numéro d'une carte - Page 2 — Les-mathematiques.net The most powerful custom community solution in the world

Trouver le numéro d'une carte

2»

Réponses

  • Hum, @bisam, l'information selon laquelle l'oracle répond de manière fonctionnelle ne me semble pas faire partie du problème original.
  • Ça n'a en fait aucune importance, puisqu'on cherche une stratégie qui permette d'identifier au moins une carte, quelles que soient les réponses (correctes) de l'oracle.
  • Modifié (June 2023)
    Une remarque à propos de la stratégie développée par le robot, il est clair qu'elle ne fonctionne plus au delà du seuil $N=3P-3$ mais cette stratégie est-elle la seule ?
    Domi 
  • Domi, tu ferais mieux de dire que $N$ est le nombre total de cartes et $P$ le nombre de cartes par paquets que l'on présente à l'oracle. C'est clair pour toi, peut-être pas pour tout le monde (d'autant plus que dans un message précédent tu as noté $P$ une permutation).
  • Modifié (June 2023)
    Tu l'as dit pour moi :)
    Je passe d'un site à l'autre et je perds parfois un peu le fil.
    Domi 
  • GaBuZoMeu a dit :
    Belle idée pour l’impossibilité. Ça marche aussi pour montrer que quand on fonctionne par paquets de 10 cartes et qu'il y a en tout 27 cartes, il n'y a aucune stratégie gagnante pour deviner une carte.
    Peux-tu développer pour (10;27)? J'ai dû l'écrire pour (3;6) et je n'arrive pas à l'étendre pour (10;27).
    The fish doesnt think. The Fish doesnt think because the fish knows. Everything. - Goran Bregovic
  • Modifié (June 2023)
    C'est exactement la même idée, il faut considérer la décomposition en 3-cycles : (1,2,3).(4,5,6).(7,8,9)....(25,26,27).
    Domi
  • GaBuZoMeu : pas compris pourquoi ça ne fait aucune différence.

    Pour le dire clairement : je ne pense pas que ça fasse partie du problème, mais je suis d’accord que toute stratégie qui marche un robot qui répond de manière fonctionnelle marche aussi contre un robot qui change d’avis : il suffit de ne pas écouter ce qu’il dit quand on lui pose à nouveau la question. Je dis juste ça à des fins de sauvegarde d’un énoncé joli.
  • En fait, tu as compris.
  • Modifié (June 2023)

    J'essaie de résumer où j'en suis.

    On peut supposer sans problème que les cartes sont alignées dans l’ordre de leurs numéros. Admettons que nous ayons proposé tous les 10-uplets au robot, il aura clairement gagné s’il arrive à nous faire croire que les cartes peuvent être numérotées de façon à ce qu’aucune d’elles n’affiche son rang. Nous dirons qu’une permutation P des 28 valeurs est compatible avec une question Q = {q1, q2, q3, … , q10} si Q et P(Q) ont un point commun. Si le robot trouve une permutation sans point fixe et compatible avec toutes les questions, il gagne en donnant à chaque question Q une valeur commune à Q et P(Q). Nous ne saurons alors jamais si la carte de rang i porte le numéro i ou P(i). Quand n = 27, cette permutation existe : P = (1,2,3).(4,5,6)…(25,26,27). À partir de n = 28, toute permutation compatible avec les réponses admet un point fixe, il suffit de décomposer P en cycles pour s’en rendre compte. Il reste une question et pas la moindre : quelle est la carte qui porte le bon numéro ?
    Domi

  • Modifié (June 2023)
    Est-ce que quelqu’un peut résumer où on en est ?
    C’est-à-dire, quels sont les couples $(n,k)$ tels que pour le jeu à $k$ cartes à jouer parmi $n$, il y a une stratégie gagnante ?

    Déjà, pour $k=1$ c’est trivialement bon pour tout $n$. Ensuite, pour $k=2$, ce n’est pas bon pour $n=2,3$ mais bon pour des $n$ supérieurs (fixer $a$ et jouer toutes les paires $\{a,b\}$ : si le robot ne répond que des choses différentes, on sait tout, et s’il répond deux fois la même chose, cette réponse est le numéro de $a$).
    Pour $k=3$, $n=5$ n’est pas bon, $7$ l’est, d’après GBZM.


    J’ai joué avec d’autres humains, et j’ai l’impression que pour $(6,3)$, il y a une stratégie gagnante.
  • Modifié (June 2023)
    J’essaie de résumer ce qui me semble établi avec tes notations
    1°) Pour chaque $k$ il y a un $n(k)$ à partir duquel il existe une stratégie gagnante et pour $n$ inférieur à $n(k)$ il n’y a pas de stratégie gagnante . La fonction $n(k)$ est croissante.
    2°) $n(k)> 3k-3 .$
    3°) $n(1)=1 ,\ n(2)=4 ,\ n(3)=7 .$
    4°) Une conjecture : $n(k)=3k-2 .$
    Domi.
  • Modifié (June 2023)
    Je garde vos notations: $n$ le nombre total de cartes, $k$ le nombre de cartes montrées.
    Plus quelques autres:
    -$E=\{1,...,n\}$, identifié aux cartes.
    -Pour tout sous ensemble $A$ de $E$ de cardinal $k$, $c(A)$ est l'élément de $A$ donné par le robot.
    -$D\subset E$ est l'ensemble image de $c$.

    Pour $i$ dans $D$, on regarde tous les ensembles $A$ tels que $c(A)=i$ et on fait leur intersection totale. Il y a nécesairement $i$ dedans.
     Mais si il n'y a que $i$ dans l'intersection, ça veut dire qu'on peut identifier la carte numérotée $i$ (il n'y a qu'une seule carte respectant toutes les réponses "$i$" du robot). 
    Sinon il existe un autre élément $j=f(i)$, appartenant à l'intersection. 

    Ainsi, si on ne peut identifier aucune carte à partir de toutes les réponses du robot, on peut définir une fonction $f$ sur $D$ qui vérifie la propriété suivante: pour tout $i$ dans $D$, $f(i)$ est différent de $i$ mais appartient à tous les ensenbles $A$ tels que $c(A)=i$.
    En particulier, pour tout ensemble $A$ de $E$ de cardinal $k$, $f(A)\cap A\not= \emptyset$ ($i=c(A)$ est dans $A$ et $f(i)$ aussi)

    Montrons que cette dernière propriété entraîne $n\leq 3k-3$.
    On peut supposer qu'il existe $B$ de cardinal $k-1$ tel que $f(B) \cap B=\emptyset$ (sinon, récurrence)
    Alors pour tout $i$ n'appartenant pas à $B$, en appliquant la propriété à $A=B\cup\{i\}$ on voit que soit $i\in f(B)$, soit ($i\in D$ et) $f(i)\in B$.
    Ainsi les éléments n'appartenant ni à $B$, ni à $f(B)$ sont tous envoyés dans $B$ par $f$.
    Si deux d'entre eux ont même image, disons $f(i)=f(j)=k$, alors $A:=B\cup\{i,j\}\backslash \{k\}$ vérifie $f(A)\cap A=\emptyset$ ce qui contredit la propriété. On déduit donc que ces éléments ont toute une image différente et qu'il y en a donc au plus $k-1$.
    Il y a également au plus $k-1$ éléments dans $B$ et $f(B)$, donc $3k-3$ en tout.
  • Modifié (June 2023)
    Tout me semble correct, bravo ! En plus la stratégie du joueur est très simple. Au moins une des intersections est un singleton, il suffit de donner la valeur de cette carte. Et si j’ai bien compris, tout se résume à cette propriété "élémentaire".
    S’il existe une fonction sans point fixe d’un ensemble dans lui-même telle que toute partie à $k$ éléments de cet ensemble intersecte son image alors le cardinal de cet ensemble est inférieur à $3k-2$.
    Domi
  • Modifié (June 2023)
    $3k-3$ en fait. Dans notre cas la fonction n'est a priori pas définie partout, mais on peut toujours l'étendre arbitrairement, donc oui je pense que tout se ramène à ce lemme.
  • Modifié (June 2023)
    Oui, inférieur strict ou inférieur ou égal, comme intersection ou intersection non vide, il faudrait préciser à chaque fois mais j'ai perdu ce réflexe depuis un moment :)
    Domi.
  • Si on ne précise pas, c'est sensé être entendu au sens large en mathématiques. Ce qui est contre-intuitif puisqu'en français courant, c'est le contraire!
    The fish doesnt think. The Fish doesnt think because the fish knows. Everything. - Goran Bregovic
  • Modifié (June 2023)
    Je l'ai su, mais la pratique au niveau élémentaire efface les habitudes. On pourra remarquer que Namiswan n'a pas réagi à "intersecte son image" alors que l'intersection existe toujours même si elle est vide, nous avons tous notre cadre mais tant qu'on se comprend tout va bien.
    Domi.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!