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

[Sonic86]

Тогда пардон.

Equinoxe писал(а):

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

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

Вижу. А что за алгоритм? Хотя наверное это неважно...

-- Сб мар 12, 2011 17:13:13 --

Equinoxe, у меня к Вам просьба: попробуйте в программу вложить массив чисел от 1 до 58, а потом из него выбрасывать числа по одному так, чтобы нераскрашиваемость в 4 цвета оставалась? Чем меньше будет итоговый массив, тем понятнее будет. Я пока попробую ручками поломать...

[age]

Нет. Тут просто нужен более красивый и оригинальный метод разбиения, типа $8k+t$, как предлагала Xenia1996, но к сожалению там загвоздка.

Доказательства невозможности-то пока нет.

[age]

На компьютере решить нереально, т.к. нужно перебрать $C_{100}^{25}\cdot C_{75}^{25}\cdot C_{50}^{25}\sim1.6\cdot10^{57}$ комбинаций. Например, числа от 1 до 20 разложить можно:
$\{1,3,6,20,14\}$
$\{2,4,9,16,19\}$
$\{5,8,11,18,13\}$
$\{7,10,12,15,17\}$

[Equinoxe]

age, ну, я же это сделала :)
При том считалось меньше трех секунд. Я не пыталась считать для 100, я поймала его на невозможности построить для 58.
Ну, а вся магия в том, что вариантов расстановки для 57 всего 4. Т.е. отсечение огромное, если это учитывать в переборе, всё очень здорово.

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

В общем, со всей ответственностью заявляю, что решения не существует уже для 58.
Вот код: http://paste.pocoo.org/show/352383/ (меняйте maxn)

[age]

Да... не то слово забавным

К сожалению, я не очень силён в С++ (привык к Pascal), но код выглядит очень уж просто, чтобы за 3 сек перебрать все варианты с 57 числами. Что-то это вызывает у меня сомнения. Нельзя ли алгоритмическим языком изложить?

P.S.
Доказательство невозможности, на мой взгляд, должно строиться как-то так: количество квадратов в ряду чисел $1...n$ растёт как $\sqrt n$, а количество чисел в каждой группе - как $\dfrac n4$. Т.е. количество возможных представлений (разностей) многократно опережает количество недопустимых вариантов (квадратов). Т.е. квадраты будут появляться среди разностей. Но это вступает в противоречие с числом групп $i=5$.

[Equinoxe]

age, у меня компилятор g++ 4.4.4, компилю под gentoo linux 2.6.36-r5 с флагами «-W -O2 -Wall» (а ведь ещё -O3 можно :):
Для 57:

Цитата:

Equinoxe interesting # time ./main
123421231242312424124241343413434231342313124131241213412
DONE!

real 0m1.422s
user 0m1.419s
sys 0m0.000s
Equinoxe interesting # time ./main
123421231242312424124241343413434231342313124131241213412
DONE!

real 0m1.418s
user 0m1.417s
sys 0m0.000s

Для 58:

Цитата:

Equinoxe interesting # time ./main
DONE!

real 0m2.526s
user 0m2.523s
sys 0m0.002s
Equinoxe interesting # time ./main
DONE!

real 0m2.525s
user 0m2.523s
sys 0m0.001s

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

Алгоритм очевиден:
TryP(i) пытается
i < maxn: подставить число от 1 до 4 в ячейку ответа ans[i], предварительно проверяя, не возникает ли противоречие, в каждом случае отсутствия противоречия переходит в TryP(i+1)
i = maxn: противоречий нет, и мы заполнили массив ответа. Выводим ans и вырубаемся (можно было exit(0), но для наглядности, что алгоритм в случае 58 прошел все варианты и умер, я сделала вывод DONE)

Мы делаем перебор в предположении, что в каждый момент в ячейках 0..i-1 нет противоречий.

