Арифметика с вьетнамской олимпиады

[Ktina]

(Оффтоп)

Если такая задача уже была, я эту удалю. Что-то память стала подводить

Найти наименьшее натуральное число $k$ со следующим свойством: в каждом $k$-элементном подмножестве множества $S=\{1, 2, \dots , 16\}$ существуют такие два различных элемента $a$ и $b$, что $a^2+b^2\in\mathbb P$.

[Dave]

(Примечание )

Я решил эту задачу, как новую. Не знаю, была ли она раньше. Также я предполагал, что под $\mathbb P$ подразумевается множество простых чисел.

Ответ: $k=9$.
В 8-элементном множестве $\{ 1,3,5,7,9,11,13,15\}$, (как, впрочем и в $\{2,4,6,8,10,12,14,16\}$) cумма квадратов любых двух различных чисел чётна и больше $2$, поэтому она не может быть простым числом. Значит $k>8$.
В то же время, в любом 9-элементном множестве обязательно будет присутствовать полностью хотя бы одна из 8 следующих пар: $\{1,16\}, \{2,3\}, \{4,5\}, \{6,11\}, \{7,8\}, \{9,10\}, \{12,13\}, \{14,15\}$, а для каждой из этих пар сумма квадратов - простая.

[Ktina]

Dave в сообщении #519111 писал(а):

(Примечание )

Я решил эту задачу, как новую. Не знаю, была ли она раньше. Также я предполагал, что под $\mathbb P$ подразумевается множество простых чисел.

Ответ: $k=9$.
В 8-элементном множестве $\{ 1,3,5,7,9,11,13,15\}$, (как, впрочем и в $\{2,4,6,8,10,12,14,16\}$) cумма квадратов любых двух различных чисел чётна и больше $2$, поэтому она не может быть простым числом. Значит $k>8$.
В то же время, в любом 9-элементном множестве обязательно будет присутствовать полностью хотя бы одна из 8 следующих пар: $\{1,16\}, \{2,3\}, \{4,5\}, \{6,11\}, \{7,8\}, \{9,10\}, \{12,13\}, \{14,15\}$, а для каждой из этих пар сумма квадратов - простая.

Вы правы, забыла уточнить, что имею в виду под $\mathbb P$. Молодец, что догадались.

Моё разбиение таково (более "умного" не нашла): 16-9, 15-14, 13-12, 11-6, 10-7, 8-5, 4-1, 3-2. Просто шла "сверху вниз" и искала подходящих партнёров.