Question

[Thầy Cao Đô]

Cho tập $A = \{1; \, 2; \, 3; \, ...; \, 16\}$. Tìm số nguyên dương $k$ nhỏ nhất sao cho trong mỗi tập con gồm $k$ phần tử của $A$ đều tồn tại hai số phân biệt $a$, $b$ mà $a^2 + b^2$ là một số nguyên tố.

Answer 1

[Nguyễn Minh Châu]

Nếu \(a\), \(b\) chẵn thì \(a^{2} + b^{2}\) là hợp số. Do đó nếu tập con \(X\) của \(A\) có hai phần tử phân biệt \(a\), \(b\) mà \(a^{2} + b^{2}\) là một số nguyên tố thì \(X\) không thể chỉ chứa các số chẵn.

Suy ra \(k = 9\).

Ta chứng tỏ \(k = 9\) là giá trị nhỏ nhất cần tìm. Điều đó có nghĩa là với mọi tập con \(X\) gồm \(9\) phần tử bất kì của \(A\) luôn tồn tại hai phần tử phân biệt \(a\), \(b\) mà \(a^{2} + b^{2}\) là một số nguyên tố.

Để chứng minh khẳng định trên ta chia tập \(A\) thành các cặp hai phần tử phân biệt \(a\), \(b\) mà \(a^{2} + b^{2}\) là một số nguyên tố, ta có tất cả \(8\) cặp \(\left{\right. 1 ; 4 \left.\right}\), \(\left{\right. 2 ; 3 \left.\right}\), \(\left{\right. 5 ; 8 \left.\right}\), \(\left{\right. 6 ; 11 \left.\right}\), \(\left{\right. 7 ; 10 \left.\right}\), \(\left{\right. 9 ; 16 \left.\right}\), \(\left{\right. 12 ; 13 \left.\right}\), \(\left{\right. 14 ; 15 \left.\right}\). Theo nguyên lí Dirichlet thì \(9\) phần tử của \(X\) có hai phần tử cùng thuộc một cặp và ta có điều phải chứng minh.