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


Содержание

73

Результат пpедлагаемой задачи учитывается дважды: В Большом Маpафоне и в мини-конкуpсе арифметических задач.

Конкурсная задача №73 (А-2) (6 баллов)

A - множество из пяти натуральных чисел. Множество B состоит из сумм элементов всевозможных подмножеств множества A, при условии, что эти суммы простые числа. Каково наибольше возможное число элементов B?

Для решения вышеизложенной задачи Вася написал программу. Эта программа обнуляет счетчик и (псевдо)случайным образом генерирует массив из пяти натуральных чисел. Затем перебираются (по одному разу) всевозможные суммы элементов этого массива (по одному, по два, по три, по четыре, по пять). Всякий раз, когда сумма является простым числом, счетчик увеличивается на единицу. Какое наибольшее значение счетчика может вернуть Васина программа?

Решение

Пусть во множестве A из n натуральных чисел имеется ровно k (k>0) нечетных. Тогда среди 2^n подмножеств множества A имеется ровно ровно 2n-1 подмножеств с нечетной суммой.
В самом деле, для того чтобы сумма элементов подмножества была нечетной необходимо и достаточно, чтобы в нем было нечетное количество нечетных элементов. Такое подмножество можно выбрать (С(k,1) + C(k,3) + C(k,5) +… )*2n-k = 2k-1*2n-k = 2n-1.

В нашем случае это означает, что во множестве B не более 17 элементов, 16 нечетных чисел плюс двойка.
Пусть A = {2, 29, 30, 42, 78}. Тогда во множестве B будет, как раз, 17 элементов.

Таким образом, ответ на первый вопрос задачи - 17.

Напомню, что два множества по определению равны, если каждый элемент первого является элементом второго, и обратно.
Например, A = {1, 3, 1, 2, 3} = {1, 2, 3} и состоит вовсе не из пяти, из трех элементов.

Васина ошибка состоит в том, что он не учитывает возможного появления одинаковых элементов, как при генерировании чисел, так и при увеличении счетчика.

Поскольку и в Васином случае среди полученных сумм не более 16 нечетных, увеличить значение счетчика можно только за счет появления среди сумм дополнительных двоек. Если будет сгенерировано 5 единиц, то двоек получится 10, а значение счетчика достигнет 21 (еще десять троек и одна пятерка).
Легко убедиться, что при меньшем числе единиц, а также при использовании нескольких двоек, суммарное число двоек и нечетных сумм будет меньше 21.

Таким образом, ответ на второй вопрос задачи - 21.

Обсуждение

Марафонцы практически не повторялись, предлагая свои варианты множества A. Кроме варианта, приведенного в ответе (как раз он-то встретился в ответах более одного раза), были предложены еще и такие:
{2, 6, 101, 1380, 1770};
{2, 12, 42, 90, 137};
{2, 17, 12, 42, 120};
{2, 17, 12, 42, 210};
{2, 17, 42, 90, 120};
{2, 17, 42, 120, 132};
{2, 29, 12, 150, 240};
{2, 29, 30, 42, 168};
{2, 29, 30, 42, 210};
{2, 59, 42, 78, 90};
{2, 107, 210, 4410, 250950};
{2, 11, 17, 90, 15630};
{2, 11, 48, 90, 9618};
{2, 11, 48, 90, 9629};
{2, 11, 30, 138, 420}.

Видно, что среди предложенных вариантов множества A есть всего два, в которых по 2 нечетных числа. Во всех остальных случаях нечетных чисел всего по одному. Более двух нечетных чисел быть не может, так как в этом случае среди нечетных сумм будут кратные трем.

Представляется очевидным (но я и не пытался это доказывать), что подходящих множеств A, бесконечно много.

Напрашивается очевидное обобщение первого пункта задачи: наибольшее количество попарно различных простых чисел, которые можно получить, суммируя элементы подмножеств n-элементнгого множества натуральных чисел, равно 2n-1 + 1. Владислав Франк доказал несколько более слабое утверждение:

«Заметим, что оценка 2n-1 для n чисел может быть доказана. Дело в том, что существование сколь угодно длинных арифметических прогрессий из простых чисел уже больше не гипотеза, а доказанный факт. Взяв прогрессию длины 2n-1, начинающуюся с p с разностью d, получим ее в виде частичных сумм множества p, d, 2d, . . . , 2n-2d.»

Отмечу, что ссылка на доказанность существования сколь угодно длинных арифметических прогрессий из простых чисел, явилась для меня новостью.

Награды

Владислав Франк, правильно решивший и обобщивший эту задачу, получает 8 призовых баллов.
За правильное решение Андрей Богданов, Дмитрий Милосердов, Олег Полубасов и Виктор Филимоненков получают по 6 призовых баллов.
За правильное решение с некоторыми шероховатостями Сергей Беляев и Константин Кноп получают по 5 призовых баллов.
За правильное, но неполное решение Анатолий Казмерчук получает 4 балла.

Эстетическая оценка задачи - 3.8 балла


 

 


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

marathon/problem_73.txt · Последние изменения: 2007/09/12 10:39 (внешнее изменение)
Powered by DokuWiki  ·  УКЦ ВГПУ 2006