Un trop plein de vaches

Dans le célèbre jeu vidéo Minecraft, il existe tout un monde d’être vivants dont des animaux. Il est possible d’interagir avec ces bêtes car on peut les nourrir (ou les tuer, selon votre degré de psychopathie) mais aussi les faire se reproduire.

« T’as de beaux meuh tu sais »

Par exemple, pour faire se reproduire deux vaches dans ce jeu, il suffit de donner du blé à chacune d’entre elles… et paf, ça fait un bébé vache !

Il n’est pas trop à croquer ce bébé vache ? (dans un bon hamburger).

Précisons tout de même que les êtres vivants n’ont pas de genre dans Minecraft et il n’y a ainsi pas de mâle ou de femelle. On peut donc faire se reproduire deux vaches quelconques, à condition qu’elles soient toutes deux adultes (mais pas forcément consentantes…). Une fois que deux vaches ont donné naissance à un bébé, il faut ensuite attendre 20 minutes pour qu’elles puissent à nouveau se reproduire. Vingt minutes, c’est aussi le temps qu’il faut à un bébé vache pour devenir adulte et pouvoir procréer.

Si jamais vous avez l’âme d’un éleveur de bêtes, vous pouvez donc vous constituer un beau petit troupeau… mais de quelle taille ? Par exemple, en jouant 24 heures en continu, combien pourrait-on avoir de vaches au maximum ?

L’amour est dans le pré

Imaginons qu’on parte d’un troupeau de deux vaches et voyons comment agrandir ce troupeau. A l’étape n°0, nous sommes donc en possession de deux bêtes:A la première étape, on fait se reproduire ces deux vaches, ce qui donne trois vaches dont un bébé:Vingt minutes plus tard, lorsque les deux adultes peuvent à nouveau se reproduire, le bébé est devenu adulte. A la fin de l’étape n°1, nous sommes donc en possession de 3 vaches adultes:A la deuxième étape, on choisit deux vaches parmi les 3 et on les fait se reproduire. La 3ème vache ne servira à rien (si ce n’est à tenir la chandelle et à dormir sur la béquille):A la fin de la deuxième étape, quand le bébé a grandi et que les vaches adultes peuvent à nouveau se reproduire, nous avons donc 4 vaches au total:Vous pouvez facilement vérifier qu’à la fin de la troisième étape, nous serons en présence de 6 vaches et vous commencez sans doute à comprendre le principe. Nous allons donc tenter de généraliser tout cela.

Modélisation du nombre de vaches

Notons $C(n)$ le nombre de vaches à la $n$ -ème étape. Par exemple, nous avons vu que $C(0)=2$ , $C(1)=3$ , $C(2)=4$ et $C(3)=6$ . Essayons de voir comment passer d’une étape à la suivante.

Supposons donc qu’on se situe à la fin de la $n$ -ème étape (à ce moment-là, les $C(n)$ vaches en notre possession sont adultes). Pour connaître le nombre de vaches à la fin de l’étape $n+1$ , on forme autant de couples de vaches que possible, chaque couple donnant naissance à un bébé. Comme il y aura autant de bébés que de couples possibles, il faut diviser le nombre de vaches $C(n)$ par 2 pour obtenir le nombre de progénitures engendrées. Cependant, s’il y a un nombre impair de vaches au départ, il y en a une qui restera seule ce qui fait que le nombre de couples de vaches, donc de bébés, sera $\left\lfloor \dfrac{C(n)}{2} \right\rfloor$ où $\left\lfloor x \right\rfloor$ désigne la partie entière de $x$ (par exemple, si à l’étape $n$ on a 13 vaches, comme la partie entière de 13/2 = 6,5 est 6, on aura donc 6 couples et une vache qui ne s’accouple pas, ce qui donnera 6 bébés).

A ces $\left\lfloor \dfrac{C(n)}{2} \right\rfloor$ bébés, il faut ajouter les $C(n)$ vaches qu’on avait déjà en notre possession, ce qui donne finalement la formule de récurrence suivante:

$\boxed{ \vphantom{\dfrac{X}{X}} C(n+1) = C(n) + \left\lfloor \dfrac{C(n)}{2} \right\rfloor }$

Grâce à cette formule, on peut calculer le nombre de vaches qu’on aura au bout de 24 heures. Comme il y a 1 440 minutes dans une journée et que 1440/20 = 72, nous pourrons donc effectuer 73 étapes de reproduction (les étapes 0 et 1 se déroulant au même instant):La formule de récurrence précédente et un petit programme informatique (ou même une calculatrice) nous permettent alors de voir que

