Две задачи

[Timur Naimov]

Сообщение от Игорь Бронников

Вы нашли решение.
Но нет доказательства, что оно единственно возможное...

Не совсем так - я нашел закономерность, по которой задача решаема, выразил эту закономерность через x,n и пр. ерунду и увидел что только при нечетном количестве придворных закономерность работает
Вполне возможно что существуют другие решения.
Можно сказать по другому - не так чтобы прям доказательство, но мысли в продолжении темы:
Из условия задачи следует что между двумя идущими по порядку придворными всегда есть кто-то третий. Между 1 и 2 тот кто следит за 2-м и т.д. Таким образом можно записать так:
x[1] -> ? -> x[2] -> ? -> x[3] -> ..... -> x[1]
Общее количество придворных равно сумме уникальных X-ов и ?-ов в этой записи. Убираем последний x[1] потому что он повторяется, получаем что кол-во X-ов всегда на 1 больше кол-ва ?-ов. Следовательно общее количество это сумма четного и нечетного числа, а это всегда нечетное число.

[Leonid Khrisanfov]

Решил задачку про придворных иначе, рассуждая больше логически.
Первое - из условия понятно, что придворные связаны круговой порукой, то бишь каждый следит за кем-то одним, но и за ним следит кто-то один.
Если не заморачиваться порядком придворных в списке, то схема слежки - это многоугольник, где вершины - придворные, а стороны - слежка. За направление слежки (связи) можно принять движение часовой стрелки.
А вот теперь, нарисуем, например, пятиугольник и пронумеруем его вершины с 1 до 5, начиная с любой из вершин, по часовой стрелке, с пропуском соседней вершины.
И... опа! Все вершины пронумерованы, т.е. условие выполнено.
В развернутом виде выглядит так:
1->4->2->5->3->1

Сообщение от Evgeniy Sklyarevskiy

При этом, первый придворный из списка следит за тем, кто следит за вторым. Второй следит за тем, кто следит за третьим, и так далее. Предпоследний следит за тем, кто следит за последним. Последний следит за тем, кто следит за первым.

Если будет квадрат, шестиугольник и проч. "четноугольник", то пронумеровать таким образом все вершины не получится (на половине пути мы вернемся в первую вершину).
Значит любое нечетное от 5-ти и более - будет решением.
На самом деле, мне кажется, что и 3 - тоже годится.
1->3->2->1
Почему 2-ой не может быть предпоследним, а 3-ий, соответственно, последним?
Спасибо ЕС за задачку, а Тимуру за математическое доказательство

[Rustam Khamidov]

2100010006

[Evgeniy Sklyarevskiy]

Сообщение от Rustam Khamidov

2100010006

Точно. Единственный ли вариант? За сколько итераций находится?

[Rustam Khamidov]

Сообщение от Evgeniy Sklyarevskiy

Точно. Единственный ли вариант? За сколько итераций находится?

Я сначало неправильно прогу написал (-;
девятки, восьмерки, семерки ... единицы, нули. Для этого случая - единственный.
Итераций не считал, хотя мелкую оптимизацию для глупого перебора делал. Скрипт работал несколько часов (точно не знаю отходил от этого компа).

Для случая
единицы, двойки ... девятки, нули.
Сейчас скрипт переписал и запустил еще раз, чтобы определить время исполнения.

[Evgeniy Sklyarevskiy]

Сообщение от Rustam Khamidov

Я сначало неправильно прогу написал (-;
девятки, восьмерки, семерки ... единицы, нули. Для этого случая - единственный.
Итераций не считал, хотя мелкую оптимизацию для глупого перебора делал. Скрипт работал несколько часов (точно не знаю отходил от этого компа).

Для случая
единицы, двойки ... девятки, нули.
Сейчас скрипт переписал и запустил еще раз, чтобы определить время исполнения.

Рустам, хорошо бы иметь листинг процесса приближения... или там очень много строк?

[netklon]

Решение для первой задачи все-таки можно найти и без перебора.

[Игорь Бронников]

Сообщение от Rustam Khamidov

Скрипт работал несколько часов (точно не знаю отходил от этого компа).

Видимо алгоритм не очень оптимальный получился.
У меня код на PHP за пару секунд выдал единственный результат

PHP код:

<?
echo "<p>Start</p>";
flush();
for ($a[0]=0; $a[0]<=9; $a[0]++) {
    for ($a[1]=0; $a[1]<=10-$a[0]; $a[1]++) {
        for ($a[2]=0; $a[2]<=10-($a[0]+$a[1]); $a[2]++) {
            for ($a[3]=0; $a[3]<=10-($a[0]+$a[1]+$a[2]); $a[3]++) {
                for ($a[4]=0; $a[4]<=10-($a[0]+$a[1]+$a[2]+$a[3]); $a[4]++) {
                    for ($a[5]=0; $a[5]<=10-($a[0]+$a[1]+$a[2]+$a[3]+$a[4]); $a[5]++) {
                        for ($a[6]=0; $a[6]<=10-($a[0]+$a[1]+$a[2]+$a[3]+$a[4]+$a[5]); $a[6]++) {
                            for ($a[7]=0; $a[7]<=10-($a[0]+$a[1]+$a[2]+$a[3]+$a[4]+$a[5]+$a[6]); $a[7]++) {
                                for ($a[8]=0; $a[8]<=10-($a[0]+$a[1]+$a[2]+$a[3]+$a[4]+$a[5]+$a[6]+$a[7]); $a[8]++) {
                                    for ($a[9]=0; $a[9]<=10-($a[0]+$a[1]+$a[2]+$a[3]+$a[4]+$a[5]+$a[6]+$a[7]+$a[8]); $a[9]++) {
                                        if (array_sum($a)==10) {
                                            for ($i=0; $i<10; $i++)
                                                $sum[$i]=0;
                                            for ($i=0; $i<10; $i++) 
                                                @$sum[$a[$i]]++;
                                            $good=true;
                                            for ($i=0; $i<10; $i++) 
                                                if ($a[$i]!=$sum[$i])
                                                    $good=false;                        
                                            if ($good) {
                                                echo "<p>", $a[1], $a[2], $a[3], $a[4], $a[5], $a[6], $a[7], $a[8], $a[9], $a[0], "</p>";
                                                flush();
                                            }
                                        }    
                                    }
                                }
                            }
                        }
                    }
                }
            }                
        }
    }
}
echo "<p>Done</p>";
?>

[German Stimban]

Не удержался, написал программу по второй задаче. Она авторитетно заявила, что среди 10 значных чисел ответ всего один, как и указывал Рустам Хамидов:
2100010006.
На С++ работала минут 5. Просто не занимался оптимизацией алгоритма

[Evgeniy Sklyarevskiy]

Сообщение от German Stimban

Не удержался, написал программу по второй задаче. Она авторитетно заявила, что среди 10 значных чисел ответ всего один, как и указывал neod1n:
2100010006

На каком языке? какой алгоритм? Сколько минут работает?