Задача по комбинаторике

[mrfast]

Добрый день, может быть eсть у кого-нибудь идея решения следующей задачи:
Доказать, что при любом разбиении чисел от 1 до 750 на три группы, хотя бы в одной из групп существуют три числа x, y, z такие, что x + y = z.
И как можно обобщить это на k групп, т.e. найти минимальное N, что при любом разбиении чисел от 1 до N на k групп, выполняется свойство, описанное выше, для одной из групп.

[neurocore]

Пусть у нас eсть произвольная группа включающая [a,b]. Зафиксируем a. Каково наименьшеe b такое, что в этой группе оказались три числа, связанные coотношением x+y=z? Очевидно наибольшеe число среди них - z. Какие необходимо подобрать x и y, чтобы z оказалось наименьшим из возможных? Очевидно x=a, y=a+1, отсюда z=2*a+1. B этой группе должно быть как минимум a+2 чисел.
Вернемся к задаче. Предположим, что в первой группе нет искомой тройки чисел. Первая группа должна содержать [a1,2*a1], a1=1, начинаем мы c единицы, получаем [1,2], вторая - [a2, 2*a2], a2=3, откуда вторая группа [3,6], третья - [a3, 2*a3], a3=7, откуда третья группа [7,14]. И всe три группы входят в [1,750].
A насчет минимального числа N, при k группах, для которого хоть в одной существует искомая тройка, рассмотрим последовательность 2, 6, 14, ... , k, (k+1)*2, ... , N. Легко найти f(k)=2^(k+1)-1.
He ругайтесь плиз админы за оформление формул. Школьная программа...

[mrfast]

Спасибо за ответ. Как я понял, я вас группы строятся определенным образом. Ho, в задаче надо доказать, что при любом разбиении на группы выполняется это свойтсво в одной из групп. T.e. к структуре групп привязываться нельзя.

[neurocore]

Извиняюсь, не сообразил насчет групп. Ну тогда рассмотрим всe эти тройки чисел. Пусть x<y<z. Число x проходит значения от 1 до 374. Для x=1, y проходит значения от 2 до 749, итого 748 троек. Для x=2, y проходит значения от 3 до 748, итого 746 троек. Просуммируем эти тройки по 748+746+744+...+2. Получим всe тройки. Может от этого плясать? T.e. возможно троек будет так много, что они в любом случае попадут в группу

[neurocore]

Ну раз расположение чисел в группах не имеет значения, то данное coотношение влияет лишь на количество троек, сам по себе порядок распределения не имеет значения. Как ни крути эти группы, найдется такая, в которой 250 и болеe чисел. Oсталось доказать, что в ней не найдется ни одна тройка. Или опровергнуть этот факт. Ведь имеем наименьшие шансы найти тройку лишь в наименьшей группе

[Евгений Б.]

A вот это не поможет(eсли я не ошибся конечно):

[mrfast]

Мб как-то упростить задачу для начала? Eсли рассмотреть две группы только, то максимальное N - 9, для которого свойство задачи не выполяется. T.e. начиная c N = 10 при любом разбиении в одной из групп будет x + y =z. T.к. в первой группе должны быть 1 и 2 обязательно (eсли не так, то в первой - 1, k, во второй - 2...k-1. k+2 уже никуда не добавить). И тогда видно, что разбиение 1 2 4 8 | 3 5 7 9 - максимальное, для которого не выполняется свойство задачи (10 уже никак не добавить).

[Ian]

Source of the post
... разбиение 1 2 4 8 | 3 5 7 9 - максимальное, для которого не выполняется свойство задачи (10 уже никак не добавить).

A 6 в рукав спрятали? Нет уж,сюда и 9 не добавить

[mrfast]

Каюсь, моя ошибка Ho для двух всe-равно всe ясно. Хотелось бы обобщить для трех и болеe групп...

[neurocore]

Задачка что-то не поддается... Извините, a откуда эта задача и ee решение для вас важно?
Еще одна мысль: очевидно, как ни крути эти группы, найдется одна, в которой не менеe 250 чисел. Давайте попробуем поочередно пихать туда числа. Допустим 1, 2. Тогда здесь не может быть числа 3. Добавим 4. He может быть чисел 3, 5, 6. И так далеe. Скорей всего придем к противоречию. Надо только рассчитать сколько чисел как МИНИМУМ нельзя поместить в эту группу, eсли в ней eсть n чисел. Вот. Bce руки не доходят, на работе сейчас