Sujet
Les damiers
Considérons un damier rectangulaire formé de cases noires et blanches. Découpons-le en \(n\) rectangles en respectant les cases avec un découpage satisfaisant aux conditions suivantes :- Chaque rectangle est formé d'autant de cases blanches que de cases noires.
- Il n'y a pas deux rectangles ayant le même nombre de cases blanches.
Dans la suite de l'exercice, pour un découpage répondant aux deux conditions précédentes :
- on note \(a_{1}, a_{2}, \ldots a_{n}\), avec \(a_{1}
- on appelle «décomposition possible » la liste ordonnée \(\left(a_{1}, a_{2}, \ldots, a_{n}\right)\).
Exemple :
( \(1,3,4\) ) constitue une décomposition possible d'un damier carré de \(4 \times 4\) cases.
- Considérons un damier de dimensions : 6 cases en largeur et 7 cases en longueur.
(a) Trouver une décomposition possible en trois rectangles.
(b) La liste \((1,3,6,11)\) est-elle une décomposition possible ? Pourquoi?
(c) Déterminer le nombre maximum de rectangles que peut compter une décomposition possible du damier. - Considérons un damier de dimensions : 6 cases en largeur et 6 cases en longueur. Déterminer toutes les décompositions possibles ayant le nombre maximum de rectangles.
- Peut-on trouver une décomposition possible en 2011 rectangles pour un damier de dimensions 2010 cases sur 2011 cases?
- (a) \((4,7,10)\) est une décomposition possible en trois rectangles d'un damier de dimensions 6 et 7 .
(b) si dans une décomposition d'un damier de dimensions 6 et 7 , un rectangle est formé de 11 cases blanches donc de 22 cases, les seules dimensions possibles sont soit 1 et 22 , soit 2 et 11 . Ce qui n'est pas réalisable dans un damier de dimensions 6 et 7.
(c) La décomposition \((1,2,3,4,5,6)\) est une décomposition possible pour un damier de dimensions 6 et 7 . Les rectangles successifs comportent le plus petit nombre de cases blanches. C'est donc une décomposition maximale.
5 est bien un nombre premier. 3 est un nombre chanceux.
\(X=5\)
| \(n\) | 1 | 2 | 3 |
| \(n^{2}+n+5\) | 7 | 11 | 17 |
7, 11 et 17 étant des nombres premiers, 5 est un nombre chanceux.
\(X=11\)
Pour \(X=11, X-2=9\), donc on doit appliquer l'algorithme de calcul pour \(n \in\{1,2, \ldots, 9\}\).
| \(n\) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| \(n^{2}+n+11\) | 13 | 17 | 23 | 31 | 41 | 53 | 67 | 83 | 101 |
Tous les nombres de la seconde ligne sont premiers, donc 11 est un nombre chanceux.
\(\boldsymbol{X}=\mathbf{7}\)
Pour \(n=1, n^{2}+n+7=9=3^{2}\) qui n'est pas premier. Cela suffit pour affirmer que \(\mathbf{7}\) n'est pas un nombre chanceux.
\(\boldsymbol{X}=\mathbf{1 3}\)
Pour \(n=1, n^{2}+n+13=15=3 \times 5\) qui n'est pas premier. Donc 13 n'est pas un nombre chanceux.
b. Soit \(X\) un nombre entier supérieur ou égal à 3 . Raisonnons par contraposition.
Supposons \(X\) pair. Alors, pour \(n=1 ; n^{2}+n+X=2+X\) donc \(n^{2}+n+X\) est un nombre pair supérieur ou égal à 5 . Le seul entier pair qui soit premier étant \(2, n^{2}+n+X\) n'est donc pas un nombre premier. Il en résulte que \(X\) n'est pas un nombre chanceux.
Ainsi, pour que \(X\) soit chanceux, il faut qu'il soit impair.
Remarque : Cette condition nécessaire n'est toutefois pas suffisante puisque 7, par exemple, n'est pas chanceux.
c. Il s'agit de mettre en œuvre un raisonnement par l'absurde.
Soit \(X\) un nombre chanceux. Supposons-le non premier.
Alors il existe deux entiers naturels \(Y\) et \(Z\) strictement supérieurs à 1 tels que \(X=Y Z\).
Il s'agit de prouver que \(Y \leqslant X-2\), c'est-à-dire que \(Y \leqslant Y Z-2\) ou encore \(2 \leqslant Y(Z-1)\).
Or, on sait que \(Y \geqslant 2\) et \(Z-1 \geqslant 1\), donc \(2 \leqslant Y(Z-1)\) soit \(Y \leqslant X-2\).
\(X\) étant chanceux et \(Y \in\{2,3, \ldots, X-2\}\), on sait alors, en appliquant l'algorithme de calcul pour \(n=Y\), que \(Y^{2}+Y+X\) est premier. Or \(Y^{2}+Y+X=Y(Y+1+Z)\). Comme \(Y \geqslant 2\) et \(Y+1+Z \geqslant 2\), ceci est absurde.
Par suite, si \(X\) est un nombre chanceux, alors il est premier.
Remarque : Cette condition nécessaire n'est pas non plus suffisante puisque 7, par exemple, n'est pas chanceux.
d. Si \(X\) est chanceux; alors, en appliquant l'algorithme, pour \(n=2,2+X\) est un nombre premier.
4. On sait qu'il existe seulement 5 nombres chanceux et les quatre premiers sont \(3,5,11\) et 17 .
Le cinquième, appelé \(A\) est nécessairement premier, d'après 3 c. Il est inférieur à 50 d'après l'énoncé et \(A+2\) est premier d'après 3d. Donc \(A\) ne peut être que 29 ou 41 .
Pour \(A=29\), on applique le programme pour \(n=2: 2^{2}+2+29=35=7 \times 5\). Donc 29 n'est pas un nombre chanceux.
Le cinquième nombre chanceux est donc 41.