P.S. Ваше «P.S.» слишком похоже на правду, чтобы ей не быть :)
P.P.S. Обещанная программистская магия:
Магия I. Дано прямоугольное поле, заполененное «#» и «.», означающими заполненную и пустую клетку, соответственно. Необходимо выяснить, можно ли заполнить все пропуски одной и той же связной фигурой, и если можно, вывести её. Есть простое решение за полином, однако MAGIC! перебор работает быстрее.
Магия II. Даны фигурки полиомино (какие-то конкретные, порядка 10 их), необходимо заполнить ими прямоугольное поле (без наложений и без пропусков) (известно, что это сделать можно). Задачка при должных усилиях здорово решается перебором (есть один такой замечательный (подтверждение тому — Серёжа Копелиович)
Магия III. Довольно сложная задача, но тоже перебор. Необходимо составить последовательность минимальной длины, используя числа 1..k, чтобы в ней зацикленной для каждой перестановки n чисел нашлась подстрока, которая при перенумерации чисел которой в порядке возрастания (134 -> 123) соответствовала бы данной перестановке. Тоже решается адовым перебором. И как всегда только человеком по имени Сергей Копелиович. Хотя теоретически я тоже могу написать.

[age]

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

Алгоритм очевиден:
TryP(i) пытается
i < maxn: подставить число от 1 до 4 в ячейку ответа ans[i], предварительно проверяя, не возникает ли противоречие, в каждом случае отсутствия противоречия переходит в TryP(i+1)
i = maxn: противоречий нет, и мы заполнили массив ответа. Выводим ans и вырубаемся (можно было exit(0), но для наглядности, что алгоритм в случае 58 прошел все варианты и умер, я сделала вывод DONE)

Теперь понятно. Но я подумал тут вот о чём. Ведь если мы сформировали уже группу из каких-то $n$ чисел, среди которых нет противоречий, и добавляем $n+1$ число. Оно вызывает противоречие. Тогда мы пробуем следующую и следующую группу и так далее. Допустим оно не подошло не в одну.
Пусть в первой группе это число $58$, которое вступило в противоречие с числом $11$, т.к. $58-11=7^2$. Но тогда ведь сохраняется возможность без потери решения перенести число $11$ в какую-нибудь группу (поменять на другое число, которое уже не будет с числом $58$ давать противоречий) - без потери общности, и таким образом, число $58$ добавится.
Кроме того, может возникнуть ситуация, когда и число $11$ не удастся поменять ни с одной группой, т.к. оно тоже даст противоречия с одним или несколькими числами, которые так же потребуется переносить. Но в конце концов, такая "пересортировка" всё же сможет дать желаемый результат. И таких возможностей может быть очень и очень много. Вот я и подумал, учитывает ли ваш алгоритм это?

P.S.
За магии спасибо! Улыбнуло. Особенно, что решается "только человеком по имени Сергей Копелиович". Задача 3 особенно интересна. Но к ней можно вернуться после того, как одолеть эту.

-- Сб мар 12, 2011 19:52:38 --

Попробовал найти доказательство для некоторого $n$, используя доказательство Ксении для трёх групп. Её доказательство начинает "работать" с $n=59$.

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

На 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 является квадратом. Противоречие.

Для того, чтобы применить подобное для 4-х групп и построить ограничение, начиная с некоторого $n$ необходимо чтобы имела решение некоторая система:
$\begin{cases} a^2+p^2=b^2\\ a^2+q^2=c^2\\ c^2-b^2=d^2 \end{cases}$
в целых числах.
Эта задача очень похожа на поиск рационального кубоида. я попытался решить её, у меня получились очень жёсткие (практически нереальные) условия на $a,b,c,d,p,q$. Которые с трудом верится, что можно выполнить. Хотя такая возможность не исключена. Но учитывая то, что отдельные множители в данном случае из которых затем "строятся" $b,c$ или $a$. Представляют собой суммы 4-х квадратов, и на них ещё задаются доп.условия, то в ближайших 10000 такое решение навряд ли существует. А значит и $n$, начиная с которого разбиение на 4 группы невозможно - достаточно велико.

[Sonic86]

Минизамечание: кажется надо было рассматривать разложение в суммы квадратов числа не 58, а 57.

Проверьте меня. Предположим граф можно раскрасить в 4 цвета. Рассмотрим числа $0;1;4;5;8;9;16;17;20;21;24;25;32;33;36;37;40;41;49;50;53;57$. (я нумеровал числа не с 1, а с 0 - так удобнее). Всего 22 числа (возможно надо взять меньше). Пытаемся покрасить их в 4 цвета. Я в Excele считал, у меня вышли классы:
$K_0 = \{ 0;5;8;20;32;37;40;50\}$
$K_1 = \{ 1;4;9;16;36;49;57\}$
$K_2 = \{ 21;33;41;53\}$
$K_3 = \{ 17;24\}$
$K_4 = \{ 25\}$
То есть в 4 цвета граф не красится. Значит 100 чисел в 4 класса не группируются.
Я вот только боюсь, что это неверно. Проверил бы кто точно. У меня мапл, зараза такая, не работает
Если это все правильно, можно попытаться решение перевести в логику решения задачи.
(алгоритм раскраски можно взять в Кристофидесе...)

-- Сб мар 12, 2011 22:20:23 --

age, Вы ищете 3 пифагоровы тройки. А в пределах 100 их всего 2. Значит их и нету.

[age]

Проверил на компьютере. Такое решение действительно существует:
$\begin{cases} 495^2+840^2=975^2\\ 495^2+952^2=1073^2\\ 952^2-840^2=448^2 \end{cases}$

[Equinoxe]

age, смотрите, возьмём более общую и строгую структуру — дерево. Корень — это пустая последовательность. Все последовательности длины 1 — её дети, 2 — их дети.
(Например, дерево перестановок длины три будет таким:

Цитата:

___корень
____/_|_\
___1_ 2_ 3
__ /|\ /|\/|\
__123123123
_/|\ ……………/|\

)
Ясно, что в нашем случае множеством теоретически возможных (подходящих по длине) решений являются все листья. Полный перебор шел бы по всему дереву, но мы можем заранее отсечь многие ветки, заметив противоречие, что и сделали. Экспериментально доказывается, что после всех отсечений для n=57 не отсеченными остаются 4 листа, при n=58 не остаётся ни одного.

Sonic86, да, думаю, оно как-то так. Я не выбирала каких-то отдельных чисел и пыталась искать противоречия в графе, до 8 вершин не нашла, а C(56, 9) многовато будет

[age]

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

age, Вы ищете 3 пифагоровы тройки. А в пределах 100 их всего 2. Значит их и нету.

Меня интересовало не в пределах 100, а можно ли использовать доказательство Ксении для 4-х групп вообще с какого-либо $n$.

[Sonic86]

age писал(а):

Меня интересовало не в пределах 100, а можно ли использовать доказательство Ксении для 4-х групп вообще с какого-либо $n$.

ааа, понятно. Но это я уже не знаю как.

Equinoxe писал(а):

Sonic86, да, думаю, оно как-то так. Я не выбирала каких-то отдельных чисел и пыталась искать противоречия в графе, до 8 вершин не нашла, а C(56, 9) многовато будет

Ну да, просто хочется простое доказательство. А доказательство Xenia1996 пункта а) можно переписать в небольшую задачку по раскраске графа примерно на 20 вершинах. Я просто наоборот хотел: сначала построить пример, а потом из него попытаться доказательство вывести.......

