=====ММ30=====

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

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

**Решение**

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

**Обсуждение** 

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

**Награды**

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