30
Maths for fun: Mathématiques des jeux et casse-têtes Laurent Fousse [email protected] 20 janvier 2009 [email protected] () Maths des jeux et casse-têtes 20 janvier 2009 1 / 25

Theorie Casse Tete Math

  • Upload
    maximin

  • View
    37

  • Download
    2

Embed Size (px)

DESCRIPTION

Théorie des jeux mathématiques

Citation preview

Page 1: Theorie Casse Tete Math

Maths for fun: Mathématiques des jeux etcasse-têtes

Laurent Fousse [email protected]

20 janvier 2009

[email protected] () Maths des jeux et casse-têtes 20 janvier 2009 1 / 25

Page 2: Theorie Casse Tete Math

Plan

1 Étude de l’énigme des lumìèresRappel de la définitionModélisation

2 TaquinPrésentationFormalisation

3 Cast O’GearPrésentationModélisation

4 Procédure Sift

[email protected] () Maths des jeux et casse-têtes 20 janvier 2009 2 / 25

Page 3: Theorie Casse Tete Math

Plan

1 Étude de l’énigme des lumìèresRappel de la définitionModélisation

2 TaquinPrésentationFormalisation

3 Cast O’GearPrésentationModélisation

4 Procédure Sift

[email protected] () Maths des jeux et casse-têtes 20 janvier 2009 3 / 25

Page 4: Theorie Casse Tete Math

Un petit jeu à étudier1

On considère un clavier magique 3x3 :

Chaque case peut cycler sur 3couleurs ;Toucher une case fait avancer sacouleur et celle de ses voisines ;Le but est de rendre le claviermonochrome ;Est-ce que toutes les positionsinitiales sont solubles ?Quelle est la stratégie ?

1Tiré de Black & White de Lionhead, sans doute un [email protected] () Maths des jeux et casse-têtes 20 janvier 2009 4 / 25

Page 5: Theorie Casse Tete Math

Un petit jeu à étudier1

On considère un clavier magique 3x3 :

Chaque case peut cycler sur 3couleurs ;Toucher une case fait avancer sacouleur et celle de ses voisines ;Le but est de rendre le claviermonochrome ;Est-ce que toutes les positionsinitiales sont solubles ?Quelle est la stratégie ?

1Tiré de Black & White de Lionhead, sans doute un [email protected] () Maths des jeux et casse-têtes 20 janvier 2009 4 / 25

Page 6: Theorie Casse Tete Math

Un petit jeu à étudier1

On considère un clavier magique 3x3 :

Chaque case peut cycler sur 3couleurs ;Toucher une case fait avancer sacouleur et celle de ses voisines ;Le but est de rendre le claviermonochrome ;Est-ce que toutes les positionsinitiales sont solubles ?Quelle est la stratégie ?

1Tiré de Black & White de Lionhead, sans doute un [email protected] () Maths des jeux et casse-têtes 20 janvier 2009 4 / 25

Page 7: Theorie Casse Tete Math

Lights Out Puzzle

1 1

1

1 1

1

1

[email protected] () Maths des jeux et casse-têtes 20 janvier 2009 5 / 25

Page 8: Theorie Casse Tete Math

Lights Out Puzzle

1 1

1

1 1

1

1

[email protected] () Maths des jeux et casse-têtes 20 janvier 2009 5 / 25

Page 9: Theorie Casse Tete Math

Lights Out Puzzle

1 1

1

1 1

1

1

[email protected] () Maths des jeux et casse-têtes 20 janvier 2009 5 / 25

Page 10: Theorie Casse Tete Math

Lights Out Puzzle

1 1

1

1 1

1

1

[email protected] () Maths des jeux et casse-têtes 20 janvier 2009 5 / 25

Page 11: Theorie Casse Tete Math

Plan

1 Étude de l’énigme des lumìèresRappel de la définitionModélisation

2 TaquinPrésentationFormalisation

3 Cast O’GearPrésentationModélisation

4 Procédure Sift

[email protected] () Maths des jeux et casse-têtes 20 janvier 2009 6 / 25

Page 12: Theorie Casse Tete Math

Modélisation

Exemple : n = 3, c = 3.

A =

1 1 0 1 0 0 0 0 01 1 1 0 1 0 0 0 00 1 1 0 0 1 0 0 01 0 0 1 1 0 1 0 00 1 0 1 1 1 0 1 00 0 1 0 1 1 0 0 10 0 0 1 0 0 1 1 00 0 0 0 1 0 1 1 10 0 0 0 0 1 0 1 1

det(A) = −7

[email protected] () Maths des jeux et casse-têtes 20 janvier 2009 7 / 25

Page 13: Theorie Casse Tete Math

Modélisation

0 1 2 0 1 2

1 0 2

0 1 2

X0 =

012102012

; A−1 =

2 1 2 1 1 0 2 0 01 1 1 1 1 1 0 2 02 1 2 0 1 1 0 0 21 1 0 1 1 2 1 1 01 1 1 1 0 1 1 1 10 1 1 2 1 1 0 1 12 0 0 1 1 0 2 1 20 2 0 1 1 1 1 1 10 0 2 0 1 1 2 1 2

A−1X0 =

022101022

[email protected] () Maths des jeux et casse-têtes 20 janvier 2009 8 / 25

Page 14: Theorie Casse Tete Math

Plan

1 Étude de l’énigme des lumìèresRappel de la définitionModélisation

2 TaquinPrésentationFormalisation

3 Cast O’GearPrésentationModélisation

4 Procédure Sift

[email protected] () Maths des jeux et casse-têtes 20 janvier 2009 9 / 25

Page 15: Theorie Casse Tete Math

Présentation

Parentée disputée : Noyes Palmer Chapman (1874)

13 14 15

9 10

5 6 8

1 2 3 4

1211

7

[email protected] () Maths des jeux et casse-têtes 20 janvier 2009 10 / 25

Page 16: Theorie Casse Tete Math

Présentation

Parentée disputée : Noyes Palmer Chapman (1874)

13 14 15

9 10

5 6 8

1 2 3 4

12

11

7

[email protected] () Maths des jeux et casse-têtes 20 janvier 2009 10 / 25

Page 17: Theorie Casse Tete Math

Présentation

Parentée disputée : Noyes Palmer Chapman (1874)

13 14 15

9 10

5 6 8

1 2 3 4

12

11

7

[email protected] () Maths des jeux et casse-têtes 20 janvier 2009 10 / 25

Page 18: Theorie Casse Tete Math

Présentation

Parentée disputée : Noyes Palmer Chapman (1874)

13 14 15

9 10

5 6 8

1 2 3 4

12

117

[email protected] () Maths des jeux et casse-têtes 20 janvier 2009 10 / 25

Page 19: Theorie Casse Tete Math

Position soluble ?

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15

11 2 8 9

5 7 10 4

12 3 6 1

13 14 15

[email protected] () Maths des jeux et casse-têtes 20 janvier 2009 11 / 25

Page 20: Theorie Casse Tete Math

Challenge de Noyes Chapman

Soluble ?

1 2 3 4

5 6 7 8

9 10 11 12

13 15 14

[email protected] () Maths des jeux et casse-têtes 20 janvier 2009 12 / 25

Page 21: Theorie Casse Tete Math

Plan

1 Étude de l’énigme des lumìèresRappel de la définitionModélisation

2 TaquinPrésentationFormalisation

3 Cast O’GearPrésentationModélisation

4 Procédure Sift

[email protected] () Maths des jeux et casse-têtes 20 janvier 2009 13 / 25

Page 22: Theorie Casse Tete Math

Formalisation

État du jeuOn identifie un état du jeu à la permutation de S16 des labels descases (la case 16 étant la case vide).

Signature d’une permutationIl existe un unique homomorphisme ε de Sn dans {−1,1} tel queε(t) = −1 si t est une transposition.

[email protected] () Maths des jeux et casse-têtes 20 janvier 2009 14 / 25

Page 23: Theorie Casse Tete Math

Formalisation

Permutation paireToute permutation se décompose comme produit de transpositions.On dit que p est une permutation paire si ε(p) = 1 et impaire sinon.Cette définition correspond à la parité du nombre de transpositionsutilisées pour écrire p.

Coup élémentaireUn coup élémentaire valide au jeu de taquin :

est représentable par un permutation des 16 cases (S16) ;échange deux cases voisines ;déplace la case vide d’une place dans une direction.

Un coup élémentaire est donc une transposition de S16.

[email protected] () Maths des jeux et casse-têtes 20 janvier 2009 15 / 25

Page 24: Theorie Casse Tete Math

Formalisation

État atteignableUn état atteignable du jeu est représenté par une permutation qui estégale au produit des transpositions effectuées.

InvariantPour un état du jeu de taquin, on définit v la parité de la position de lacase vide. Alors

ε(p) · v

est un invariant du jeu.

ThéorèmeLes positions solubles sont celles dont l’invariant est égal à celui de laposition résolue. Il existe 653837184000 positions solubles.

[email protected] () Maths des jeux et casse-têtes 20 janvier 2009 16 / 25

Page 25: Theorie Casse Tete Math

Plan

1 Étude de l’énigme des lumìèresRappel de la définitionModélisation

2 TaquinPrésentationFormalisation

3 Cast O’GearPrésentationModélisation

4 Procédure Sift

[email protected] () Maths des jeux et casse-têtes 20 janvier 2009 17 / 25

Page 26: Theorie Casse Tete Math

Présentation

[email protected] () Maths des jeux et casse-têtes 20 janvier 2009 18 / 25

Page 27: Theorie Casse Tete Math

Plan

1 Étude de l’énigme des lumìèresRappel de la définitionModélisation

2 TaquinPrésentationFormalisation

3 Cast O’GearPrésentationModélisation

4 Procédure Sift

[email protected] () Maths des jeux et casse-têtes 20 janvier 2009 19 / 25

Page 28: Theorie Casse Tete Math

Modélisation

Une étoile à cinq branches, dont deux présentant une encoche ;

Un cube (6 faces donc) sur lequel l’étoile peut se déplacer enfranchissant certaines arêtes ;Une face contient une encoche qu’il faut faire correspondre aveccelles de l’étoile.

[email protected] () Maths des jeux et casse-têtes 20 janvier 2009 20 / 25

Page 29: Theorie Casse Tete Math

Modélisation

Une étoile à cinq branches, dont deux présentant une encoche ;Un cube (6 faces donc) sur lequel l’étoile peut se déplacer enfranchissant certaines arêtes ;

Une face contient une encoche qu’il faut faire correspondre aveccelles de l’étoile.

[email protected] () Maths des jeux et casse-têtes 20 janvier 2009 20 / 25

Page 30: Theorie Casse Tete Math

Modélisation

Une étoile à cinq branches, dont deux présentant une encoche ;Un cube (6 faces donc) sur lequel l’étoile peut se déplacer enfranchissant certaines arêtes ;Une face contient une encoche qu’il faut faire correspondre aveccelles de l’étoile.

[email protected] () Maths des jeux et casse-têtes 20 janvier 2009 20 / 25