Diễn Đàn MathScope - Về bài số học trong đề thi chọn đội tuyển TPHCM

Mình xin phân tích một số nội dung liên quan đến bài toán này. Các thảo luận liên quan mọi người có thể xem tại đây:
[Only registered and activated users can see links. Click Here To Register...]

Trích:

Nguyên văn bởi MATHSCOPE (Post 213861)

T
$\boxed{20}$ [Sài Gòn] Gọi $S$ là tập hợp các hoán vị của 164 số nguyên dương đầu tiên.

Có bao nhiêu hoán vị $\left(a_1,\,a_2,\,\ldots ,\,a_{164}\right)\in S$, thỏa mãn $a_i\ne i\;\forall\,i=\overline{1,\,164}$ và $a_i\equiv i\pmod{41}\quad\forall\,i=\overline{1,\,164}?$
Tồn tại hay không một hoán vị $\left(a_1,\,a_2,\,\ldots ,\,a_{164}\right)\in S$, thỏa mãn với mỗi $i\in\{1,\,2,\,\ldots ,\,164\}$ luôn tồn tại $b_i\in\{0,\,1,\,\ldots ,\,40\}$ sao cho $a_1+a_2+\ldots+a_i\equiv b_i^2\pmod{41}$.

Về câu a của bài toán, có thể thấy rằng các số cùng số dư khi chia cho $41$ sẽ đổi chỗ cho nhau. Số hoán vị không có điểm cố định của $4$ phần tử là $9$, có thể dùng công thức hoặc liệt kê cụ thể ra.
Từ đây suy ra kết quả của câu này là $9^{41}$.

Bài toán sẽ thú vị hơn xíu nếu điều kiện đổi thành $a_i + i$ chia hết cho $41$ hoặc xét một bội lớn hơn của $41$, chẳng hạn $410.$

Về câu b, ngoài 2 cách của anh 2M và bạn chemthan, bài toán có thể tiếp cận nhẹ nhàng hơn như sau, cũng là ý mà tác giả "chế" ra bài này:

Cách 1 (của tác giả). Dùng bổ đề: số nguyên tố $p=3k+2$ sẽ có tính chất $\{1^3,2^3, \ldots, p^3\}$ là hệ thặng dư đầy đủ mod $p$. Khi đó, ta chọn $a_i \equiv i^3 \pmod{41}$ là xong, vì để ý rằng $$1^3+2^3+\cdots+k^3$$ luôn là số chính phương.

Chứng minh bổ đề: Giả sử trong bộ trên có hai số $i\ne j$ sao cho ${{i}^{3}}\equiv {{j}^{3}}(\bmod p)$, suy ra ${{i}^{3k}}\equiv {{j}^{3k}}(\bmod p)$. Theo định lý Fermat nhỏ thì ${{i}^{3k+1}}\equiv {{j}^{3k+1}}(\bmod p)$ nên
$${{i}^{3k+1}}\equiv {{j}^{3k+1}}=j\cdot {{j}^{3k}}\equiv j\cdot {{i}^{3k}}(\bmod p),$$ kéo theo ${{i}^{3k}}(i-j)$ chia hết cho $p$ hay $i\equiv j(\bmod p)$, vô lý vì $i,j\in \{1,2,\ldots ,p\}$ và $i\ne j.$

Cách 2 (của học sinh). Nhận xét $$1+3+5+\cdots+2k-1=k^2$$ nên hoán vị sau đây sẽ thỏa mãn đề bài:
Xếp các số lẻ từ $1$ đến $41$, xếp các số chẵn từ $2$ đến $40$, tiếp tục xếp các số lẻ từ $43$ đến $81$, ... cứ như thế.

Đáp án cho thấy bất kỳ số nguyên tố $p=3k+2$ nào cũng tồn tại hoán vị như thế. Tuy nhiên, lời giải của học sinh cho thấy, các số như thế có rất nhiều. Ta thử phân tích tí xíu về các số thỏa mãn tồn tại hoán vị như thế, tạm gọi là "số đẹp". :D

Theo cách giải thứ 2, rõ ràng bất kỳ số nguyên dương lẻ $2m+1$ nào cũng là "số đẹp".
Tiếp theo, ta thấy bội của $2m+1$ cũng đẹp, vì rõ ràng ta xếp hết $2m+1$ số đầu xong thì cứ cộng mỗi số cho $2m+1$ rồi xếp đến các số tiếp theo, và cứ thế. Như thế, số nguyên dương không phải lũy thừa của $2$ đều đẹp. Vậy còn lũy thừa của $2$ thì sao?

Số $2$ đẹp, xét hoán vị $1,2$.
Số $n=2^k$ có tổng của tất cả $n$ số là $2^{k-1}(2^k-1)$, số này chia $n$ dư là $2^{k-1}$. Như thế thì với $k$ chẵn, không tồn tại hoán vị thỏa mãn đề bài.
Tuy nhiên, ta có nhận xét rằng nếu $a$ đẹp thì các ước của $a$ cũng đẹp, nhưng vì số $4$ không đẹp nên tất cả các lũy thừa khác của $2$ cũng thế.

Vậy nên tất cả các số đẹp cần tìm là: 2 cùng tất cả các số có ước nguyên tố lẻ.

Mong được trao đổi thêm với mọi người về bài toán này. :)