|
Solution au problème de février 2007
Pour Noël, Sophie et Sally ont reçu chacune un
casse-tête chinois.
Celui de Sophie est une grille 10 par 10 qu'on doit remplir avec un
certain nombre de pièces de dimensions 1 par 4 et d'autres
pièces de
dimensions 2 par 2. Celui de Sally est aussi une grille 10 par 10 qu'on
doit remplir avec un certain nombre de pièces 1 par 4 et
d'autres
pièces de dimensions 2 par 2. Sophie a complété
son casse-tête en 2
minutes et 30 secondes, et Sally a complété le sien en 4
minutes. Puis,
elles ont échangé leurs casse-têtes, Sophie a
complété celui de Sally
en 4 minutes et 20 secondes alors que Sally complétait celui de
Sophie
en 3 minutes et 12 secondes. Puis, elles sont revenues chacune à
son
casse-tête original, mais Sophie a donné une pièce
1 par 4 à Sally, qui
lui a donné en échange une pièce 2 par 2. Notre
question: Combien de
temps chacune va-t-elle maintenant prendre pour compléter son
casse-tête?
Nous avons reçu des solutions correctes de
| Saïd Amghibech
(Québec) |
|
Xavier Hecquet
(France) |
| Gérard Billion
(France) |
|
Normand
LaLiberté (Ontario) |
| Lou Cairoli
(États-Unis) |
|
Matthew Lim
(États-Unis) |
| K.A. Chandrashekara
(Inde) |
|
Jean-Luc Luyet
(Suisse) |
| Derek DiCesare (East
Kentwood) |
|
Mark Pilloff
(États-Unis) |
Philippe Fondanaiche
(France)
|
|
Ananda Raidu (Inde)
|
| Zac Friggstad
(Edmonton) |
|
Ryan Tifenbach
(Regina) |
Solution. Après l'échange des
pièces, il est impossible de compléter les
casse-têtes.
Notre problème de
février est une adaptation d'un problème du chapitre 2 (Coloring proofs) du
livre Problem solving
strategies de Arthur Engel (Problem Books in Mathematics,
Springer-Verlag, New York, 1998. x+403 pp.). En proie à une
humeur espiègle, nous avons omis de dire que Sophie et Sally ne
sont pas de vraies petites filles mais plutôt les chattes de la
voisine (voir figure 1), et nous avons adopté
une formulation qui laisse supposer
qu'il est toujours possible de compléter les
casse-têtes. En fait, si on suppose que la grille est
colorée comme dans la figure 2, on peut facilement se convaincre
qu'un tel casse-tête peut être complété
seulement si il comporte un nombre impair de pièces 2 par 2.
Figure 1
|
|
En effet, chaque pièce 1 par 4 couvre un nombre
pair de cases rouges (soit 0 ou 2). Puisqu'il y a en tout 25 cases
rouges, il doit y avoir un nombre impair de pièces 2 par 2 pour
couvrir toutes les cases rouges. Ainsi, les casse-têtes originaux
avaient chacun un nombre impair de pièces 2 par 2 (puisqu'ils
pouvaient être complétés). Mais après l'échange d'une pièce 1 par 4
pour une pièce 2 par 2, chaque casse-tête a un nombre pair
de pièces 2 par 2, donc il ne peut être
complété.
Amghibech et Cairoli nous ont envoyé
la solution ci-haut. Nos correspondants ont trouvé
plusieurs autres façons
originales de démontrer qu'un tel casse-tête
peut être complété seulement si il comporte un
nombre pair de pièces 1 par 4 (et donc un nombre impair de
pièces 2 par 2).
1 - Le coloriage de
Billion: ``Peignons maintenant verticalement chaque colonne (1
par 10) alternativement en blanc et en rouge, de cette manière
nous avons peint la même surface en blanc et en rouge. Enlevons
maintenant les pièces 2 par 2 et les pièces 1 par 4
placées horizontalement. Ces pièces avaient la même
surface peinte en blanc et en rouge, donc la surface restante peinte en
rouge est égale à la surface restante peinte en blanc.
Donc le nombre de pièces verticales blanches est égale au
nombre de pièces verticales rouges et donc le nombre de
pièces verticales est pair. On démontre de même que
le nombre de pièces horizontales est pair, et donc finalement
que le nombre de pièces 1 par 4 ne peut être que pair.''
Notons que cette solution démontre en plus que
dans tout recouvrement, le nombre de pièces 1 par 4 horizontales
est pair et le nombre de pièces 1 par 4 verticales est aussi
pair. Plusieurs de
nos correspondants sont arrivés à cette conclusion
à l'aide d'une démonstration combinatoire. En
particulier, Matthew Lim n'utilise pas le recouvrement, et sa démonstration
par induction peut servir à établir que
si un nombre impair k de pièces 1
par d sont disposées horizontalement sur une grille m par n,
alors une colonne de la grille est traversée par un nombre
impair de pièces.
En effet, l'énoncé est évident pour
k = 1. Supposons l'énoncé vrai pour tout nombre impair inférieur
à k, et disposons k pièces 1 par d horizontalement sur la
grille. Soit a, le nombre de pièces qui traverse la première
colonne. Si a est impair, alors bravo! Sinon, on retire les
pièces qui traversent la première colonne, pour obtenir
une disposition de k-a pièces sur la grille. Selon l'hypothèse
d'induction, on retrouve une colonne de la grille qui est
traversée par un nombre impair de pièces. Lorsqu'on
ajoute les pièces manquantes, ce nombre demeure impair, ce qui
prouve la validité de l'énoncé.
Par suite, dans tout recouvrement d'une grille par des pièces
1 par 4 et 2 par 2, les cases d'une colonne qui ne sont pas recouvertes
par des pièces 1 par 4 horizontales sont recouvertes par des pièces
1 par 4 verticales ou 2 par 2. Par conséquent, le nombre de
pièces horizontales qui traverse chaque colonne est pair. et de même,
le nombre de pièces
verticales qui traverse chaque ligne est pair.
2 - L'arithmétique
de
Laliberté: ``Considérons
que les coordonnées des cases de chaque grille vont de:
(0,
0), (1, 0), ..., (9, 0) - première rangée
(0,
1), (1, 1), ..., (9, 1) - deuxième rangée
...
(0,
9), (1, 9), ..., (9, 9) - dixième rangée
Comme
la somme des x de chaque rangée et des y de chaque colonne est
45, il est facile de voir que la somme des coordonnées,
ci-après SoCo, pour chaque grille est
SoCo = 900 ≡ 0 mod 4.
Désignons
par C22 une pièce de dimensions 2 par 2; par R14
une pièce de dimensions 1 par 4. Considérons
que les coordonnées d'un C22 sont: (x, y), (x+1,
y), (x, y+1), (x+1, y+1). Nous avons alors:
SoCo(
C22) = 4 ( x + y + 1 ) ≡ 0 mod 4.
Par
contre, les coordonnées d'un R14 horizontal sont: (x,
y),
(x+1, y), (x+2, y), (x+3, y); celles d'un R14 vertical: (x,
y), (x,
y+1), (x, y+2), (x, y+3). Dans les deux cas, nous avons:
SoCo
( R14) = 4 ( x + y ) + 6 ≡ 2 mod 4.
Comme
chaque pièce -C22 ou R14- couvre 4 cases,
il faut
un total de 25 pièces pour couvrir parfaitement une grille
–sans chevauchement, dépassement ni trou.
Soit
J un jeu de 2i C22 et (25 – 2i) R14; en d'autres
mots:
nombre pair de C22, nombre impair de R14. Nous
avons
alors:
SoCo
( J) ≡ 2i x 0 + (25 – 2i) x 2 mod 4. ≡ 2 mod 4.
C'est
dire qu'un tel jeu ne peut couvrir parfaitement une grille. Il faut
donc que J soit de la forme: (2i + 1) C22 et (25 – (2i +
1)) = (24 – 2i) = 2 x (12 – i) R14; nombre impair de C22,
nombre pair de R14. Car alors nous avons bien:
SoCo
( J) ≡ (2i + 1) x 0 + 2 x (12 – i) x 2 mod 4. ≡ 0 mod 4.''
3 - L'intégrale de Luyet:
``Considérons la fonction à deux variables
f(x,y) = sin( (Pi ×
x) / 2) × sin( (Pi × y) / 2)×(16 / Pi).
L'intérêt de cette fonction, c'est que si on
l'intègre sur un rectangle 1x4, elle s'annule toujours
à cause de la périodicité de 4 dans les deux
directions x et y des primitives.
En revanche, l'intégrale de cette fonction sur un carré
2x2 donnera soit 1 soit -1, en fonction des coordonnées de ce
carré. L'intégrale de la fonction sur le grand
carré 10x10 donne 1 si on place les sommets aux
coordonnées (0,0), (10,0) (10,10) et (0,10). Évidemment
l'intégrale sur le grand carré est la somme des
intégrales sur les différentes parties. Il y a donc
forcément un nombre impair de carrés 2x2. Comme il y a 25
pièces en tout, cela fait un nombre pair de rectangles 1x4.''
Commentaires: Dans
le même esprit, on trouve plusieurs démonstrations du
théorème suivant de de Bruijn:
Soit un rectangle T
décomposé en rectangles T1, T2,
..., Tn. Si chaque Ti a un côté de longueur entière, alors T a un
côté de longueur entière.
Béla Bollobás en donne quatre dans Modern Graph Theory
(Graduate Texts in Mathematics, 184. Springer-Verlag, New York, 1998.
xiv+394 pp.).
|
