Разбиение чисел от 1 до 100 (не решила только второй пункт)

[Xenia1996]

Дано множество всех натуральных чисел от 1 до 100 (включительно).
Требуется либо разбить это множество на

а) 3

б) 4

в) 5

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

Не справилась с пунктом б).
Вот попытка решения а) и в):

(Оффтоп)

На 3 подмножества разбить нельзя.
Для каждого $9<n<60$ числа n и n+7 обязаны находиться в одном и том же подмножестве. Почему? Возьмём числа $n-9, n, n+7, n+16$. Ясно, что n-9, n и n+16 должны принадлежать трём разным подмножествам. Точно так же n-9, n+7 и n+16 должны принадлежать трём разным подмножествам. Следовательно, n и n+7 будут вместе. Тогда числа 10, 17, 24, ... 59 должны быть вместе, но 59-10=49 является квадратом. Противоречие.

Вот разбиение на 5:

1-ое подмножество: всё, что кончается на 1 или 4
2-ое подмножество: всё, что кончается на 2 или 5
3-е подмножество: всё, что кончается на 3 или 6
4-ое подмножество: всё, что кончается на 7 или 9
5-ое подмножество: всё, что кончается на 8 или 0

Основано это разбиение на том, что квадраты не кончаются на 3, 7, туз, 2, 8.
А если разность кратна 10, она не кратна 100, ибо 100-1=99<100

Пожалуйста, помогите со средним пунктом задачи.
Заранее признательна!

[Sonic86]

б) можно решить так же как и а), т.е. рассмотреть цепочку из 10 квадратов и так же попытаться определить, как же они должны быть распределены между классами.

Или я вру?

[Xenia1996]

Sonic86 в сообщении #421540 писал(а):

б) можно решить так же как и а), т.е. рассмотреть цепочку из 10 квадратов и так же попытаться определить, как же они должны быть распределены между классами.

Или я вру?

Надеюсь, что не врёте. Но почему именно из 10 квадратов? Ведь только один из этих 10 является разностью двух других.
Или я тоже вру?

[Sonic86]

Xenia1996 писал(а):

Ведь только один из этих 10 является разностью двух других.

Полезно знать маленькие пифагоровы тройки:
$3^2+4^2=5^2$
$6^2+8^2=10^2$

И $100$ заменить на любое $N \geq 100$ для б) и в).

[Xenia1996]

Sonic86 в сообщении #421544 писал(а):

Xenia1996 писал(а):

Ведь только один из этих 10 является разностью двух других.

Полезно знать маленькие пифагоровы тройки:
$3^2+4^2=5^2$
$6^2+8^2=10^2$

Это само собой.
Есть только одна проблема: разность наибольшего и наименьшего элементов=99, следовательно, только одну пифагорову тройку можно использовать, что я и сделала.

-- Чт мар 10, 2011 20:20:50 --

Sonic86 в сообщении #421544 писал(а):

Xenia1996 писал(а):

Интересно, можно ли $100$ заменить на любое $N \geq 100$?

Можно.
Моё разбиение на 5 подходит для любого N>8, а невозможность разбиения на 3 сохраняется для $N \geq 100$.

[age]

Например, так:
1-ое подмножество: всё, что кончается на 1, 4 или 6
2-ое подмножество: всё, что кончается на 2, 5 или 3
3-е подмножество: всё, что кончается на 7, 9 или 6
4-ое подмножество: всё, что кончается на 8, 0 или 3

Второе и четвертое точно не дают квадратов. Автоматом строятся, а затем 3-е и 1-е подбираются вручную так, чтобы в них не было квадратов вида $a1-b6=t^2$, $a6-b1=u^2$, $a6-b7=p^2$ и $a7-b6=q^2$

[Xenia1996]

age в сообщении #421616 писал(а):

Например, так:
1-ое подмножество: всё, что кончается на 1, 4 или 6
2-ое подмножество: всё, что кончается на 2, 5 или 3
3-е подмножество: всё, что кончается на 7, 9 или 6
4-ое подмножество: всё, что кончается на 8, 0 или 3

Первое, второе и четвертое точно не дают квадратов. А третье - вручную.

А как же 1 и 26?

[age]

Xenia1996 в сообщении #421617 писал(а):

А как же 1 и 26?

Да. Второе и четвертое сразу. А первое и третье надо подбирать. Т.е. распихать 1 и 26 в разные. Может сработает, может нет. Не проверял. Идея примерно такая. Хотя можно подумать и разбивку улучшить.

[Xenia1996]

age в сообщении #421618 писал(а):

Xenia1996 в сообщении #421617 писал(а):

А как же 1 и 26?

Да. Второе и четвертое сразу. А первое и третье надо подбирать. Т.е. распихать 1 и 26 в разные. Может сработает, может нет. Не проверял. Идея примерно такая.

Второе - тоже нет! 2 и 3, например.

[Sonic86]

Я выше наврал. Мне кажется, что б) невозможен, но почему - я понять, к сожалению, не могу

[Xenia1996]

Sonic86 в сообщении #421621 писал(а):

Я выше наврал. Мне кажется, что б) невозможен, но почему - я понять, к сожалению, не могу

(Оффтоп)

Я тоже не могу. К сожалению. А сдавать мне завтра

[age]

