Shortlist 2009, N1¶
Domaine : Théorie des nombres · Difficulté : ★★☆☆☆ · Proposé par : Australia
Concepts : Divisibilité, PGCD et algorithme d'Euclide · Théorème des restes chinois · Graphes : degrés, chemins, arbres
Solution officielle : Shortlist officielle 2009 (avec solutions), p. 69 (page 71 du PDF)
Problème 1 de l'OIM 2009
Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2009, où il était le problème 1 (jour 1).
Énoncé¶
A social club has \(n\) members. They have the membership numbers \(1, 2, \ldots, n\), respectively. From time to time members send presents to other members, including items they have already received as presents from other members. In order to avoid the embarrassing situation that a member might receive a present that he or she has sent to other members, the club adds the following rule to its statutes at one of its annual general meetings:
"A member with membership number \(a\) is permitted to send a present to a member with membership number \(b\) if and only if \(a(b - 1)\) is a multiple of \(n\)."
Prove that, if each member follows this rule, none will receive a present from another member that he or she has already sent to other members.
Alternative formulation: Let \(G\) be a directed graph with \(n\) vertices \(v_1, v_2, \ldots, v_n\), such that there is an edge going from \(v_a\) to \(v_b\) if and only if \(a\) and \(b\) are distinct and \(a(b - 1)\) is a multiple of \(n\). Prove that this graph does not contain a directed cycle.
Indices : les idées clés
- PGCD décroissant : une arête \(v_i \to v_j\) impose \(\gcd(j, n) \mid \gcd(i, n)\) ; sur un cycle, tous ces pgcd sont égaux à \(t\), et le théorème chinois détermine \(i\) modulo \(n\) à partir de \(t\).
- Transitivité (solution 2) : \(a \to b \to c\) implique \(a \to c\), donc un plus petit cycle aurait longueur \(2\), ce qui force \(a = b\).
- Produit (solution 3) : le long d'un cycle, \(i_1 \equiv i_1i_2 \equiv \cdots \equiv i_1i_2 \cdots i_r \pmod n\), et de même pour chaque \(i_k\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2009 (cinq solutions).
Solution 1¶
Supposons qu'il y ait une arête de \(v_i\) vers \(v_j\). Alors \(i(j - 1) = ij - i = kn\) pour un entier \(k\), ce qui implique \(i = ij - kn\). Si \(\gcd(i, n) = d\) et \(\gcd(j, n) = e\), alors \(e\) divise \(ij - kn = i\), et donc \(e\) divise aussi \(d\). Ainsi, s'il y a une arête de \(v_i\) vers \(v_j\), alors \(\gcd(j, n) \mid \gcd(i, n)\).
S'il y a un cycle dans \(G\), disons \(v_{i_1} \to v_{i_2} \to \cdots \to v_{i_r} \to v_{i_1}\), on a
ce qui implique que tous ces pgcd sont égaux, disons à \(t\).
Choisissons l'un quelconque des \(i_k\), sans perte de généralité \(i_1\). Alors \(i_r(i_1 - 1)\) est un multiple de \(n\), donc (en divisant par \(t\)) \(i_1 - 1\) est un multiple de \(\frac{n}{t}\). Comme \(i_1\) et \(i_1 - 1\) sont premiers entre eux, \(t\) et \(\frac{n}{t}\) le sont aussi. Par le théorème chinois, la valeur de \(i_1\) est donc déterminée de façon unique modulo \(n = t \cdot \frac{n}{t}\) par la valeur de \(t\). Mais, comme \(i_1\) a été choisi arbitrairement parmi les \(i_k\), cela implique que tous les \(i_k\) sont égaux, ce qui est une contradiction. \(\blacksquare\)
Solution 2¶
Si \(a\), \(b\), \(c\) sont des entiers tels que \(ab - a\) et \(bc - b\) soient des multiples de \(n\), alors \(ac - a = a(bc - b) + (ab - a) - (ab - a)c\) est aussi un multiple de \(n\). Cela implique que s'il y a une arête de \(v_a\) vers \(v_b\) et une arête de \(v_b\) vers \(v_c\), alors il y a aussi une arête de \(v_a\) vers \(v_c\). Par conséquent, s'il y a des cycles, le plus petit cycle doit être de longueur \(2\). Mais supposons que les sommets \(v_a\) et \(v_b\) forment un tel cycle, c'est-à-dire que \(ab - a\) et \(ab - b\) soient tous deux des multiples de \(n\). Alors \(a - b\) est aussi un multiple de \(n\), ce qui n'est possible que si \(a = b\), ce qui est impossible. \(\blacksquare\)
Solution 3¶
Supposons qu'il y ait un cycle \(v_{i_1} \to v_{i_2} \to \cdots \to v_{i_r} \to v_{i_1}\). Alors \(i_1(i_2 - 1)\) est un multiple de \(n\), c'est-à-dire \(i_1 \equiv i_1i_2 \pmod n\). En continuant ainsi, on obtient \(i_1 \equiv i_1i_2 \equiv i_1i_2i_3 \equiv i_1i_2i_3 \cdots i_r \pmod n\). Mais la même chose vaut pour tous les \(i_k\), c'est-à-dire \(i_k \equiv i_1i_2i_3 \cdots i_r \pmod n\). Donc \(i_1 \equiv i_2 \equiv \cdots \equiv i_r \pmod n\), ce qui signifie \(i_1 = i_2 = \cdots = i_r\), une contradiction. \(\blacksquare\)
Solution 4¶
Soit \(n = k\) la plus petite valeur de \(n\) pour laquelle le graphe correspondant a un cycle. Montrons que \(k\) est une puissance d'un nombre premier.
Si \(k\) n'est pas une puissance d'un nombre premier, on peut l'écrire comme un produit \(k = de\) d'entiers premiers entre eux supérieurs à \(1\). En réduisant tous les nombres modulo \(d\), on obtient un sommet unique ou un cycle dans le graphe correspondant à \(d\) sommets, car si \(a(b - 1) \equiv 0 \pmod k\), cette relation est aussi vraie modulo \(d\). Mais comme le graphe à \(d\) sommets n'a pas de cycle, par minimalité de \(k\), tous les indices du cycle doivent être congrus modulo \(d\). Il en est de même modulo \(e\), et donc aussi modulo \(k = de\). Mais alors tous les indices sont égaux, ce qui est une contradiction.
Donc \(k\) doit être une puissance d'un nombre premier, \(k = p^m\). Aucune arête n'aboutit en \(v_k\), donc \(v_k\) n'appartient à aucun cycle. Toutes les arêtes qui ne partent pas de \(v_k\) aboutissent en un sommet d'indice non multiple de \(p\), et toutes les arêtes partant d'un non-multiple de \(p\) doivent aboutir en \(v_1\). Mais aucune arête ne part de \(v_1\). Il n'y a donc pas de cycle. \(\blacksquare\)
Solution 5¶
Supposons qu'il y ait un cycle \(v_{i_1} \to v_{i_2} \to \cdots \to v_{i_r} \to v_{i_1}\). Soit \(q = p^m\) une puissance d'un nombre premier divisant \(n\). Montrons que ou bien \(i_1 \equiv i_2 \equiv \cdots \equiv i_r \equiv 0 \pmod q\), ou bien \(i_1 \equiv i_2 \equiv \cdots \equiv i_r \equiv 1 \pmod q\).
Supposons qu'il y ait un \(i_s\) non divisible par \(q\). Alors, comme \(i_s(i_{s+1} - 1)\) est un multiple de \(q\), on a \(i_{s+1} \equiv 1 \pmod p\). De même, on conclut \(i_{s+2} \equiv 1 \pmod p\), et ainsi de suite. Aucune des étiquettes n'est donc divisible par \(p\) ; mais comme \(i_s(i_{s+1} - 1)\) est un multiple de \(q = p^m\) pour tout \(s\), tous les \(i_{s+1}\) sont congrus à \(1\) modulo \(q\). Cela prouve l'affirmation.
Comme toutes les étiquettes sont congrues modulo toutes les puissances de nombres premiers divisant \(n\), elles doivent toutes être égales d'après le théorème chinois. C'est une contradiction. \(\blacksquare\)