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

[Equinoxe]

age, я похоже поняла, в чем различие наших пониманий, я не числа перебираю, а их группы. И противоречия ищу там же. Ответ — это вектор единиц, двоек, троек и четверок. Всё очень просто :)

[age]

Кажется понял, но не совсем. Интересный подход...
Т.е. вы хотите сказать, что выше 57 разбивок не существует и вы в этом уверены?

[Equinoxe]

age, ага :)

[Sonic86]

Рассмотрим граф на множестве вершин $\{ 0;9;18;...;81\} \cup \{ 16;25;34;43;...;97\}$. Вершины связаны $\Leftrightarrow$ их разница - ненулевой квадрат. Граф похож на ленту из клеток, каждая из которых имеет диагональ (все диагонали однонаправленны). Предположим, что граф можно раскрасить в 4 цвета. Обозначим $h(j)$ - цвет вершины $j$, $h(j) \in \{ 0;1;2;3\}$. С точностью до переобозначения цветов раскраска графа имеет вид:
$h(0)=0;3 \ h(16)=2$
$h(9)=2 \ \ \ h(25)=1$
$h(18)=1 \ \ h(34)=0;3$
$h(27)=0;3 \ h(43)=2$
$h(36)=2 \ \ \ h(52)=1$
$h(45)=1 \ \ \ h(61)=0;3$
$h(54)=0;3 \ h(70)=2$
$h(63)=2 \ \ \ h(79)=1$
$h(72)=1 \ \ \ h(88)=0;3$
$h(81)=0;3 \ h(97)=2$
Ну и наконец $h(97)=h(16)=2$ и $97-16=9^2$. Противоречие.

Проверьте!

[venco]

$\{0;18;45;63;72\} \to 0$
$\{9;27;36;54;81\} \to 1$
$\{16;34;61;79;88\} \to 2$
$\{25;43;52;70;97\} \to 3$

[Sonic86]

venco, это контрпример? Но ведь $36-27=3^2$, значит 36 и 27 нельзя раскрасить в цвет 1? Или я чего-то не понял?

-- Пн мар 14, 2011 22:43:49 --

А хотя я понял. Левую сторону графа красим в 010101, правую - в 232323...

[venco]

Это я перепутал. Вот так надо:
$\{0;18;52;70;72\} \to 0$
$\{9;27;61;79;81\} \to 1$
$\{16;34;36;54;88\} \to 2$
$\{25;43;45;63;97\} \to 3$

[Sonic86]

Хорошо, давайте так.
Берем квадрат с диагональю $\{ 0; 9;16; 25\}$. Транслируем его вверх и вправо - получается решетка, в координатах $(x,y)$ которой стоят числа $16x+9y$. Убираем все вершины с номерами $\leq 100$. Получается кусок решетки. Тогда с точностью до перенумерации существует единственная его раскраска, сводящаяся к раскраске исходного квадрата: вершины $(0;0),(0;1),(0;2),...$ красятся как $010101...$, вершины $(1;0),(1;1),(1;2),...$ красятся как $232323...$, потом за счет $36-32=2^2$ вершины $(2;0),(2;1),(2;2),...$ красятся как $101010...$ и за счет $52-48=2^2$ вершины $(3;0),(3;1),(3;2),...$ красятся как $323232...$. Раскраска периодична вверх по модулю 2, антипериодична вправо по модулю 2, периодична вправо по модулю 4.
Ну и наконец $81-32=49=7^2$, но 81 и 32 раскрашены цветом 1. Теперь все-таки противоречие?

-- Пн мар 14, 2011 23:45:21 --

Не. Раскраска явно не одна. Их надо как-то в общем перебрать...