Aller au contenu

Shortlist 2024, C2

Domaine : Combinatoire · Difficulté : ★☆☆☆☆ · Proposé par : Türkiye

Concepts : Récurrence et constructions récursives · Congruences, théorèmes de Fermat et d'Euler

Solution officielle : Shortlist officielle 2024 (avec solutions), section C2 (livret PDF)

Énoncé

Let \(n\) be a positive integer. The integers \(1, 2, 3, \ldots, n^2\) are to be written in the cells of an \(n \times n\) board such that each integer is written in exactly one cell and each cell contains exactly one integer. For every integer \(d\) with \(d \mid n\), the \(d\)-division of the board is the division of the board into \((n/d)^2\) nonoverlapping sub-boards, each of size \(d \times d\), such that each cell is contained in exactly one \(d \times d\) sub-board.

We say that \(n\) is a cool number if the integers can be written on the \(n \times n\) board such that, for each integer \(d\) with \(d \mid n\) and \(1 < d < n\), in the \(d\)-division of the board, the sum of the integers written in each \(d \times d\) sub-board is not a multiple of \(d\).

Determine all even cool numbers.

Indices : les idées clés
  • Construction récursive : à partir d'un bon remplissage \(P\) du tableau \(2^k \times 2^k\), on en recopie quatre exemplaires décalés, puis on fait deux échanges pour corriger les quatre grands blocs.
  • Congruences : décaler par des multiples de \(2^{2k}\) et échanger des nombres qui diffèrent de \(2^{k-1}\) ne change pas les sommes modulo \(2^i\) pour \(i < k\).
  • Récurrence sur les blocs \(2^i \times 2^i\) : quatre blocs de somme \(\equiv 2^{i-1} \pmod{2^i}\) donnent un bloc de somme multiple de \(2^i\), donc \(\equiv 2^i \pmod{2^{i+1}}\).
  • Comparer avec la somme totale \(\frac{n^2(n^2+1)}{2}\) pour obtenir une contradiction quand \(n = 2^s m\), \(m > 1\) impair.
Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2024 (une solution et une remarque).

Réponse. Les nombres cool pairs sont les \(n = 2^k\), avec \(k\) entier strictement positif.

Solution

Les puissances de 2 sont cool. On procède par récurrence sur \(k\). Pour \(n = 2\), il n'y a aucun diviseur \(d\) avec \(1 < d < 2\) : c'est trivial.

Supposons \(2^k\) cool et construisons un remplissage du tableau \(2^{k+1} \times 2^{k+1}\). On le découpe en quatre sous-tableaux \(2^k \times 2^k\). Par hypothèse, il existe un remplissage \(P\) du tableau \(2^k \times 2^k\) qui convient ; on l'écrit dans chacun des quatre sous-tableaux, puis on ajoute \(2^{2k}\) à tous les nombres du deuxième sous-tableau, \(2 \times 2^{2k}\) à ceux du troisième et \(3 \times 2^{2k}\) à ceux du quatrième. On obtient ainsi les nombres de \(1\) à \(2^{2(k+1)}\).

On échange ensuite le nombre \(2^{2k}\) (dans le premier sous-tableau) avec le nombre \(2^{2k} + 2^{k-1}\) (dans le deuxième), et le nombre \(3 \times 2^{2k}\) (dans le troisième) avec le nombre \(3 \times 2^{2k} + 2^{k-1}\) (dans le quatrième).

Vérifions ce remplissage. Les diviseurs à considérer sont les \(d = 2^i\) avec \(1 \leq i \leq k\).

  • Cas \(i < k\). La somme d'un sous-tableau \(2^i \times 2^i\), modulo \(2^i\), n'est modifiée ni par l'ajout de multiples de \(2^{2k}\), ni par les échanges (qui modifient une case de \(\pm 2^{k-1}\), multiple de \(2^i\)). Elle est donc congrue modulo \(2^i\) à la somme du sous-tableau correspondant dans \(P\), qui n'est pas multiple de \(2^i\).

  • Cas \(i = k\). La somme de \(P\) vaut \(\frac{2^{2k}(2^{2k}+1)}{2} = 2^{2k-1}(1 + 2^{2k})\). Pour \(b \in \{0, 1, 2, 3\}\), la somme du \((b+1)\)-ième sous-tableau vaut donc

    \[2^{2k-1}(1 + 2^{2k}) + b \cdot 2^{4k} + (-1)^b\, 2^{k-1} \equiv 2^{k-1} \pmod{2^k},\]

    qui n'est pas multiple de \(2^k\).

Donc \(2^{k+1}\) est cool, ce qui achève la récurrence.

Les autres nombres pairs ne sont pas cool. Soit \(n = 2^s m\) avec \(s \geq 1\) et \(m > 1\) impair, et supposons par l'absurde qu'il existe un remplissage convenable. Pour \(1 \leq i \leq s\), \(2^i\) est un diviseur de \(n\) avec \(1 < 2^i < n\).

Affirmation. Pour \(1 \leq i \leq s\), dans la \(2^i\)-division, la somme de chaque sous-tableau \(2^i \times 2^i\) est congrue à \(2^{i-1}\) modulo \(2^i\).

Preuve. Par récurrence sur \(i\). Pour \(i = 1\), la somme de chaque bloc \(2 \times 2\) doit être impaire. Supposons l'affirmation vraie pour \(2^i\) (avec \(i < s\)). Dans la \(2^{i+1}\)-division, chaque bloc \(2^{i+1} \times 2^{i+1}\) est formé de quatre blocs \(2^i \times 2^i\), de sommes congrues à \(2^{i-1}\) modulo \(2^i\) ; sa somme est donc multiple de \(2^i\). Elle ne peut pas être multiple de \(2^{i+1}\) d'après les conditions, donc elle est congrue à \(2^i\) modulo \(2^{i+1}\). \(\square\)

Comme \(m\) est impair, en additionnant les sommes des \(m^2\) blocs \(2^s \times 2^s\), on obtient pour la somme totale

\[2^{s-1} m^2 \equiv 2^{s-1} \pmod{2^s}.\]

Mais la somme des entiers de \(1\) à \(n^2\) vaut

\[\frac{n^2(n^2+1)}{2} = 2^{2s-1} m^2 (2^{2s} m^2 + 1) \equiv 0 \pmod{2^s}.\]

C'est une contradiction : \(n\) n'est pas cool. \(\blacksquare\)

Remarques

Remarque 1. Pour \(n\) impair, des arguments analogues montrent que les puissances de nombres premiers sont cool. Si l'on exige en plus, dans la définition, que tous les sous-tableaux \(d \times d\) de la \(d\)-division aient le même reste non nul modulo \(d\), alors les nombres cool sont exactement les puissances de nombres premiers.