Inscription / Connexion Nouveau Sujet
Trouver un seul numéro
Bonjour à tous 
Un Petit problème d'apparence très simple mais qui donne assez vite mal au crâne .
Tu as devant toi un jeu de 28 cartes numérotées ( face cachée ) de 1 à 28 et tu dois simplement retrouver le numéro de l'une d'elles . Pour ce faire tu peux proposer ad nauseam des lots de dix cartes à un robot qui te donnera à chaque fois et sans commentaire , le numéro de l'une d'elles .
Es-tu certain de pouvoir assurer ta mission ?
On s'amuse et on peut blanker si on le juge utile
Imod
Bonsoir,
Un éclaircissement :
"tu dois simplement retrouver le numéro de l'une d'elles "
Est-ce que ça veut dire
1°) Une des cartes a un dos rouge, les 27 autres ont un dos bleu et tu dois trouver le n° de la carte au dos rouge.
ou
2°) À un moment donné, tu choisis une carte , tu dis "cette carte a le n° tant" et tu vérifies que tu as raison en retournant la carte.
C'est la deuxième proposition qui est la bonne : on donne le numéro d'une carte que l'on choisit à la fin du questionnement .
Imod
J'illustre avec un exemple plus abordable : 3 cartes A , B , C numérotées par les entiers de 1 , 2 , 3 . Je peux proposer des paires de cartes et le robot me donne le numéro de l'une d'entre elles .
AB -> 1
AC -> 2 ( un deuxième 1 donnerait la valeur de A ) .
BC -> 3 ( un deuxième 1 ou 2 donnerait la valeur de B ou C ) .
Mais alors on peut avoir ABC=132 ou ABC=213 , on ne connait donc la valeur d'aucune carte .
Imod
En effet , d'ailleurs en général on peut noter le jeu (P,T) pour P cartes proposées sur un total de T . Pour chaque P , il y a un seuil T à partir duquel le jeu est gagnant , ici (2,T) est gagnant quand T est supérieur ou égal à 4 , on peut le noter G(2)=4 . On se demande si G(10) est plus grand que 28 .
Imod
salut
j'attendais aussi des éclaircissements au début ...
avec ton exemple j'avais la même idée que toi à 16h44 mais je le faisais à l'envers : pour T fixé quel est le seuil maximal qui permette de déterminer le numéro ?
et donc pour ton cas particulier est-ce que 10 dépasse ce seuil ?
puisque dans tous les cas G(1) est gagnant !! 
je proposerais donc comme idée : est-ce que l'ensemble des parties à 10 cartes (parmi 28) ou encore en notant D cet ensemble alors est-ce que l'ensemble des applications de D dans [[1, 28]] permet de définir la fonction carte --> numéro ?
tout en se disant qu'en donnant plusieurs fois la même partie (selon ta règle) on puisse nous répondre différents numéros pour cette même parties ... le pire cas étant bien sûr que cette saleté de robot nous réponde toujours le même numéro à la même partie
ensuite je pense que c'est qu'une histoire de réunion et d'intersection ...
J'étais parti sur une fonction de l'ensemble des parties à 10 éléments vers l'ensemble des valeurs pour étudier les images réciproques de chaque élément mais ce n'est vraiment pas simple . Sinon je pense qu'il est plus naturel de considérer le minimum de cartes donnant une solution positive au problème pour un tirage de taille donné mais à chacun son point de vue
Imod
J'ai implémenté le robot 
J'ai beaucoup tourné en rond à me demander comment représenter les possibilités après un certain nombre de paquets proposés. Ma solution n'était pas correcte et j'ai finalement abandonné pour une méthode beaucoup plus brute. Je génère toutes les possibilités (il y en a factorielle(T)) et puis je filtre celles qui ne correspondent pas aux réponses du robot.
Ce faisant j'ai pu confirmer que G(3) = 7. Et j'ai découvert une méthode beaucoup plus propre de le prouver.
Pour que le robot gagne, il faut et il suffit que pour toutes les combinaisons de cartes ses réponses soient au moins compatibles avec deux permutations de valeurs.
Soit ces deux permutations, pour tout paquet de carte il faut que les valeurs de ces cartes pour chaque permutation ait au moins une valeur en commun.
Sans perte de généralité admettons que la première permutation est (1,2,3,4,5,6,7...,t).
Une façon de générer la seconde permutation est (2,3,4,5,6,7...,t,1).
Quel est le t maximum tel qu'il y ait toujours une valeur en commun? 2(p-1) En effet, dans le pire cas les cartes sont
1234567....t
234567....t1
^ ^ ^....^ Une carte en plus et on est sûr de retrouver une valeur déjà choisie pour l'autre permutation.
On peut faire mieux. 3(p-1) Avec la seconde permutation (2,3,1,5,6,4,8,9,7...,t-1,t,t-2)
Dans le pire des cas, les cartes sont:
123456789...
231564897...
^ ^ ^ ...
Il n'y a pas moyen de faire mieux car dans un groupe de quatre on peut choisir deux cartes avec tous les numéros différents.
On a donc G(p) > 3(p-1). Ou comme Imod le pensait, G(p) = 3p-2
Cliquez pour afficherBonjour LittleFox
J'ai bien compris qu'on pouvait supposer que les valeurs des cartes étaient aussi leurs rangs et que l'objectif du robot était de proposer un autre choix . Après je me perds un peu dans les générations de permutations . Il y a sans doute un résultat sur les décompositions en cycles qui explique le truc , je te fais confiance mais je n'ai pas encore tout compris .
Imod
Bonjour Imod
Je n'ai pas participé ,mais je profite de la présence de Littlefox
pour lui demander de bien vouloir jeter un oeil sur "Eclairage public"
car je suis sûr qu'il va valider...
Salut Imod,
On se perd dans les générations de permutations mais justement, c'est le problème du joueur. Le robot lui n'a pas besoin de générer des permutations. Il en fixe deux et répond de manière compatible à chaque fois.
Prenons un exemple:
t = 5, p = 3
Le robot choisi
abcde
12345
23154Voici une partie:
abc -> les valeurs en commun sont (1,2,3) -> 2 (une valeur parmi celles en commun)
abd -> (2) -> 2
abe -> (2) -> 2
acd -> (1) -> 1
ace -> (1) -> 1
ade -> (4,5) -> 4
bcd -> (3) -> 3
bce -> (3) -> 3
cde -> (4,5) -> 5
Quand plusieurs valeurs sont en commun le robot pourrait même changer de réponse pour le même choix de carte. Je joueur aura plus d'info mais il ne saura toujours pas choisir.
Qu'est ce que le joueur sait au final?
'ab' contient 2, 'bc' contient 3 et 'ac' contient 1 => abc = 231 ou 123 exactement ce que le robot avait choisi au départ.
On peut déduire aussi 'de' contient 4 et 5 => de = 45 ou de = 54. Encore une fois les choix du robot.
Seuls les permutations de longueur 2 et 3 ne sont pas séparables. Dans le sens où choisir deux cartes parmi elles ne permet pas de déduire de quelle permutation il s'agit parce qu'elles ont au moins une valeur en commun et le robot donne l'une de ces valeurs.
Je vais améliorer mon robot
J'ai amélioré mon robot pour qu'il soit plus plaisant à jouer
J'ai fait une version interactive pour jouer contre lui.
Je sais que je suis pénible mais j'ai toujours eu besoin de laisser reposer la pâte avant de faire mes crêpes
Avec les notations de LittleFox , je suis archi convaincu que G(p)>3(p-1) mais un peu moins que G(p)=3p-2 . La décomposition en 3-cycles est particulièrement efficace mais pourquoi le stade suivant nous libère-t-il à coup sûr ?
Imod
J'ai l'intuition que c'est parce que les 3-cycles ont le meilleur ratio nombre de cartes / max cartes choisies sans être séparable. Mais ce n'est pas une vraie preuve.
Voici un début de preuve, il me manque un petit bout mais peut-être saurez-vous m'aider
Quelques définitions:
- Une permutation est l'ensemble des valeurs au dos des cartes dans l'ordre des cartes.
- Deux permutations données forment un ensemble de cycles où dans chaque cycle la valeur suivante est la valeur de la deuxième permutation de la carte qui a la valeur courante dans la première permutation. Par exemple,les permutations 0213456 et 1523604 ont les cycles 0125, 3 et 46.
- Un n-cycle est un cycle de longueur n.
- On dit que deux permutations sont séparées, si (au moins) l'une d'elle ne correspond pas aux réponses du robot.
1) Les n-cycles (n>1) sont séparables avec un nombre de cartes choisies <= n//2. Où // est la division entière.
En effet, on peut prendre une carte sur deux (en laissant tomber la dernière carte si n est impair). L'ensemble des valeurs de la première permutation pour ces cartes est disjoint de l'ensemble des valeurs de la deuxième permutation. Sinon, c'est que notre n-cycle contient un 1-cycle ce qui contredit les hypothèses. Donc peu importe la valeur que le robot nous donne pour ces cartes, on peut éliminer une des permutations.
2) Si deux permutations n'ont aucune valeur en commun (pour la même carte), alors elles sont séparable avec un nombre carte p si t > 3(p-1).
En effet, comme les permutations n'ont pas de valeurs en commun, tous les cycles sont de longueur n>1.
Si le nombre de cycles c >= p alors il suffit de choisir 1 carte dans chaque cycle.
Sinon c < p et on peut choisir cartes. On a
.
3) Si t > 3(p-1), Alors, lorsque le robot a donné une réponse pour chaque combinaison de cartes, chaque paire de permutations possible a au moins une valeur en commun.
En effet, si toutes les valeurs sont différentes alors au moins une des deux permutations aurait été éliminée comme montré en 2).
Voilà ou j'en suis
S'il ne reste qu'une permutation on connait toutes les cartes. Et si toutes les permutations ont une valeur en commun alors on peut donner cette valeur.
En faisant des expériences, je remarque que tous les cycles sont les mêmes dans toutes les permutations restantes. Donc la valeur en commun dans chaque paire est la même pour toutes les permutations. Mais je ne vois pas comment montrer que les cycles sont les mêmes.
Une piste, par exemple (t,p) = (7,3):
0123456
0231564
1204536
La première et la deuxième permutation ont les cycles (0, 123, 456) et ne sont pas séparables.
La première et la troisième permutation ont les cycles (012, 345, 6) et ne sont pas séparables.
La deuxième et la troisième permutation ont les cycles (01463, 2, 5) et ne sont pas séparable non plus.
Pourtant demander abe permet d'éliminer au moins une permutation.
Si 0, on élimine la troisième;
Si 1, la deuxième;
Si 2 ou 5, la première;
Si 3 ou 6, on les éliminent toutes;
Si 4, la deuxième et la troisième.
Merci pour ta réponse LittleFox
J'ai un peu de mal avec tes notations car j'ai d'autres habitudes mais je vais m'y faire . Ce que j'ai compris :
Tu parles depuis le début de 2 permutations alors qu'il n'y en a qu'une , on peut en effet supposer sans problème comme tu le faisais remarquer que les cartes sont numérotées 123... la transformation est alors une simple bijection de 123... dans lui même . D 'autre part il est connu que toute permutation se décompose de façon unique ( aux permutations près ) en un produit de cycles .
J'ai plus de mal à voir ce que tu appelles séparé ou séparable , j'avais cru comprendre que cela signifiait que "la" permutation n'avait pas de point fixe . Tu confirmes ou tu infirmes ?
Je n'ai pas encore lu la suite
Imod
J'infirme
Je me place ici du point de vue du joueur.
Au départ avant que le robot n'ai répondu quoique ce soit, toutes les permutations des valeurs sont possibles.
J'en choisi une (qui peu être réordonnée en échangeant les cartes de place mais on s'y perd à réordonner en permanence et il n'y a pas besoin) je la compare aux autres une à une d'où mes paires de permutations.
Je démontre que si t > 3(p-1) et que les deux permutations n'ont pas de valeur en commun alors l'une des deux peut être invalidée avec les réponses du robot. Il ne reste donc à la fin que des permutations avec au moins une valeur en commun.
Au lieu de parler de valeur en commun, j'aurais pu dire que la seconde permutation après réorganisation des cartes pour que la première soit l'identité, n'a pas de point fixe. Mais ça me semble plus compliqué.
Séparée ou séparable dans le sens qu'on a ou qu'on peut retirer la permutation de l'ensemble des permutations compatibles avec les réponses du robot.
Par exemple les cycles (012, 3456) sont séparable pour p <= 3 mais pas pour p >= 4. En effet, si on a au moins deux cartes dans un cycle alors on a une valeur en commun pour ce cycle et le robot peut donner cette valeur. Par le principe des tiroirs, ça arrive si p > que la somme des tiroirs qui est ici de 3 (1 pour le premier cycle et 2 pour le second).
Ces cycles sont générés par la paire de permutations 0123456 et 1204560. On peut réordonner les cartes mais attention à bien le faire de la même façon pour les deux (et pour les questions au robot).
J'ai implémenté mon joueur théorique et effectivement il y a un soucis.
Première remarque: on ne demande au robot que les combinaisons de cartes contenant la première carte.
J'ai fait plusieurs parties en (t,p) = (5,2) et la plupart du temps le joueur gagne. Il suffit que le robot donne deux fois la même réponse et on sait la valeur de la première carte.
Par contre quand le robot répond avec des valeurs différentes à chaque fois, on ne sait pas décider. Par exemple, le joueur théorique ne gagne pas cette partie:
ab -> 0
ac -> 1
ad -> 2
ae -> 3
Les permutations finales:
04123
10423
20143
30124
40123
Elles ont bien 2 par 2 une valeur en commun mais pas toutes la même. Et les cycles ne sont pas les mêmes.
On pourrait demander au robot bc pour éliminer entre 1 et 3 permutations mais le joueur théorique ne le fait pas.
Je ne sais pas trop quoi te répondre car tes programmes ne me parlent pas ( je suis largué depuis longtemps en informatique ) . Voilà comment j'avais interprété ton premier message :
Le robot cherche une permutation P des n éléments sans point fixe et de façon à ce qu'il puisse répondre à chaque question Q ( un ensemble de p cartes ) un élément appartenant à la fois à Q et à P(Q) . On ne saurait alors jamais pour chaque carte i si sa valeur est i ou P(i) . Si n=3(p-1) la permutation P=(1,2,3).(2,3,4)...(n-2,n-1,n) remplit clairement le cahier des charges donc on ne trouvera la valeur d'aucune carte si n<3p-2 . Que se passe-t-il à partir de 3p-2 ?
Deux questions :
1°) Le robot utilise la même stratégie : perd-t-il à tous les coups ?
2°) Existe-t-il une autre stratégie ?
Pour le 1°) la décomposition en cycle me semble une bonne piste mais je n'ai aucune idée pour le 2°) .
Il reste du grain à moudre
Imod
1°) Oui, le robot perds à tous les coups, c'est ma thèse 2).
Si n>3(p-1) alors on peut pour toute permutation P choisir p cartes Q de façon à ce que les valeurs de Q et de P(Q) soient disjointes. On élimine donc une permutation et il ne reste que l'autre.
2°) J'essaie de prouver qu'il n'existe pas de stratégie gagnante pour t > 3(p-1) et donc pas de meilleure que celle des 3-cycles. Je ne suis pas loin je pense.
Si une telle stratégie existe alors les permutations qui sont compatibles avec ont une valeur en commun deux par deux.
Un résultat est que plus de deux permutations sont compatibles, sinon le joueur peut donner cette valeur en commun.
D'accord , ma première question n'a pas lieu d'être , je n'avais pas compris ton développement 
Il reste à savoir si le robot ne dispose pas d'une autre stratégie
Imod
J'ai réussi à mettre un peu d'ordre dans mes idées ( ce problème est vraiment un casse-tête ) . Je n'arrive pas à raisonner avec deux permutations en même temps , je reste donc sur une seule . Il est "clair" qu'à partir de t=3p-2 , le robot ne pourra pas produire de permutation P sans point fixe avec Q et P(Q) disjoints . Mais si je reprends mon rôle de joueur , j'ai du mal à voir comment exploiter ces réponses pour trouver une bonne carte .
Imod
De mon côté je travaille avec t! permutations en même temps .
Et j'essaie de les éliminer en les confrontant les unes aux autres.
Je n'ai pas trouvé le moyen d'envoyer un message personnel sur l'île ( je ne sais pas si c'est possible ) . Comme LittleFox c'est beaucoup investi dans le problème , je lui signale que celui-ci a énormément progressé sur le site déjà nommé .
Imod
Je dirais même que le problème est résolu.
J'ai implémenté le "joueur de Namiswan": .
J'ai dû passer dans la démonstration avec plusieurs exemples concrets pour comprendre. Mais c'est une belle démonstration.
Juste une petite erreur: et non
.
Un exemple concret en suivant la démonstration de Namiswan:
Le robot a choisi ces cartes :
abcde
14023abc -> 0 (c)
abd -> 1 (a)
abe -> 4 (b)
acd -> 2 (d)
ace -> 0 (c)
ade -> 1 (a)
bcd -> 2 (d)
bce -> 4 (b)
bde -> 3 (e)
cde -> 2 (d)Les intersections sont
0 (c) -> ac
1 (a) -> ad
2 (d) -> cd
3 (e) -> be
4 (b) -> bceOn a bien
Comme aucune intersection ne contient qu'un élément, on ne peut pas déduire la valeur d'une carte. C'est attendu pour
c -> a
a -> d
d -> c
e -> b
b -> cOn a bien
Choisissons
On vérifie
On a bien
Et donc
En fait il n'y a pas d'erreur , chez nous le signe d'inclusion est à prendre au sens large , comme le terme inférieur qui sans précision signifie inférieur ou égal
Imod
Je suis d'accord pour le terme sous-ensemble mais pas pour le signe.
est différent de
tout comme
est différent de
.
Si le français est imprécis, les notations mathématiques sont justement faites pour être précises.
Oui , apparemment le signe d'inclusion sans le égal a évolué vers un ordre strict comme pour le signe inférieur mais ce n'est pas universel . Par contre il ne faut pas mélanger l'appartenance et l'inclusion .
Imod
Annuler
connectez vous