Xenia1996
В общем идея такая: разбить 10 чисел от 1 до 10 на 4 класса так, чтобы в каждом классе было по 3 числа, и все их разности были $\{2,3,5,7,8\}$. При этом какие-то два числа входят сразу в две группы.

[Xenia1996]

age в сообщении #421629 писал(а):

Xenia1996
В общем идея такая: разбить 10 чисел от 1 до 10 на 4 класса так, чтобы в каждом классе было по 3 числа, и все их разности были $\{2,3,5,7,8\}$. При этом какие-то два числа входят сразу в две группы.

Да я вроде написала "попарно непересекающихся".
А если "10 чисел от 1 до 10 на 4 класса так, чтобы в каждом классе было по 3 числа", тогда пересекаться будут.


..................


Ага! Уже поняла...

[age]

Такого разбиения не существует.
Тогда по-другому. В последовательности от 1 до 100 всего 10 квадратов. Из них только один квадрат, кончающийся на $5$ и один на $0$. Остальных по два.

В любом случае, т.к. разбиения не существует, то в каждую группу попадёт обязательно минимум одно число разность с которым будет "плохой", т.е. возможность дать квадрат.

Т.к. "стационарных" чисел (входящих только в одну группу) у нас 8, а "плавающих" - которые входят сразу в две группы у нас 2, то каждая группа будет состоять из 20 чисел, оканчивающихся на "стационарное число" и нескольких чисел $<10$, оканчивающихся на "плавающее" (если в группах допускается разное количество чисел). Тогда если в некоторой группе $n<5$ "плавающих чисел", то в какой-то другой их будет $10-n>5$.

С другой стороны, т.к. чисел, оканчивающихся на "стационарную цифру" в каждой группе 10, а квадратов с любым окончанием, кроме $0$ и $5$ - по два, то построить такие квадраты из разностей "стационарных" и "плавающих" чисел легче. Поэтому в качестве примера достаточно рассмотреть любой из квадратов с окончанием $5$ или $0$, каждый из которых можно получить меньшим числом способов.

К примеру, $5$. Это квадрат $25$. Он получается в любой группе, т.к. все группы (подмножества) симметричны, поэтому возьмём какое-нибудь подмножество $\{3,6,1\}$. Оно содержит все числа оканчивающиеся на $3$ и $6$. Рассмотрим, какие варианты чисел, оканчивающихся на $1$ можно в него добавить, чтобы ни разу не получилась разность $25$. Очевидно, что $1$ нельзя, т.к. $26-1=25$. Точно так же нельзя никакие, вплоть до $81$.
Таким образом, данному подмножеству удовлетворяют только два числа $81$ и $91$. Но тогда остальные $8$ попадут в другое подмножество, где из них рассуждая аналогично построится какой-либо квадрат. Мы пришли к противоречию.

Т.е. разбить нельзя. В общем, примерно так.

[Xenia1996]

age в сообщении #421645 писал(а):

Такого разбиения не существует.
Тогда по-другому. В последовательности от 1 до 100 всего 10 квадратов. Из них только один квадрат, кончающийся на $5$ и один на $0$. Остальных по два.

В любом случае, т.к. разбиения не существует, то в каждую группу попадёт обязательно минимум одно число разность с которым будет "плохой", т.е. возможность дать квадрат.

Т.к. "стационарных" чисел (входящих только в одну группу) у нас 8, а "плавающих" - которые входят сразу в две группы у нас 2, то каждая группа будет состоять из 20 чисел, оканчивающихся на "стационарное число" и нескольких чисел $<10$, оканчивающихся на "плавающее" (если в группах допускается разное количество чисел). Тогда если в некоторой группе $n<5$ "плавающих чисел", то в какой-то другой их будет $10-n>5$.

С другой стороны, т.к. чисел, оканчивающихся на "стационарную цифру" в каждой группе 10, а квадратов с любым окончанием, кроме $0$ и $5$ - по два, то построить такие квадраты из разностей "стационарных" и "плавающих" чисел легче. Поэтому в качестве примера достаточно рассмотреть любой из квадратов с окончанием $5$ или $0$, каждый из которых можно получить меньшим числом способов.

К примеру, $5$. Это квадрат $25$. Он получается в любой группе, т.к. все группы (подмножества) симметричны, поэтому возьмём какое-нибудь подмножество $\{3,6,1\}$. Оно содержит все числа оканчивающиеся на $3$ и $6$. Рассмотрим, какие варианты чисел, оканчивающихся на $1$ можно в него добавить, чтобы ни разу не получилась разность $25$. Очевидно, что $1$ нельзя, т.к. $26-1=25$. Точно так же нельзя никакие, вплоть до $81$.
Таким образом, данному подмножеству удовлетворяют только два числа $81$ и $91$. Но тогда остальные $8$ попадут в другое подмножество, где из них рассуждая аналогично построится квадрат $25$. Мы пришли к противоречию.

Т.е. разбить нельзя. Если ничего не пропустил, то примерно так.

Ура! Нашла! По остаткам при делении на 8!

0 и 2, 1 и 3, 4 и 6, 5 и 7!

Ура!

Во я тупая! Оказывается так просто!!!
Квадрат нечётного числа дарамдаш остаток 1 при делении на 8, а чётного - 0 или 4.
Разбивая на 4 множества так, как я показала, мы избежим квадратов!