Bonsoir,
Je voudrais que quelqu'un me dise (et m'explique aussi =)) quelle est la fonction (ou les) à la base du jeu de Nim (ou jeux des allumettes).
Je m'explique: Il y a 2joueurs, le jeu consiste à placer un certain nombre d'allumettes sur une table et les joueurs doivent un à un retirer 1, 2 ou 3 allumettes, le perdant est celui qui récupère la dernière allumette.
Il y a donc une astuce: quelque soit le nombre initial d'allumettes, il faut s'arranger pour en laisser 4x+1 ensuite, quand l'adversaire en retirera 1, on en retirera 3, quand il en retirera 2 on en retirera 2 aussi et quand il en retirera 3 on en retirera 1 et c'est gagné! Plus simplement, la somme de son retrait et du mien doit être égale à 4, ainsi, après 4*x retraits il restera 1 allumette et c'est lui qui la récupèrera .
Voila ^^ Merci d'avance
c'est plus une histoire de congruence 1 modulo 4 qu'une histoire de fonction...
quelle serait la variable? le nombre de départ?
le nombre d'allumettes enlevé en premier? en second?
En fait je disais fonction un peu comme ça, parce que ce jeu m'intriguait et en posant la question au prof, il m'a envoyée balader
Pourrais-tu m'expliquer un peu plus cette notion de congruence ? Et comment s'applique-t-elle dans ce cas là ?
Merci
En fait, au jeu de Nim, si on commence le prmir (et qu'on sait faire un peu de math) on est spur de gagner.
Oui, c'est ce que j'ai dit un peu plus haut mais je voudrais l'explication mathématiques ^^ et garnouille à parlé de congruence...
nan, désolé 1 Schumi 1, mais c faux:
-si on commence le premier et que le nombre d'allumette d'est pas égal à: 1+4n (ou n est un entier quelquonque) on est sur de gagner en mettant le nombre d'allumette à 1+4n
ex: il y 18 allumette, or 1+4x4=17, donc, si tu enlève une allumette, tu est sur de gagner, car si il en enlève une tu en enlève 3, si il en enlève 2, tu en enlève 2; et 3, tu en enlève 1, comme ca, tu arrivera a 5, il en enlève autant qu'il vux, tu pourra toujours arriver à en enlevé autant qu'il faut pour qu'il en reste 1! tu as gagné
-si on commence est que le nombre est égal à 1+4n, alors là, si l'autre personne connait la technique, t'es mort!
voila, je suis quasi sur que c juste!
La notion de congruence est liée à la notion de divisibilité.
Soit, a, b,et n trois entiers
On dit que a est congru a b modulo n (je sais, c'est un peu barbare), signifie que n divise (a-b)
On note cela comme ca:
>> simon92,
Si si, il y bien une méthode gagante, mais elle n'est pas en modulo 4.
Elle est en modulo 5.
Regarde:
Au premier tour, tu prends 4.
Après, tu t'arranges à chaque tour pour que la somme de ce qu'il prend et que celle que tu prends juste après lui soit 5.
Et là, tu gagnes.
Exemple.
Toi (1): 4
Lui (1): 2
Toi (2): 3
Lui (2): 4
Toi (3): 1
...
Comme , t'es sûr de gagner.
Ayoub.
Merci Schumi pour cet éclaircissement la notion de congruence je n'en ai jamais encore entendu parler ^^ mais je pense avoir compris
Donc dans le cas présent, on pourrait prendre 5 pour a, -1 pour b, en divisant par 4 et écrire:
5-1(mod4)
???
Maths 7378, tu donnes toi-même une bonne explication :
5=4*1 + 1 donc 51 (modulo 4)
9=4*2 + 1 donc 91 (modulo 4)
13=4*3 + 1 donc 131 (modulo 4)
4x+11 (moulo 4) avec x entier bien sûr...
@ Schumi:
Ah lol oui c'est vrai ^^
Et donc en fait c'est cette expression mathématique qui traduit le fait que quelque soit le nombre 4x+1 de départ suite aux retraits consécutifs, à la fin on obtiendra forcément 1 ?
@ Garnouille: lol non je voulais juste traduire ça mathématiquement, enfin je voulais savoir quelle était la notion mathématique à la base de tout ça, et apparemment, c'est la notion de congruence ^^
@ Schumi:
Je te demandais si c'est donc bien la notion de congruence qui permet de résumer le jeu de Nim ?
@ Garnouille:
Merci pour ces exemples, je saisis mieux
lol je vois ^^
Merci pour tout en tous cas! Comme ça, je pourrais aller énerver mon prof de maths avec ça
Dernière question et promis j'arrête : C'est en quelle année qu'on aborde la congruence ??
Non, au jeu de nim, on peut enlever jusqu'à quatre, enfin, je crois bien.
Si effectivement, on ne peut enlever 4, alors, ca ne marche plus, faut que je trouve une autre méthode.
A vérifier.
Ayoub.
Math737, deux remarques :
1) la notion de congruence correspond au reste dans la division euclidienne
exemples :
*17 et 32 ont pour reste 2 dans la division euclidienne par 5, on dit qu'ils sont "congrus modulo 5" (ils ont le même reste qui est 2), ils aussi congus à 2 modulo 5 car 2 est son propre reste dans la division euclidienne par 5
* 100 et 19 sot congrus à 1 modulo 9 car le reste de 100 par 9 est 1, idem pour 19
on peut aussi dire que deux nombres sont congrus modulo 9 quand leur différence est un multiple de 9 (les restes se soustraient et comme ils sont égaux!...)
reprenons 100 et 19 : 100-19=81 qui est bien un multiple de 9
avec 17 et 32 qui sont congrus modulo 5, on a aussi leur différence multiple de 5, la preuve : 32-17=15 qui est bien multiple de 5
2) pour le jeu de Nim, je ne connais pas la règle exacte mais tu dis toi-même que si on arrive à laisser 4x+1 allumettes à son adversaire alors, on est sûr de pouvoir gagner à condition de faire en sorte d'enlever 4 allumettes au tour suivant (1+3 ou 2+2 ou 3+1)... avec la notion de congruence, à chaque tour, on doit laisser un nombre d'allumette(s) congru à 1 modulo 4 et le tour est joué... mais ce n'est pas toujours possible selon la position que l'on occuppe et selon le nombre d'allumettes au départ!...
Merci beaucoup Garnouille pour ces précisions !
Du coup, je me pose des questions que voici:
1)Est-ce le fait que le reste de la division euclidienne (par un même nombre n) soit le même pour deux nombres qui nous permet de dire que ces deux nombres sont congrus modulo n?
2) Peut-on dire que 3 ou 4 ou... nombres sont congrus modulo n? Ou cela ne fonctionne-t-il que pour des couples ?
3) Mise à part la précision, y a-t-il une différence quand on précise ou pas à quel nombre sont congrus x et y ?
Parce que dans ton exemple, tu dis que 17 et 32 sont congrus modulo 5 et tu rajoutes qu'ils sont également congrus à 2 modulo 5, y a-t-il une différence entre ces deux formulations?
4) Je ne saisis pas très bien quand tu dis que "deux nombres sont congrus modulo 9 quand leur différence est un multiple de 9 (les restes se soustraient et comme ils sont égaux!...)" en fait c'est surtout ce qui est entre parenthèses que je ne saisis pas ^^
PS1 Pour le jeux de Nim, même si l'on est 1er à jouer et que le nombre d'allumettes est déjà congru à 1 modulo 4, si notre adversaire n'est pas aussi doué que nous on peut toujours s'arranger pour gagner ^^
PS2 J'ai visité le lien ^^ Ca prouve bien que t'avais raison dès ton 1er post Tu ferais un bon prof de Maths à mon avis
Bah, tout compte fait, c pas plus dur.
Tu prends 3 au début, et puis tu t'arranges pour que ce qu'il prend au tour n et que tu prends au tour n+1 fasse 4.
oui, bien sûr Schumi, complète... je n'avais pas vu ta question... je rédigeais mon message!
salut à toi!...
Ce vois pas trop ce qu'on peut encore rajouter.
Bien fait, franchement bien.
Si on prend l'autre définition, c'est réglé en deux lignes exactement.
Ayoub.
Merci beaucoup Garnouille, vraiment !
Mais encore quelques petites questions
Le reste peut-il être nul ?
Et du coup, par exemple pour 9, tous ses multiples seraient congrus entre eux ?!
Ceci porte-t-il un nom spécial?
Oui, le reste peut être nul. dans ce cas, c'est le nombre lui même qui est un multiple de 9.
Par exemple:
En effet, 18-0=18 est divisible par 9
je confirme, tous les multiples de 9 sont congrus modulo 9 entre eux :
autres exemples :72999999 [9]
justification : ce sont des multiples de 9, le reste dans la division par 9 est 0
de plus tout miltiple de 9 est congru à 0 modulo 9
pas de nom "spécial" à mon avis, on a déjà les maultiples et les diviseurs dans ce cas...
Merci ^^
1) Donc je fais un petit récapitulatif :
Dire que a et congru à b modulo n signifie que le reste de la division euclidienne de a par n est le même que celui de la division euclidienne de b par n. Cela entraine le fait que le résultat de la soustraction a-b est un multiple de n.
Ai-je bien compris ?
2) Est-ce que ce sont les 2 uniques façons de caractériser les congruences ?
3) A l'écrit (je me base sur ce que j'ai vu dans ce topic) cela se présente comme ça:
ab (mod n) et ab [n] (laquelle est la plus juste entre ces deux ?)
ou bien comme ça:
n|(a-b) (dans ce cas là, que représente la barre ?)
Quand écrit-on la 1ère ou la 2nde et quand la 3ème ?
4) Sur la calculatrice comment peut-on retrouver la notion de congruence ? (la mienne est une TI-89)
Merci
Bonjour,
1) Tu as tout compris.
2) A ma connaissance, ce sont les deux seules (mais elles sont équivalentes)
3) Les trois sont bonnes.
Quand tu écris en congruences, tu utilises les deux premières.
La troisième, juste quand on fait des petites raisonnement.
La barre signifie "divise"
4) En général, on a pas besoin de calculatrice. En spé, c'est plus du raisonnement que du calcul.
Merci ^^
3) Question bête mais...
La barre qui signifie "divise" est un symbole mathématique, ou bien l'équivalent du "slash" sur le clavier ?
4) En fait j'ai vu sur ma calculatrice que la fonction modulo existait, je tape mod(7,3) j'obtiens 1, ainsi 7 est congru à 1 modulo 3, mais quand je tape mod(7,-3) j'obtiens -2 ce qui voudrait dire que 7 est congru à -2 modulo -3 ce qui est vrai vu que 7+2=9 et 9 est divisible par -3, mais le reste de 7/-3 est-il le même que celui de -2/3 ?? Même chose quand je tape mod(-7,3) j'obtiens 2 et enfin quand je tape mod(-7,-3) j'obtiens -1...
5) J'ai fais quelques recherches sur la congruences, et je suis tombée ici et je ne saisis pas très bien la remarque tout en bas, puisque diviser revient à multiplier par l'inverse donc si la multiplication est autorisée, je ne vois pas pour la division ne le serait pas...
Merci
3) Question bête mais...
La barre qui signifie "divise" est un symbole mathématique, ou bien l'équivalent du "slash" sur le clavier ?
c'est plutôt "|" que "/"
n | (a-b) se lit n divise (a-b) mais je ne sais pas si cette notation est acceptée partout
4) 7-2(mod-3)
7=(-3)(-2)+1
-2=(-3)*1+1
le reste est 1 mais celà demande de connaître la division euclidienne avec des nombres relatifs
division euclidienne de a par b dans :a=bq+r avec 0r< |b| (valeur absolue de b)
pour 5) il faut faire les démonstrations.. tu veux essayer?
commence par la multiplication
5) En fait on nous dit que si ab (p) alors pour tout c appartenant à
ac bc (p)
On multiplie donc par c
En multipliant par 1/c (ou en divisant par c) on obtiens bien ab (p)
Et dans la remarque on dit que la relation de congruence n'est pas compatible avec la division, c'est ce que je ne comprends pas très bien ...
si ab[p] alors a=b+kp soit a-b=kp
on multiplie par c, on obtient c(a-b)=kcp
ou ca-cb=kp danc ca et cb sont congrus modulo p
mais si on a ac=bc+kp
en voulant diviser par c : a=b+kp/c
et il se peut que kp ne soit pas divisible par c
le symbole de congruence ne se traite pas comme une égalité même si certaines propriétés fonctionnent de la même façon, pour être sûr, il faut reprendre les définitions
ab(mod p) signifie qu'il existe un entier k tel que a-b=kp ou a=b+kp
Merci ^^ mais...
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :