Problèmes du mois
Feuille en cours
(exercices sélectionnés : 0)
Menu
Problème du mois de Décembre : Les pépites du chercheur d'Or
Jean-Eudes est un jeune chercheur d'or parti dans l'Ouest Américain pour y faire fortune. Au bout de quelque temps à creuser son filon, il parvient à extraire de nombreuses pépites. Mais son filon finit par s'épuiser, et il s'ennuie, pauvre garçon. Il décide donc de s'amuser un peu :
Il prend un lot de pépites d\'or - dont sa première pépite qui pèse au bas mot 352 grammes - et sa balance.

Il constate plusieurs choses :
- Il y a un nombre impair de pépites dans son lot;
- A chaque fois qu'il retire une pépite du lot, il arrive, en trifouillant un peu, à former deux tas de pépites qui ont le même poids et le même nombre de pépites.

Il parvient, sans les peser individuellement, à trouver le poids de chacune des pépites !

Comment a-t-il fait et surtout, quel est le poids de chacune des pépites ?
Prendre un vecteur colonne avec le poids $p_i$ de chacune des pépites puis déterminer une matrice carrée telle que ce vecteur appartienne à son noyau.
Problème du mois de Novembre :
Énoncé :
Correction :
Problème du mois de Octobre : La Sauterelle et l'Escalier
Énoncé :
Une sauterelle se trouve devant un escalier de $n$ marches où $n$ est un entier plus grand ou égal à $3$.
Son but est de monter sur la dernière marche de l'escalier et elle ne peut monter qu'une ou deux marches à chacun de ses sauts (et elle ne redescend jamais !).

Combien de possibilités, en fonction de $n$, la sauterelle a-t-elle d'atteindre son but ?
En notant $P(k)$ le nombre de possibilités d'atteindre la $k$-ieme marche, que peut-on dire de $P(n)$ en fonction des $P(i)$ avec $i=1,...,n-1$ ?
Correction :
Soit $k \in \mathbb{N}$. On note $P(k)$ l'ensemble des possibilités d'atteindre la $k$-ième marche de l'escalier. Le but est de déterminer $\#P(n)$ en fonction de $n$.

