Конкурсная задача ММ30 (3 балла)

Доказать, что для любого натурального числа n, можно подобрать множество M из n (разумеется, попарно различных) натуральных чисел таких, что сумма чисел из любого непустого подмножества M не является квадратом натурального числа.

Решение

Пусть p - простое число, превосходящее 1+2+…+n.
Тогда множество M = {p, 2p,…, np}, будет подходящим.
В самом деле, сумма элементов любого подмножества этого множества будет делиться на p, но не будет делиться на p².

Обсуждение

Любопытно, что никто из марафонцев, решивших эту задачу, не предложил решения, изложенного здесь. БОльшая часть предложенных решений используют доказательство по индукции. Такой подход позволяет получать требуемое M для данного значения n, добавляя новое число во множество, построенное для предыдущего значения M. Но этого в задаче не требовалось.

Награды

За правильное решение этой задачи Макс Алексеев, Влад Франк, Алексей Копылов и Андрей Бежан получают по 3 призовых балла.