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

[age]

[ИСН]

Этот фокус прокатывал с 10, потому что на 10 не делился ни один квадрат в нашей зоне внимания. На 8 их делится целая куча.

[Xenia1996]

ИСН в сообщении #421653 писал(а):

Этот фокус прокатывал с 10, потому что на 10 не делился ни один квадрат в нашей зоне внимания. На 8 их делится целая куча.

Да, Вы правы. Скажем, 1 и 65.

(Оффтоп)

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

-- Пт мар 11, 2011 00:11:27 --

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$ попадут в другое подмножество, где из них рассуждая аналогично построится какой-либо квадрат. Мы пришли к противоречию.

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

Кажется верным, но тут взгляд профессионала требуется, а не энтузиаста.

[Equinoxe]

Xenia1996, моя программа говорит, что решение существует для n = 57, вот пример:

Цитата:

123421231242312424124241343413434231342313124131241213412

Для 58 решение уже не находится (полный перебор). Может быть, это как-то поможет
И да, 58=3^2+7^2, скорее всего какое-нибудь особенное противоречие

[Xenia1996]

Equinoxe в сообщении #421664 писал(а):

Xenia1996, моя программа говорит, что решение существует для n = 57, вот пример:

Цитата:

123421231242312424124241343413434231342313124131241213412

Для 58 решение уже не находится (полный перебор). Может быть, это как-то поможет
И да, 58=3^2+7^2, скорее всего какое-нибудь особенное противоречие

Это что, остатки при делении? Что за "12342123124..."?
...........
Поняла...

[Equinoxe]

Xenia1996, это пример разбиения, там 57 символов, каждый соответствует номеру группы в разбиении

[age]

(Оффтоп)

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

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

Не понял, что неправильно-то!? У Вас все разности дают или $8k+2$ или $8k+6$, которые не могут быть квадратами.

[Xenia1996]

Equinoxe в сообщении #421667 писал(а):

Xenia1996, это пример разбиения, там 57 символов, каждый соответствует номеру группы в разбиении

(Оффтоп)

Я же написала, что уже дошло.
Что поделаешь, туго соображаю.

-- Пт мар 11, 2011 00:39:27 --

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

(Оффтоп)

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

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

Не понял, что неправильно-то!? У Вас все разности дают или $8k+2$ или $8k+6$, которые не могут быть квадратами.

1 и 65 дарамдаш остаток 1 при делении на 8, тем не менее, их разность - квадрат.
ИСН объяснил, почему это не работает.
Что самое смешное, когда я разбивала на 5, я это учла, а теперь забыла...

[age]

Всё. Понял.

[age]

Числа в группах можно перемешать так, чтобы исключить все квадраты вида $8k$, которых два $16$ и $64$. В этом случае в множество 1 попадут $8k$ и $8k+2$:
$\{8,16,48,56,88,96,26,34,66,74\}$. Итого 10 чисел. Надо 20, поэтому аналогично строим другие 7 полугрупп. Итого 80 чисел.
При этом, т.к. в ряду 1..100 есть только квадраты вида $8k+1$, то при перемешивании необходимо лишь обратить внимании на коммутации групп $8k$ и $8k+7$, $8k+4$ и $8k+3$. В итоге получится следующее:
1 и 2 группа: $8k$, $8k+2$, $8k+5$ и $8k+7$.
3 и 4 группа: $8+4k$, $8k+6$, $8k+1$ и $8k+3$.

При этом несколько чисел придётся исключить (например, $100=8k+4$ и $75=8k+3$ не могут быть в одной группе, поэтому одно из них придётся исключить). Останется примерно 70 чисел в 4 группах. Остальные 30 надо будет распределить среди них. Вот как-то так.

[Equinoxe]

(Оффтоп)

Решение ещё не раскрыто?

[age]

(Оффтоп)

нет ещё. Представленное мной выше решением не является. Т.к. неизвестно, можно ли разбросать оставшиеся ~30 чисел в четыре образованные группы.
Да и к тому же оно слишком брутально. А решение должно выглядеть просто и красиво.

[age]

Проверил. Нет, этим методом максимально можно 75 чисел:
$\{8,16,48,56,88,18,26,58,66,98,47,55,95,21,29,61,69,3,76,100\}$
$\{2,10,42,50,82,90,24,32,64,72,5,13,45,53,85,93,79\}$
$\{4,12,44,52,84,92,22,30,62,70,1,9,41,49,81,89,99,7,15\}$
$\{6,14,46,54,86,94,20,28,60,68,83,91,17,25,57,65,97,40,80\}$

[Sonic86]

У нас дан граф на 100 вершинах, вершины $i,j$ смежны $\Leftrightarrow (\exists q) |i-j|=q^2$. Нам надо его раскрасить в $k=4$ цветов (смежные вершины должны быть раскрашены в разные цвета по определению раскраски).
В Maple можно это сделать. Задача-то оказывается не олимпиадная, может не быть интересного решения и даже смысла. М.б. кто-нибудь попробует "ломануть" задачу на компе. Хотя бы будем точно знать что доказывать. М.б. даже сможем решение в осмысленный вид привести...

[Xenia1996]

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

У нас дан граф на 100 вершинах, вершины $i,j$ смежны $\Leftrightarrow (\exists q) |i-j|=q^2$. Нам надо его раскрасить в $k=4$ цветов (смежные вершины должны быть раскрашены в разные цвета по определению раскраски).
В Maple можно это сделать. Задача-то оказывается не олимпиадная, может не быть интересного решения и даже смысла. М.б. кто-нибудь попробует "ломануть" задачу на компе. Хотя бы будем точно знать что доказывать. М.б. даже сможем решение в осмысленный вид привести...

Дык на компе уже ломанули (см. пост пользователя Equinoxe ).