Formalisons ! Pour $k \in \mathbb{N}$, on peut caractériser une possibilité $p \in P(k)$ par un $i$-uplet $(p_1,...,p_i)$ tel que $i \in \mathbb{N}$; \[ p_i \in \{1,2\}\quad\text{et} \quad \sum_{j=1}^i p_j=k \] Ici, les $p_j$ représentent chaque saut de $1$ ou $2$ marches et leur somme doit valoir $k$ (car il s'agit d'une possibilité d'atteindre la $k$-ième marche). De plus, pour une telle possibilité $p=(p_1,...,p_i)$, on a $E(k/2) \leqslant i \leqslant k$ car $i \leqslant \sum p_j \leqslant 2i$.

Ainsi, on a :
\[ P(k)=\{(p_1,...,p_i) \; | \; i \in [\!\!\![\; E(k/2), k \;]\!\!\!]\;,\; p_j \in \{1,2\},\; \sum p_j=k \} \subset \bigcup_{i= E(k/2)}^k \{1,2\}^i \] Par exemple, $P(3)=\{(1,2),(2,1),(1,1,1)\}$.


Deux possibilités s'offrent à nous désormais pour déterminer $\#P(n)$ :

1ere possibilité : On exprime $\#P(n)$ en fonction des $\#P(k)$ avec $k \leqslant n$ :
Intuitivement, on remarque que pour aller sur la $n$-ième marche, on vient soit de la marche $n-1$, soit de la marche $n-2$, donc on conjecture que $\#P(n)=\#P(n-1)+\#P(n-2)$. Montrons-le !

On a la partition suivante de $P(n)$ : \[ P(n)=\underbrace{\{(p_1,...,p_i) \in P(n) \; | \; p_i=1\}}_{:=P_1(n)}\sqcup \underbrace{\{(p_1,...,p_i) \in P(n) \; | \; p_i=2\}}_{:=P_2(n)} \] Or $P_1(n)$ et $P(n-1)$ ainsi que $P_2(n)$ et $P(n-2)$ sont en bijection via l'application $(p_1,...,p_n)\mapsto (p_1,...,p_{i-1})$.
Par suite, \[\#P(n)=\#P(n-1)+\#P(n-2)\] Il s'agit donc de la suite de Fibonacci ! Pour obtenir $\#P(n)$, on a besoin de $\#P(1)$ et $\#P(2)$ qui valent respectivement $1$ et $2$ et on retrouve, par la méthode usuelle pour déterminer la valeur explicite des termes de la suite de Fibonacci : \[ \#P(n)=\dfrac{1}{\sqrt{5}}\left(\left(\dfrac{1+\sqrt{5}}{2}\right)^n- \left(\dfrac{1+\sqrt{5}}{2}\right)^n\right). \]


2eme possibilité : on partitionne $P(n)$ en fonction du nombre de saut de $2$ marches :
Considérons un entier naturel $k$. On note $P_k$ l'ensemble des possibilités d'arriver à la $n$-ième marche en effectuant exactement $k$ sauts de $2$ marches. En utilisant la formalisation effectuée au début, on obtient : \[ P_k=\{p=(p_1,...,p_i) \in P(n) \; | \; \#\{j \in \;[\!\!\![\; 1,i\;]\!\!\!]\; \; | \; p_j=2\}=k\} \] Le nombre de sauts de $2$ pas pour atteindre la marche $n$ étant inférieur à partie entière de $n/2$, on obtient la partition de $P(n)$ : \[ P(n)=\bigsqcup_{k=0}^{E(n/2)}P_k. \] Il ne nous donc plus qu'à déterminer $\#P_k$ pour $1\leqslant k \leqslant E(n/2)$.
Considérons un tel $k$. Alors on remarque que pour tout $p=(p_1,...,p_i) \in P_k$, le nombre $i$ de sauts total est constant égal à $n-k$. En effet, si on note $l\#\{j \in \;[\!\!\![\; 1,i\;]\!\!\!]\; \; | \; p_j=1\}$ le nombre de sauts de $1$ marche, on a $l+2k=n$ et $l+k=i$.

Ainsi, pour "créer" une possibilité $p=(p_1,...,p_{n-k}) \in P_k$, il faut et il suffit de placer $k$ sauts de $2$ (i.e. $k$ $p_j$ égaux à deux) parmi les $n-k$ sauts puis de placer les sauts de $1$ aux places restantes ! Ainsi, \[ \#P_k=\dbinom{n-k}{k}. \] Il en résulte que : \[ \#P(n)=\sum_{k=0}^{E(n/2)}\#P_k=\sum_{k=0}^{E(n/2)}\dbinom{n-k}{k}. \]

Pour la route, vérifions que notre deuxième expression de $P(n)$ satisfait bien la relation de la suite de Fibonacci (histoire d'être sûr qu'on obtient bien le même résultat !).

On traite le cas où $n$ est pair, le cas $n$ impair étant similaire. Pour $n$ pair, on a $E((n+1)/2)=n/2=E(n/2)$ et $E((n+2)/2)=n/2+1$, d'où :

$P(n+1)+P(n)$
$\displaystyle = \sum_{k=0}^{n/2}\dbinom{n+1-k}{k}+\sum_{k=0}^{n/2}\dbinom{n-k}{k}$
$\displaystyle = \dbinom{n+1}{0}+\sum_{k=1}^{n/2}\dbinom{n-(k-1)}{k}+\sum_{k=0}^{n/2-1}\dbinom{n-k}{k}+\dbinom{n/2}{n/2}$
$\displaystyle = 1+\sum_{k=0}^{n/2-1}\left(\dbinom{n-k}{k+1}+\dbinom{n-k}{k}\right)+1$
$\displaystyle = 1+\sum_{k=0}^{n/2-1}\dbinom{n-k+1}{k+1}+1$
$\displaystyle = \dbinom{0}{n+2}+\sum_{k=1}^{n/2}\dbinom{n-k+2}{k}+\dbinom{(n+2)/2}{(n+2)/2}$
$\displaystyle =\sum_{k=0}^{n/2+1}\dbinom{n-k+2}{k}=P(n+2).$
Problème du mois de Septembre : Somme de la somme de la somme des chiffres
Énoncé :
Que vaut la somme de la somme de la somme des chiffres du nombre (en base $10$ bien-sûr !) : \[ 4444^{4444} \]
  1. En base $10$, la somme des chiffres d'un nombre est congrue à ce nombre modulo ? (d'ailleurs, on peut généraliser ceci à une base $b$ quelconque, quel sera le ? dans ce cas ?)
  2. Pour conclure, il faut essayer de majorer grossièrement cette somme de somme de somme !
Correction :
Pour tout $x \in \mathbb{N}$, on note $s(x)$ la somme de ses chiffres en base $10$. Comme, pour tout $n \in \mathbb{N}$, $10^n$ est congru à $1$ modulo $9$, on a : \[ s(x) \;\equiv\; x \; \text{ mod }9. \] Ainsi, le nombre $s(s(s(4444^{4444})))$ recherché vérifie : \[ s(s(s(4444^{4444})))\;\equiv\;s(s(4444^{4444}))\;\equiv\;s(4444^{4444})\;\equiv\;4444^{4444}\;\text{ mod }9. \quad (*) \] Or $4444=9\times 493 + 7\;\equiv\;7\;\text{ mod }9$ et $7^{4444}\;\equiv\;(7^{3})^{1481}\times 7\;\equiv\;7\;\text{ mod }9$ car $7^3\;\equiv\; 1 \text{ mod }9$;
Par suite, \[ 4444^{4444}\;\equiv\;7^{4444}\;\equiv\;7\;\text{ mod }9. \]

Il en résulte, d'après $(*)$, que : \[ s(s(s(4444^{4444})))\;\equiv\;7\;\text{ mod }9. \] Maintenant, on sait que $s(s(s(4444^{4444})))$ est de la forme $7+9n$ où $n \in \mathbb{N}$ (on a bien que $n$ est un entier naturel car notre somme de somme de somme est positive). On va alors majorer $s(s(s(4444^{4444})))$ pour pouvoir majorer $n$ et avec un peu de chance, on aura même une seule valeur possible !
On a $4444^{4444}\leqslant 10000^{4444}=10^{17776}$ et ce dernier nombre possède $17777$ chiffres en base $10$. Le nombre d'au plus $17777$ chiffres de somme des chiffres maximale est $99...99$ (avec $17777$ chiffres $9$) donc : \[ s(4444^{4444})\leqslant s(99...99)=9\times 17777=159993. \] Ainsi, $s(4444^{4444})$ est un nombre d'au plus $6$ chiffres et plus petit que $159993$. On emploie le même raisonnement pour la seconde somme des chiffres. Le nombre d'au plus $6$ chiffres, plus petit que $159993$ de somme des chiffres maximale est $99999$. Ainsi : \[ s(s(4444^{4444}))\leqslant s(99999)=5\times 9=45. \] Par suite, $s(s(4444^{4444}))$ est un nombre d'au plus $2$ chiffres et plus petit que $45$. Le nombre d'au plus $2$ chiffres, plus petit que $45$ de somme des chiffres maximale est $39$. On a donc finalement : \[ s(s(s(4444^{4444})))\leqslant s(39)=12. \]
Or, le seul nombre de la forme $7+9n$ ($n\in \mathbb{N}$) plus petit que $12$ est $7$. Il en résulte que :

La somme de la somme de la somme des chiffres de $4444^{4444}$ est égale à $7$ !