uniolympiads Ελληνικά

IMC selection 2025, Problem 4

Έστω nn θετικός ακέραιος για τον οποίο υπάρχουν ξένα σύνολα A,BA, B τέτοια ώστε A∪B={1,2,…,n}A \cup B = \{1, 2, \dots, n\} και

∑k∈Akr=∑k∈Bkr(2)\sum_{k \in A} k^r = \sum_{k \in B} k^r \qquad (2)

για κάθε r∈{0,1,2,3}r \in \{0, 1, 2, 3\}. Δείξτε ότι 8∣n8 \mid n και n≠8n \ne 8.

Original from the official PDFΈστω n θετικός ακέραιος για τον οποίο υπάρχουν ξένα σύνολα A, B τέτοια ώστε A ∪ B = {1, 2, … , n} και ∑ k r = ∑ k r (2) k∈A k∈B για κάθε r ∈ {0, 1, 2, 3}. Δείξτε ότι 8|n και n ≠ 8.

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

Εφαρμόζοντας τη (2) για r=0r = 0, παίρνουμε ∣A∣=∣B∣|A| = |B|. Έστω s=∣A∣s = |A|. Τότε n=2sn = 2s. Η (2) για r=1r = 1 δίνει ότι

∑k∈Ak=∑k∈Bk=12n(n+1)2=s(2s+1)2.\sum_{k\in A} k = \sum_{k\in B} k = \frac{1}{2}\frac{n(n+1)}{2} = \frac{s(2s+1)}{2}.

Το αριστερό μέλος είναι ακέραιος, άρα 2∣s2|s. Έστω n=4ℓn = 4\ell με ℓ∈N+\ell \in \mathbb{N}^+. Η (2) για r=2r = 2 και r=3r = 3 δίνει ότι είναι ακέραιοι οι

∑k∈Ank2=12n(n+1)(2n+1)6=ℓ(4ℓ+1)(8ℓ+1)3,∑k∈Ank3=12n2(n+1)24=2ℓ2(4ℓ+1)2.\begin{aligned} \sum_{k\in A}^{n} k^2 &= \frac{1}{2}\frac{n(n+1)(2n+1)}{6} = \frac{\ell(4\ell+1)(8\ell+1)}{3}, \\ \sum_{k\in A}^{n} k^3 &= \frac{1}{2}\frac{n^2(n+1)^2}{4} = 2\ell^2(4\ell+1)^2. \end{aligned}

Αν υποθέσουμε ότι ο ℓ\ell είναι περιττός, τότε ο πρώτος από αυτούς τους αριθμούς είναι περιττός ενώ ο δεύτερος είναι άρτιος. Όμως η διαφορά τους είναι ∑k∈A(k3−k2)=∑k∈Ak2(k−1)\sum_{k\in A}(k^3 - k^2) = \sum_{k\in A} k^2(k-1), που είναι άρτιος. Άτοπο. Άρα ο ℓ\ell είναι άρτιος, και επομένως 8∣n8|n.

Για το n≠8n \ne 8.

Ας υποθέσουμε ότι τέτοια σύνολα A,BA, B υπάρχουν για n=8n = 8. Βέβαια ∣A∣=∣B∣=4|A| = |B| = 4. Δουλεύοντας με τη (2) για r=2r = 2, βλέπουμε ότι: τα 88 και 77 δεν μπορούν να ανήκουν στο ίδιο σύνολο, το 66 πρέπει να πάει στο ίδιο σύνολο με το 77, το 55 στο ίδιο με το 88. Και τελικά η μόνη διαμέριση που ικανοποιεί τη (2) για r=0,2r = 0, 2 είναι η {8,5,3,2},{7,6,4,1}\{8, 5, 3, 2\}, \{7, 6, 4, 1\}. Η διαμέριση ικανοποιεί τη (2) και για r=1r = 1 αλλά όχι για r=3r = 3.

Transcribed from the official solutions, pages 3–4. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?