Énoncé:
Voici les enregistrements d'un système téléphonique très fréquenté comptant un million d'utilisateurs :
| RecNr | Appelant | Appelé |
|---|---|---|
| 1 | 200007 | 100053 |
| 2 | 600183 | 500439 |
| 3 | 600863 | 701497 |
| ... | ... | ... |
Le numéro de téléphone de l'appelant et le numéro appelé dans l'enregistrement $n$ sont $Appelant(n) = S_{2n-1}$ et $Appelé(n) = S_{2n}$ où $S_1, 2, 3, \dots$ proviennent du " générateur de Fibonacci décalé " :
Pour $1 \le k \le 55$, $S_k = [100003 - 200003k + 300007k^3] \mod 1000000$.
Pour $56 \e k$, $S_k = [Sk-24 + Sk-55] \mod 1000000$
Si $Caller(n) = Appelé(n)$ alors l'utilisateur est supposé avoir mal composé le numéro et l'appel échoue; sinon l'appel est réussi.
Dès le début des enregistrements, nous disons que toute paire d'utilisateurs $X$ et $Y$ est amie si $X$ appelle $Y$ ou vice-versa. De même, $X$ est l'ami d'un ami de $Z$ si $X$ est l'ami de $Y$ et $Y$ est l'ami de $Z$; et ainsi de suite pour les chaînes plus longues.
Le numéro de téléphone du Premier ministre est le $524287$. Après combien d'appels réussis, sans compter les erreurs de numérotation, $99\%$ des utilisateurs (y compris le Premier ministre) seront-ils un ami, ou l'ami d'un ami, etc. du Premier ministre ?
Lien du problème originel