Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

“Mais c’est impossible !”Exemples d’utilisation d’invariants
Lycée Saint-Exupéry, 4 février 2008

Jérôme Germoni (université Lyon 1)

Lycée Saint-Exupéry, 4 février 2008

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Deux types de problèmes
1

On veut classer une catégorie d’objets ;Une démarche possible : trouver une quantité facile à calculer, qui
ne change pas par les transformations élémentaires.
Lycée Saint-Exupéry, 4 février 2008

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Deux types de problèmes
1

On veut classer une catégorie d’objets ; plus modestement, onveut séparer deux objets d’une même catégorie :Une démarche possible : trouver une quantité facile à calculer, qui
ne change pas par les transformations élémentaires.
Lycée Saint-Exupéry, 4 février 2008

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Deux types de problèmes
1

On veut classer une catégorie d’objets ; plus modestement, onveut séparer deux objets d’une même catégorie :Une démarche possible : trouver une quantité facile à calculer, qui
ne change pas par les transformations élémentaires.
Lycée Saint-Exupéry, 4 février 2008

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Deux types de problèmes
1

On veut classer une catégorie d’objets ; plus modestement, onveut séparer deux objets d’une même catégorie :2On essaie de faire quelque chose, et on n’y arrive pas.
Mais pour se convaincre que ce n’est pas possible, il y aurait
trop de cas à tester. Que faire ?

Une démarche possible : trouver une quantité facile à calculer, qui
ne change pas par les transformations élémentaires.
Lycée Saint-Exupéry, 4 février 2008

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Question
Trois cas, deux invariants

Plan
1

PavageQuestion
Trois cas, deux invariants

2

De nouveaux nombres ?
Deux nombres
Quatre nombres3

Le solitaire agrandi ?
Solitaire classique
Solitaire agrandi
Retour au solitaire classique

Lycée Saint-Exupéry, 4 février 2008

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Question
Trois cas, deux invariants

La question
Paver un rectangle écorné par des dominos 1 × 2

Lycée Saint-Exupéry, 4 février 2008

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Question
Trois cas, deux invariants

Un exemple
Rectangle de départ : 6 × 9012
Lycée Saint-Exupéry, 4 février 2008

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Question
Trois cas, deux invariantsCas de deux côtés impairs
Rectangle de départ : a × b, avec a et b impairs

Lycée Saint-Exupéry, 4 février 2008

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Question
Trois cas, deux invariantsCas de deux côtés impairs
Rectangle de départ : a × b, avec a et b impairs

Impossible ! L’aire à recouvrir est impaire.
Lycée Saint-Exupéry, 4 février 2008

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Question
Trois cas, deux invariantsCas de d’un côté pair et un côté impair
Rectangle de départ : a × b, avec a pair et b impair

Lycée Saint-Exupéry, 4 février 2008

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Question
Trois cas, deux invariantsCas de d’un côté pair et un côté impair
Rectangle de départ : a × b, avec a pair et b impair

Possible !
Lycée Saint-Exupéry, 4 février 2008

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Question
Trois cas, deux invariantsCas de deux côtés pairs
Rectangle de départ : a × b, avec a et b pairs

Lycée Saint-Exupéry, 4 février 2008

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Question
Trois cas, deux invariantsCas de deux côtés pairs
Rectangle de départ : a × b, avec a et b pairs

Lycée Saint-Exupéry, 4 février 2008

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Question
Trois cas, deux invariantsCas de deux côtés pairs
Rectangle de départ : a × b, avec a et b pairs

Lycée Saint-Exupéry, 4 février 2008

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Question
Trois cas, deux invariantsCas de deux côtés pairs
Rectangle de départ : a × b, avec a et b pairs

Lycée Saint-Exupéry, 4 février 2008

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Question
Trois cas, deux invariantsCas de deux côtés pairs
Rectangle de départ : a × b, avec a et b pairs

Vraiment pas possible ?
Lycée Saint-Exupéry, 4 février 2008

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Question
Trois cas, deux invariantsCas de deux côtés pairs : indication
Rectangle de départ : a × b, avec a et b pairs

Lycée Saint-Exupéry, 4 février 2008

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Question
Trois cas, deux invariantsCas de deux côtés pairs : indication
Rectangle de départ : a × b, avec a et b pairs

Lycée Saint-Exupéry, 4 février 2008

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Question
Trois cas, deux invariantsCas de deux côtés pairs : indication
Rectangle de départ : a × b, avec a et b pairs

Lycée Saint-Exupéry, 4 février 2008

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Question
Trois cas, deux invariantsCas de deux côtés pairs : preuve !
Rectangle de départ : a × b, avec a et b pairs

Invariant :nb cases
hachuréesLycée Saint-Exupéry, 4 février 2008

−Invariants

nb caseslissesPavage
De nouveaux nombres ?
Le solitaire agrandi ?

Question
Trois cas, deux invariantsCas de deux côtés pairs : preuve !
Rectangle de départ : a × b, avec a et b pairs
Invariant :nb caseshachuréesLycée Saint-Exupéry, 4 février 2008