$C(73) = 11 \, 608 \, 742 \, 626 \, 668$

Autrement dit, en 24 heures, vous pourrez obtenir un élevage de plus de dix mille milliards de vaches… de quoi bien remplir votre champ !

«Quand y en a une ça va, c’est quand il y en a beaucoup qu’il y a des problèmes.»

Une formule explicite ?

Comme souvent avec les suites, il est toujours plus commode d’avoir une formule explicite plutôt que d’avoir simplement une formule par récurrence. Malheureusement, il est difficile (mais possible, voir en fin d’article) de trouver une formule explicite pour le nombre de vaches $C(n)$ . Qu’à cela ne tienne, nous allons encadrer cette suite par deux autres suites, afin d’estimer à quelle vitesse le nombre de vaches croît (et il croît très vite comme on l’a vu !). Pour cela, nous allons utiliser le résultat suivant:

Si $k$ est un nombre entier, alors

$\dfrac{k-1}{2} \leqslant \left\lfloor \dfrac{k}{2} \right\rfloor \leqslant \dfrac{k}{2}$ .

Pour prouver ce résultat, il suffit de distinguer deux cas:

• Si $k$ est pair, alors $k = 2m$ où $m$ est un entier. Ainsi,

$\left\lfloor \dfrac{k}{2} \right\rfloor = \left\lfloor \dfrac{2m}{2} \right\rfloor = \left\lfloor m \right\rfloor = m$ c’est-à-dire $\left\lfloor \dfrac{k}{2} \right\rfloor = \dfrac{k}{2}$ .

• Si $k$ est impair, alors $k = 2m+1$ où $m$ est un entier. Par suite,

$\left\lfloor \dfrac{k}{2} \right\rfloor = \left\lfloor \dfrac{2m+1}{2} \right\rfloor = \left\lfloor m + \dfrac{1}{2} \right\rfloor = m = \dfrac{(2m+1)-1}{2}$ c’est-à-dire $\left\lfloor \dfrac{k}{2} \right\rfloor = \dfrac{k -1}{2}$

Voyons alors comment cela nous permet d’étudier la suite $C(n)$ .

Prise en sandwich (au boeuf)

En appliquant le résultat précédent à $k= C(n)/2$ , on a les inégalités:

$\dfrac{C(n)-1}{2} \leqslant \left\lfloor \dfrac{C(n)}{2} \right\rfloor \leqslant \dfrac{C(n)}{2}$

En ajoutant $C(n)$ dans chaque membre, on obtient

$C(n) + \dfrac{C(n)-1}{2} \leqslant C(n) + \left \lfloor \dfrac{C(n)}{2} \right\rfloor \leqslant C(n) + \dfrac{C(n)}{2}$

Autrement dit, $\dfrac{3}{2}C(n) - \dfrac{1}{2} \leqslant C(n+1) \leqslant \dfrac{3}{2}C(n)$ .

Ce raisonnement nous incite donc à considérer les deux suites $(u_n)$ et $(v_n)$ définies de la manière suivante:

$\begin{cases} u_0 = 2 \\ u_{n+1} = \dfrac{3}{2} u_n - \dfrac{1}{2} \end{cases}$ et $\begin{cases} v_0 = 2 \\ v_{n+1} = \dfrac{3}{2} v_n \end{cases}$

et nous allons montrer par récurrence que pour tout entier naturel $n$ , $u_n \leqslant C(n) \leqslant v_n$ .

• Si $n=0$ alors il est clair que $u_0 \leqslant C(0) \leqslant v_0$ .

• Supposons que $u_n \leqslant C(n) \leqslant v_n$ . Nous avions vu que $\dfrac{C(n)-1}{2} \leqslant \left\lfloor \dfrac{C(n)}{2} \right\rfloor \leqslant \dfrac{C(n)}{2}$ donc en ajoutant membre à membre ces deux relations, on obtient

$u_n + \dfrac{C(n)-1}{2} \leqslant C(n) + \left\lfloor \dfrac{C(n)}{2} \right\rfloor \leqslant v_n + \dfrac{C(n)}{2}$

Or, par hypothèse de récurrence, $u_n \leqslant C(n)$ donc $\dfrac{u_n - 1}{2} \leqslant \dfrac{C(n) - 1}{2}$ . De même, $C(n) \leqslant v(n)$ entraîne que $\dfrac{C(n)}{2} \leqslant \dfrac{v(n)}{2}$ . Ainsi,

