Математический факультетИнформация для студентовЭлектронная библиотека
Карта сайтаКарта сайта
Недавние измененияНедавние изменения
ПоискПоиск
  
Вы посетилиВы посетили
История страницыИстория страницы
  
Вход/выходВход


Содержание

ММ30

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

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

Решение

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

Обсуждение

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

Награды

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

 

 


Страница: [[marathon:problem_30]]

marathon/problem_30.txt · Последние изменения: 2015/10/09 13:50 — letsko
Powered by DokuWiki  ·  УКЦ ВГПУ 2006