Nan mais ça c'est pour le défault
Sans parler que je rage aussi sur le fait, que celui qui est vert ils ont mis un decalco "tête de requin" et ça je trouve ça cringe, d'où le blanc... Mais du coup j'ai peur que les accessoires soient po de la même couleur. u.u Après il fait aussi disparaître le blason, que j'aime pas non plus.
Après pour celle de Peter Coffin, qui ennuit aussi bien Le Curieux que Krabot, toutéde la fote de Snufkin, qui avait abordé le mème et que j'avais juste mis le short, du coup j'avais peur que le curieux me tombe ensuite dessus de pas avoir suffisament crédité la personne. é.è
Moi mon avis, c'est que Hbomberguy a raté sa vidéo, pdt 4h il appelle à bâtir un meilleur "youtube" en jetant des individus à la vindicte populaire, même si il conclut par dire que ça aura pas d'impact. Méducoup il lance une croisade décapité, qui peut que déboucher sur du harcèlement et j'ai du mal à voir un net positif...
Même son idée de dire, qu'il faudrait, que "les youtubeurs sourcent/créditent leurs vidéos" est pour moi stupide, vu que c'est même pas dans les règles de youtube.
Enfin, c'est sans doute une vidéo divertissante de 4h, mais pour moi ça va pas audelà que du divertissement...
Rappel : Situation initiale : Plateau avec des pièces mises n'importe comment, et une case contient une clé. Joueur 1 : Retourne exactement une pièce Joueur 2 : Arrive, regarde le plateau et devine où se situe la clé.
L'indication que je donnais, c'est ce que doit faire le joueur 2 (en voyant le plateau, il fait un calcul de XOR et en déduit où se situe la clé). Ce qu'il faut montrer, c'est que cette fonction permet effectivement de gagner à tous les coups, autrement dit que quelque soit la situation intiale, le joueur 1 peut, en retournant une pièce, se débrouiller pour que joueur 2 trouve la clé. On dira qu'un plateau "désigne" la case obtenue par XOR des cases avec des pièces à pile.
Voilà un exemple pour aider à comprendre comment ça marche :
Spoiler
Les cases sont donc 00, 01, 10, 11, on peut, comme le suggère l'indication, construire le XOR des pièces à pile.
Par exemple, si le plateau est P, F, P, P, Joueur 1 calcule le XOR de 00, 10, et 11, et en déduit que le plateau "désigne" la case 01.
S'il veut que le plateau désigne 00, il retourne la case 01 (le plateau est alors PPPP, qui désigne bien 00) S'il veut désigner la case 01 (celle qui est déjà désignée), il retourne 00. S'il veut désigner la case 10, il retourne 11. S'il veut désigner la case 11, il retourne 10.
Autrement dit : il retourne la case qui est le XOR entre la case actuellement désignée par le plateau et celle qu'il veut que le plateau désigne. On peut se convaincre aisément que cela fonctionne.
Reste à déterminer comment ça peut se généraliser pour d'autres valeurs que 4, puis à montrer qu'il n'y a pas de solution dans les autres cas !
[ce message a été édité par Uncurieux le 22/07 à 15:43]
Je ne comprend pas comment le XOR permet de désigner une case, par exemple quand tu dis "Par exemple, si le plateau est P, F, P, P, Joueur 1 calcule le XOR de 00, 10, et 11, et en déduit que le plateau "désigne" la case 01." ce que je vois c'est que XOR de 00=0, XOR de 10=1, XOR de 11=0... Et je ne sais que faire de cette info. Pareil pour "S'il veut que le plateau désigne 00, il retourne la case 01 (le plateau est alors PPPP, qui désigne bien 00)" Si le plateau est PPPP, alors les XOR donnent 0 1 1 0, je ne comprend pas comment ça peut désigner 00...) De toute évidence, je dois mal utiliser le XOR ^^ *noob inside*
> Je ne comprend pas comment le XOR permet de désigner une case, par exemple quand tu > dis "Par exemple, si le plateau est P, F, P, P, Joueur 1 calcule le XOR de 00, 10, et > 11, et en déduit que le plateau "désigne" la case 01." ce que je vois c'est > que XOR de 00=0, XOR de 10=1, XOR de 11=0...
Ah, j'ai utilisé un raccourci : quand on parle de faire du XOR de nombres à plusieurs bits, on fait généralement du XOR bit-à-bit : autrement dit un XOR de tous les premiers bits ensemble, puis un XOR de tous les deuxièmes bits ensemble.
Avec 00, 10 et 11, cela donne (0 ⊕ 1 ⊕ 1 = 0), (0 ⊕ 0 ⊕ 1 = 1) donc 01.
Le XOR-bit-à-bit entre deux nombres à plusieurs bits (que je note aussi ⊕) conserve les propriétés intéressantes du XOR, par exemple, si A et B sont deux nombres en binaire : A ⊕ B ⊕ B = A
Or justement, dans cette situation, si le plateau désigne A, tu voudrais qu'il désigne B. Il suffit alors de voir que A ⊕ (A⊕B) = B (autrement dit, en retournant la pièce (A⊕B) d'un plateau qui désigne A, le plateau va désigner B).
[ce message a été édité par Uncurieux le 22/07 à 16:06]
> Les cases sont donc 00, 01, 10, 11, on peut, comme le suggère l'indication, construire le XOR > des pièces à pile. > > Par exemple, si le plateau est P, F, P, P, Joueur 1 calcule le XOR de 00, 10, et 11, et en > déduit que le plateau "désigne" la case 01. > > S'il veut que le plateau désigne 00, il retourne la case 01 (le plateau est alors PPPP, qui > désigne bien 00) > S'il veut désigner la case 01 (celle qui est déjà désignée), il retourne 00. > S'il veut désigner la case 10, il retourne 11. > S'il veut désigner la case 11, il retourne 10. > > Autrement dit : il retourne la case qui est le XOR entre la case actuellement désignée par > le plateau et celle qu'il veut que le plateau désigne. On peut se convaincre aisément que cela > fonctionne.
il me semble que la méthode se généralise à tous les entiers qui sont une puissance de 2 : on numérote les case en binaire, le XOR des case avec un Pile fait un certain nombre, et on est capable de changer n'importe quel digit de ce XOR en changeant de sens la pièce de la case désignée par ces digits (plus précisément, la case qui a des 1 sur ces digit et des 0 sur les autres). Pouvant changer n'importe quelles digits, on peut désigner n'importe quelle case du plateau avec un seul changement de sens, pour toute les positions initiales.
une peu de formalisme pour ceux qui tenteraient de continuer le problème (personnellement j'abandonne) :
1/ ce que voit le second joueur, c'est un plateau dans un certain état ; il n'a pas d'autres informations (il ne sait pas l'état initial, quelle pièce a été retournée etc). A partir de cet état, il doit choisir une case. L'enjeu est donc de créer une fonction f prenant en argument un état du plateau X et renvoyant une case.
Un état du plateau est un élément de {F,P}^n (une suite de n P et F). Il contient 2^n élément.
On a n cases, qu'on peut par exemple numéroter de 0 à n-1 (pour rester raccord avec l'exemple à 4 cases, où les cases sont numérotées de 0 à 3, et leur nombre noté en binaire).
On veut donc créer une fonction f: {F,P}^n -> les entiers de 0 à n-1.
2/ évidemment ce n'est pas la seule contrainte pour f. On a, par ailleurs, n mouvements élémentaire qu'on peut noter m0, m1,... m_(n-1), m_i consistant à retourner la pièce de la case i. Pour un état donné du plateau noté X, on peut noter X+m_i l'état du plateau après avoir effectué le mouvement m_i.
Par exemple, si X = FFF, X+m2 = FPF, X+m2+m1 = PPF, X+m2+m1+m2 = PFF, etc.
L'ordre des mouvements n'importe pas (c'est pour ça que j'ai utilisé la notation "+" : X+m1+m2 = X+m2+m1). Faire deux fois le même mouvement revient à la position initiale (X+m1+m1=X).
le premier joueur voit le plateau dans un état X quelconque, et doit pouvoir désigner n'importe quelle case avec un unique mouvement. En d'autres termes, pour tout X fixé, la fonction qui a un mouvement m associe la case f(X+m) doit être surjective. Puisque par ailleurs, on a autant de mouvements que de cases, il faut que cette fonction soit bijective.
On peut noter f_X la fonction qui, à un mouvement m donné, associe f(X+m). La contrainte s'écrit alors pour pouvoir résoudre le problème : pour toute position X, f_X définie par f_X(m) = f(X+m) est une bijection de l'ensemble des mouvements vers l'ensemble des cases.
3/ De ceci, on peut facilement établir que deux état du plateau séparés de deux mouvements désignent forcément une case différente par f. En effet, les état X+mi+mj et X sont a un mouvement de X+mi, et f_(X+mi) étant injective, f(X) = f_(X+mi)(mi) est différent de f(X+mi+mj)=f_(x+mi)(mj).
3a/ de là on déduit rapidement que le problème n'a pas de solution pour n=3. En effet, si f est une telle solution et X est un état, alors f(X+m1+m2+m3) doit être différent de f(X+m1), f(X+m2) et f(X+m3) ; mais f_x étant surjective, f(X+m1), f(X+m2) et f(X+m3) désignent les 3 cases du plateau. f(X+m1+m2+m3) ne peut donc désigner aucune case.
... Et de là je bloque. on peut montrer que le système n'a pas de solution pour n=5 et n=6 (en vrai ça ne demande pas de creuser loin dans la combinatoire), de là je conjecture qu'il n'y a de solution que si n est une puissance de 2, mais j'arrive pas à trouver de méthode qui se généralise.
Wow, c'est impressionnant ! Merci d'avoir pris le temps de rédiger tes recherches !
Donc déjà, pour n puissance de 2, tu as parfaitement raison, la généralisation se fait bien.
Pour les autres cas, voici le petit truc qui te manquait, et je précise un peu le vocabulaire : on parle en fait d'un graphe : chaque sommet est un plateau, deux sommets sont reliés si on peut passer d'un à l'autre avec exactement un déplacement, et l'objectif est donc de faire en sorte que chaque sommet ait un voisin associé à n'importe quelle case du plateau.
Or un sommet a toujours exactement n voisins. Un sommet associé à 1 permet donc de couvrir exactement n sommets (il permet à n sommets d'avoir un voisin associé à 1, quoi). Il faut donc 2^n / n sommets associé à 1 pour tous les couvrir, au moins. De même, il faut 2^n / n sommets associés à 2, etc. Et le seul moyen d'avoir ça, c'est que 2^n soit divisible par n, ce qui arrive très exactement si n est une puissance de 2.
Pour ceux qui préfèrent une démonstration uniquement en combinatoire, sans graphe (c'est exactement la même démo, c'est juste les outils qui changent) :
Déjà en reprenant les notations que j'ai introduite, on considère qu'il existe une fonction f résolvant le problème. On va noter E l'ensemble de toutes les positons du plateau (il a 2^n éléments), et E_i = {Y | f(Y) = i}. On va montrer que le cardinal de E_i est exactement 2^n/n (ce qui prouvera que 2^n/n est entier : un cardinal est toujours entier).
On choisit un i. pour n'importe quel Y dans E_i, {X | X est à un mouvement de Y} a pour cardinal n (on a n mouvements, qui mènent à les position différentes). Par ailleurs, la réunion suivante : U_(Y élément de E_i) {X | X est à un mouvement de Y} est égale à E : toute position est à un mouvement d'une position renvoyant i. Le cardinal d'un union est inférieur à la somme des cardinaux : somme_(Y élément de E_i) card {X | X est à un mouvement de Y} >= 2^n et somme_(Y élément de E_i) card {X | X est à un mouvement de Y} = somme_(Y élément de E_i) n = n * card E_i L'on en ressort n * card E_i >= 2^n, soit card E_i >= 2^n/n.
Par ailleurs, U_i E_i = E, et il s'agit d'une union disjointe ; le cardinal de E est donc exactement la somme des cardinaus des E_i : 2^n = somme_(i entre 0 et n-1) card E_i >= somme_(i entre 0 et n-1) 2^n/n = n* 2^n/n = 2^n Le seul cas d'égalité possible dans la précédente inégalité correspond au cas où chaque card E_i vaut exactement 2^n/n.
On a donc établi que 2^n/n est entier. La fin est de l’arithmétique de base : les seuls diviseurs de 2^n sont les puissance de 2.