$u_n + \dfrac{u_n - 1}{2} \leqslant u_n + \dfrac{C(n)-1}{2} \leqslant C(n) + \left\lfloor \dfrac{C(n)}{2} \right\rfloor \leqslant v_n + \dfrac{C(n)}{2} \leqslant v_n + \dfrac{v_n}{2}$

En ne gardant que les inégalités les plus extrêmes, on a

$u_n + \dfrac{u_n - 1}{2} \leqslant C(n) + \left\lfloor \dfrac{C(n)}{2} \right\rfloor \leqslant v_n + \dfrac{v_n}{2}$

c’est-à-dire $\dfrac{3}{2} u_n - \dfrac{1}{2} \leqslant C(n) + \left\lfloor \dfrac{C(n)}{2} \right\rfloor \leqslant \dfrac{3}{2}v_n$ et donc $u_{n+1} \leqslant C(n+1) \leqslant v_{n+1}$ . CQFD.

Encadrement du nombre de vaches

Autant il n’est pas simple de trouver une forme explicite à la suite $C(n)$ , autant les suites $(u_n)$ et $(v_n)$ sont faciles à étudier. En effet, la suite $(u_n)$ étant une suite arithmético-géométrique ( $u_{n+1} = \dfrac{3}{2}u_n - \dfrac{1}{2}$ ), nous savons alors que :

$u_n = \left( \dfrac{3}{2}\right)^n \times \left( u_0 - \dfrac{-\frac{1}{2}}{1- \frac{3}{2}} \right) + \dfrac{-\frac{1}{2}}{1- \frac{3}{2}}$

c’est-à-dire $u_n = \left( \dfrac{3}{2}\right)^n \times \left( 2 - \dfrac{-\frac{1}{2}}{- \frac{1}{2}} \right) + \dfrac{-\frac{1}{2}}{- \frac{1}{2}}$ donc $u_n = \left( \dfrac{3}{2}\right)^n + 1$

D’autre part, la suite $(v_n)$ étant géométrique ( $v_{n+1} = \dfrac{3}{2}v_n$ ), on a donc

$v_n = v_0 \times \left( \dfrac{3}{2}\right)^n = 2 \times \left( \dfrac{3}{2}\right)^n$

Nous en déduisons l’encadrement suivant du nombre de vaches qu’il est possible de générer au bout de la $n$ -ème étape:

$\boxed{ \vphantom{\dfrac{\frac{X}{X}}{\frac{X}{X}}} \left( \dfrac{3}{2}\right)^n + 1 \leqslant C(n) \leqslant 2 \times \left( \dfrac{3}{2}\right)^n }$

Autrement dit, la croissance du nombre de vaches est de l’ordre de $\left(\dfrac{3}{2}\right)^n$ c’est-à-dire que c’est une croissance exponentielle !

Par exemple, si vous voulez générer $10^{80}$ vaches, c’est-à-dire autant que le nombre d’atomes dans l’univers observable, il suffit que $n$ vérifie

$10^{80} \leqslant \left( \dfrac{3}{2} \right)^n \leqslant C(n) \iff \dfrac{\ln(10^{80})}{\ln(3/2)} \leqslant n$

Ainsi, il suffit de $n = 455$ étapes pour obtenir $10^{80}$ vaches, ce qui représente $454 \times 20 \text{mn} = 9080\text{mn}$ , soit 6 jours, 7 heures et 20 minutes de jeu, donc moins d’une semaine… la vache !

Notes:

La suite du nombre de vaches que nous avons étudiée dans cet article est référencée sur la très sérieuse Encyclopédie en ligne des suites de nombres entiers: https://oeis.org/A061418 . On y apprend d’ailleurs qu’il existe une formule explicite pour cette suite: $C(n) = \left\lceil K \times \left( 3/2 \right)^n \right\rceil$ où $\left\lceil x \right\rceil$ désigne la partie entière par excès de $x$ et où $K\approx 1,08151366859...$ est une constante.
Pour ceux qui connaissent la notation grand thêta, nous avons en fait démontré dans cet article que $C(n) = \Theta( \left( 3/2 \right)^n )$ .

Un commentaire pour Un trop plein de vaches

Ping : Trop de vaches? | L'Endormitoire

Votre commentaire Annuler la réponse.

Entrez votre commentaire...

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

E-mail (adresse strictement confidentielle)

Nom

Site web

Vous commentez à l’aide de votre compte WordPress.com. ( Déconnexion / Changer )

Vous commentez à l’aide de votre compte Facebook. ( Déconnexion / Changer )

Annuler

Connexion à %s

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur la façon dont les données de vos commentaires sont traitées.