−Invariants

nb caseslisses=2

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Question
Trois cas, deux invariants

Une utilisation d’un invariant
Imaginons un système qui peut être dans différents états, on passede l’un à l’autre par des transformations.
Prouver l’impossibilité
Pour prouver qu’on ne peut pas passer d’un état à un autre sansessayer toutes les possibilités :1

on exhibe un invariant (facile à calculer) ;2

on le calcule dans la situation initiale ;3

on le calcule dans la situation finale ;Si ces deux valeurs sont différentes, c’est gagné.
 
nb cases
nb cases
Ex : parité du nb de cases ;−hachuréeslisses
Lycée Saint-Exupéry, 4 février 2008

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Deux nombres
Quatre nombres

Plan1

PavageQuestion
Trois cas, deux invariants

2

De nouveaux nombres ?
Deux nombres
Quatre nombres3

Le solitaire agrandi ?
Solitaire classique
Solitaire agrandi
Retour au solitaire classique

Lycée Saint-Exupéry, 4 février 2008

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Deux nombres
Quatre nombres

Une arithmétique simplifiéeCe qui a été crucial :pair + pair = pair

pair × pair = pairpair + impair = impair

pair × impair = pair

impair + pair = impair

impair × pair = pair

impair + impair = pair

Lycée Saint-Exupéry, 4 février 2008

impair × impair = impair

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Deux nombres
Quatre nombres

Une arithmétique simplifiéeSimplifions les notations : pair ; 0, impair ; 1.
0+0 = 00×0 = 00+1 = 10×1 = 01+0 = 1

1×0 = 01+1 = 01×1 = 1

Lycée Saint-Exupéry, 4 février 2008

Invariants

PavageDe nouveaux nombres ?
Le solitaire agrandi ?

Deux nombres
Quatre nombres

Le paradis des distraits
Des calculs simplifiés !
Plus d’erreurs de signe
Pour a, b ∈ {0, 1}, on peut écrire :2 × a = a + a = 0.
En particulier :−a = a.

Lycée Saint-Exupéry, 4 février 2008

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Deux nombres
Quatre nombres

Le paradis des distraits
Des calculs simplifiés !
Plus d’erreurs de signe, plus de double produit oublié !
Pour a, b ∈ {0, 1}, on peut écrire :2 × a = a + a = 0.
En particulier :−a = a.
Amusant : dans cet ensemble de nombres :(a + b)2 = a2 + b 2 .

Lycée Saint-Exupéry, 4 février 2008

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Deux nombres
Quatre nombres

Quelques équations

1

Cherchons x ∈ {0, 1} tel que x 2 = 1 :x 2 + 1 = 0 ⇐⇒ (x + 1)2 = 0 ⇐⇒ x + 1 = 0 ⇐⇒ x = 1.

Lycée Saint-Exupéry, 4 février 2008

Invariants

PavageDe nouveaux nombres ?
Le solitaire agrandi ?

Deux nombres
Quatre nombres

Quelques équations

1

Cherchons x ∈ {0, 1} tel que x 2 = 1 :x 2 + 1 = 0 ⇐⇒ (x + 1)2 = 0 ⇐⇒ x + 1 = 0 ⇐⇒ x = 1.

2

Cherchons α ∈ {0, 1} tel que α2 = α + 1 :02 6= 0 + 1,Lycée Saint-Exupéry, 4 février 2008

12 6= 1 + 1.

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Deux nombres
Quatre nombres

Quelques équations

1

Cherchons x ∈ {0, 1} tel que x 2 = 1 :x 2 + 1 = 0 ⇐⇒ (x + 1)2 = 0 ⇐⇒ x + 1 = 0 ⇐⇒ x = 1.

2Cherchons α ∈ {0, 1} tel que α2 = α + 1 :02 6= 0 + 1,12 6= 1 + 1.

Pas de α tel que α2 = α + 1 ? On en crée un.

Lycée Saint-Exupéry, 4 février 2008

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Deux nombres
Quatre nombres

Quelques calculs
Addition : très facile !
α + 0 = α, α + 1 = α + 1, α + (α + 1) = 1...

Lycée Saint-Exupéry, 4 février 2008

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Deux nombres
Quatre nombres

Quelques calculs
Addition : très facile !
α + 0 = α, α + 1 = α + 1, α + (α + 1) = 1...
Multiplication : pas dur !
α2 = α + 1,(α + 1)2 = α2 + 1 = α + 1 + 1 = α,α(α + 1) = α2 + α = α + 1 + α = 1.

Lycée Saint-Exupéry, 4 février 2008

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Deux nombres
Quatre nombres

Quelques calculsAddition : très facile !
α + 0 = α, α + 1 = α + 1, α + (α + 1) = 1...
Multiplication : pas dur !
α2 = α + 1,(α + 1)2 = α2 + 1 = α + 1 + 1 = α,α(α + 1) = α2 + α = α + 1 + α = 1.
Et même la division (sauf par 0...) :
1
= 1,1

1
= α + 1,αLycée Saint-Exupéry, 4 février 2008

1= α.
α+1

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Solitaire classique
Solitaire agrandi
Retour au solitaire classiquePlan1Pavage
Question
Trois cas, deux invariants

2De nouveaux nombres ?
Deux nombres
Quatre nombres3

Le solitaire agrandi ?
Solitaire classique
Solitaire agrandi
Retour au solitaire classique

Lycée Saint-Exupéry, 4 février 2008

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Solitaire classique
Solitaire agrandi
Retour au solitaire classique

Le jeu du solitaire

But : éliminer toutes les pierres, sauf une.

Lycée Saint-Exupéry, 4 février 2008

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Solitaire classique
Solitaire agrandi
Retour au solitaire classique

Le jeu du solitaire

But : éliminer toutes les pierres, sauf une.

Lycée Saint-Exupéry, 4 février 2008

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Solitaire classique
Solitaire agrandi
Retour au solitaire classique

Le jeu du solitaire

But : éliminer toutes les pierres, sauf une.

Lycée Saint-Exupéry, 4 février 2008

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Solitaire classique
Solitaire agrandi
Retour au solitaire classique

Le jeu du solitaire

But : éliminer toutes les pierres, sauf une.

Lycée Saint-Exupéry, 4 février 2008

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Solitaire classique
Solitaire agrandi
Retour au solitaire classique

Le jeu du solitaire

But : éliminer toutes les pierres, sauf une.

Lycée Saint-Exupéry, 4 février 2008

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Solitaire classique
Solitaire agrandi
Retour au solitaire classique

Le jeu du solitaire

But : éliminer toutes les pierres, sauf une.

Lycée Saint-Exupéry, 4 février 2008

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Solitaire classique
Solitaire agrandi
Retour au solitaire classique

Le jeu du solitaire agrandi

But : montrer qu’on ne peut pas finir avec une seule pierre

Lycée Saint-Exupéry, 4 février 2008

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Solitaire classique
Solitaire agrandi
Retour au solitaire classique“Energie” d’une configuration
On numérote lesdiagonales

1
α1+α1
α
1+α1···

Lycée Saint-Exupéry, 4 février 2008

InvariantsChaque pierre
contribue selon sa
diagonalePavage
De nouveaux nombres ?
Le solitaire agrandi ?

Solitaire classique
Solitaire agrandi
Retour au solitaire classique“Energie” d’une configuration
On numérote lesdiagonales

1α
1+α
1α1+α
1···

Lycée Saint-Exupéry, 4 février 2008

Invariants

Chaque pierre
contribue selon sa
diagonale
Energie :E = 1+2×α+2×
1 + (1 + α) + 2 × 1 + α

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Solitaire classique
Solitaire agrandi
Retour au solitaire classique“Energie” d’une configuration
On numérote lesdiagonales

1α1+α1α1+α1···

Lycée Saint-Exupéry, 4 février 2008

Invariants

Chaque pierre
contribue selon sadiagonale
Energie :E = 1+2×α+2×
1 + (1 + α) + 2 × 1 + α
E = 1 + (1 + α) + α
E =0Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Solitaire classique
Solitaire agrandi
Retour au solitaire classiqueInvariance de l’énergie (1)Avant la prise :énergie avant : 1 + α
α 1 1+α

Lycée Saint-Exupéry, 4 février 2008

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Solitaire classique
Solitaire agrandi
Retour au solitaire classiqueInvariance de l’énergie (1)Avant la prise :énergie avant : 1 + α
α 1 1+αAprès la prise :énergie après : 1 + α
α 1 1+α

Lycée Saint-Exupéry, 4 février 2008

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Solitaire classique
Solitaire agrandi
Retour au solitaire classiqueInvariance de l’énergie (2)En général...
Avant la prise :énergie avant : a + bab cAprès la prise :énergie après : cab cMais a + b + c = 1 + α + (1 + α) = 0, donc a + b = c.

Lycée Saint-Exupéry, 4 février 2008

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Solitaire classique
Solitaire agrandi
Retour au solitaire classique

Energie de la configuration de départ

1
α1+α1
α1+α1···

Lycée Saint-Exupéry, 4 février 2008

Invariants

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Solitaire classique
Solitaire agrandiRetour au solitaire classique

Energie de la configuration de départ

1
α1+α1
α1+α1···

Lycée Saint-Exupéry, 4 février 2008

Invariants

Energie totale : 0Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Solitaire classique
Solitaire agrandi
Retour au solitaire classique

Energie de la configuration de départ

1
α1+α1
α1+α1···

Lycée Saint-Exupéry, 4 février 2008

Invariants

Energie totale : 0
On ne peut donc pas
terminer avec une seulepierre !

Pavage
De nouveaux nombres ?
Le solitaire agrandi ?

Solitaire classique
Solitaire agrandi
Retour au solitaire classique

A vous de jouer...
On ne peut gagner que sur une des cases cerclées.

Lycée Saint-Exupéry, 4 février 2008

Invariants