[Equinoxe]

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

Проверьте меня. Предположим граф можно раскрасить в 4 цвета. Рассмотрим числа

К сожалению:

Цитата:

__0__1__4__5__8__9_16_17_20_21_24_25_32_33_36_37_40_41_49_50_53_57
__1__2__2__1__1__2__2__3__1__2__2__3__1__4__2__1__1__4__3__1__4__3

[Sonic86]

Блин, жаль...

[age]

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

Проверил на компьютере. Такое решение действительно существует:
$\begin{cases} 495^2+840^2=975^2\\ 495^2+952^2=1073^2\\ 952^2-840^2=448^2 \end{cases}$

Нашёл. Искомое число 595 360 000. Начиная с этого числа работает доказательство Ксении для четырёх групп. Как видим, уж больно сильно оно отличается от 100. Поэтому вопрос доказательства невозможности деления 100 на четыре группы остаётся открытым.

-- Сб мар 12, 2011 21:40:13 --

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

Полный перебор шел бы по всему дереву, но мы можем заранее отсечь многие ветки, заметив противоречие, что и сделали.

Мне не совсем понятно как. Пусть нам дана последовательность $\{2,10,42,50,82,90,24,32,64,72,5,13,45,53,85,93\}$.
Если мы к ней начинаем добавлять число $100$, то мы получаем противоречие с числом $64$, т.к. $100-64=36$ - квадрат. Но при этом, если мы отыщем возможность заменить число $64$ на какое-либо число из другой группы, скажем, $79$, то число 100 мы уже сможем добавить. Т.е. несмотря на то, что было противоречие, мы его "исправили" и можем продолжить дальше. Поэтому мне не совсем понятно, как можно заранее отсекать ветки (т.е. исключать возможность "исправления"). Или у вас принцип другой?