Здравствуйте, Pushkin, Вы писали:
P>Предлагаю выжать максимум из классической задачи.
P>Стоит шеренга новобранцев. Сержант командует "напра-во". Все поворачиваются произвольным образом — кто направо, кто налево. После этого начинается болтанка — каждая пара, встретившись глазами, пугается и делает синхронный поворот кругом.
P>1) Классика. Доказать, что болтанка успокоится, т.е. будет сделано не более чем конечное числа поворотов кругом.
P>2) Сколько максимально поворотов кругом будет сделано (считаем каждый поворот каждого солдата)?
P>3) Сколько в среднем поворотов кругом будет сделано?
P>4) Какова вероятность того, что ровно K из полного числа N солдат в итоге будут повёрнуты направо?
P>5) Успокоится ли болтанка на кольце (кольцо из новобранцев изначально смотрит на сержанта в центре)?
P>6) Что будет в двумерном случае? (Каре NxM в нулевой момент поворачивается кто-куда (включая кругом), затем каждый солдат, увидев перед глазами не_затылок соседа, поворачивается туда, куда этот сосед смотрит.) Здесь тоже, очевидно, всё устаканится, но столь ясного доказательства, как в одномере, у меня нет. И числа посчитать тоже пока не могу.
P>7) Что ещё умного можно тут спросить?
Так, ответ на вопросы 1,2,3 я уже дал. Ответ на 4й очевиден — сколько вначале было перевернуто направо, столько и всегда будет повернуто.
В кольце болтанка не успокоится никогда, если она началась. Потому что число солдат, смотрящих по часовой стрелке и против, постоянно, значит всегда найдется испуганная пара.
Да, мне пришло в голову действительно красивое решение.
На самом деле, можно считать, что солдаты "испугавшись" не поворачиваются, а меняются местами, смотря в ту же сторону.
Ничего с точки зрения задачи не изменилось, а вот решение становится очевидным — солдаты просто "всплывают" к тому краю, в сторону уоторого они смотрят.
Здравствуйте, Pushkin, Вы писали:
P>>>1) Классика. Доказать, что болтанка успокоится, т.е. будет сделано не более чем конечное числа поворотов кругом. К>>Не более чем за два такта с каждого края шеренги стабилизируется не менее одного человека.
P>Не ясно, почему некоторое время жизнь не может теплиться в центре... P>Т.е. не ясен смысл словосочетания "с каждого края".
Да, здесь я малость погнал.
P>В любом случае имхо есть более "убойные" доказательства.
Чего тут убойного?
Пусть шеренга выглядит так:
<<<<<<< ??????? >>>>>>>
<--L--> <--M--> <--R-->
где изначально L и R могут быть = 0.
Лемма 1. Области L и R не уменьшаются. Очевидно.
Лемма 2. Когда M = 0, шеренга стабилизируется. Очевидно.
Лемма 3. за конечное число тактов (не более M/2) M обязательно отдаст не менее одного человека в L или в R.
Доказательство:
Пусть M устроена так:
>>>(X)>>>. В таком случае все они присоединятся к R.
>>>(X)>>><???. В таком случае за один такт ситуация изменится на >>>(X-1)>><>???. За X тактов ситуация придет к <>???, и один человек присоединится к L.
Иных вариантов устройства M в данной классификации нет, поэтому за конечное число шагов (не более, чем за M/2) M заведомо уменьшится на 1.
Почему M/2? Потому что M можно представить как >>>(X)>>>???<<<(Y)<<<, и очевидно, что min(X,Y) <= M/2.
Итого доказательство.
Не более чем за M/2 + (M-1)/2 + ... + 1 шаг (очень грубая оценка сверху) область M отдаст всех человек.
Кстати, о вероятности того, что шеренга стабилизируется с конкретными значениями L и R.
За один поворот количество смотрящих влево и вправо не меняется. Поэтому — сколько человек смотрело влево, столько и будет.
Таким образом, это задача о количестве перестановок.
P(L,R) = C(L, L+R) / 2^(L+R)
Стоит шеренга новобранцев. Сержант командует "напра-во". Все поворачиваются произвольным образом — кто направо, кто налево. После этого начинается болтанка — каждая пара, встретившись глазами, пугается и делает синхронный поворот кругом.
1) Классика. Доказать, что болтанка успокоится, т.е. будет сделано не более чем конечное числа поворотов кругом.
2) Сколько максимально поворотов кругом будет сделано (считаем каждый поворот каждого солдата)?
3) Сколько в среднем поворотов кругом будет сделано?
4) Какова вероятность того, что ровно K из полного числа N солдат в итоге будут повёрнуты направо?
5) Успокоится ли болтанка на кольце (кольцо из новобранцев изначально смотрит на сержанта в центре)?
6) Что будет в двумерном случае? (Каре NxM в нулевой момент поворачивается кто-куда (включая кругом), затем каждый солдат, увидев перед глазами не_затылок соседа, поворачивается туда, куда этот сосед смотрит.) Здесь тоже, очевидно, всё устаканится, но столь ясного доказательства, как в одномере, у меня нет. И числа посчитать тоже пока не могу.
Здравствуйте, Pushkin, Вы писали:
P>Здравствуйте, Кодт, Вы писали:
P>>>1) Классика. Доказать, что болтанка успокоится, т.е. будет сделано не более чем конечное числа поворотов кругом. К>>Не более чем за два такта с каждого края шеренги стабилизируется не менее одного человека.
P>Не ясно, почему некоторое время жизнь не может теплиться в центре... P>Т.е. не ясен смысл словосочетания "с каждого края". P>В любом случае имхо есть более "убойные" доказательства.
Обычно в таких случаях вводят меру, которая стабильно уменьшается.
В этом случае этот метод срабатывает
Введем показатель — "Неразбериха". Он равен кол-ву пар солдат (не обязательно стоящих рядом), которые смотрят в сторону друг друга.
При каждом "испугивании" неразбериха уменьшается РОВНО на единицу. Так как новых пар солдат смотрящих в сторону друг друга при этом не появляется, а исчезает ровна одна — пара из двух солдат, учавствующих в "испугивании".
Таким образом болтанка не просто успокоется через конечное число поворотов, а через фиксироанное число поворотов, равное показателю "неразберихи".
К>>Фактически, мы имеем дело с клеточным автоматом (наподобие Конвеевской "Жизни"). К>>Было бы занятно написать программулю — симулятор и полюбоваться на возможные развития событий.
P>Эх, нашёлся б неленивый человек P>Меня всегда потрясало, что целые группы профессиональных математиков не жалели весьма продолжительного времени изобретая, "планерное ружьё". И изобрели ведь, мерзавцы
Планерное ружье-фигня по сравнению с паровозом, которые при движении эти ружья генерит. Число клеток такой конфигурации растет как квадрат от времени
Здравствуйте, Pushkin, Вы писали:
P>Предлагаю выжать максимум из классической задачи.
P>Стоит шеренга новобранцев. Сержант командует "напра-во". Все поворачиваются произвольным образом — кто направо, кто налево. После этого начинается болтанка — каждая пара, встретившись глазами, пугается и делает синхронный поворот кругом.
P>1) Классика. Доказать, что болтанка успокоится, т.е. будет сделано не более чем конечное числа поворотов кругом.
Не более чем за два такта с каждого края шеренги стабилизируется не менее одного человека.
P>2) Сколько максимально поворотов кругом будет сделано (считаем каждый поворот каждого солдата)?
P>3) Сколько в среднем поворотов кругом будет сделано?
P>4) Какова вероятность того, что ровно K из полного числа N солдат в итоге будут повёрнуты направо?
P>5) Успокоится ли болтанка на кольце (кольцо из новобранцев изначально смотрит на сержанта в центре)?
Не обязательно.
Пусть все, кроме одного, повернулись налево.
1. ... <<< > < <<< ...
2. ... <<< < > <<< ...
за один такт ситуация повторилась сдвинутой на 1 человека вправо.
P>6) Что будет в двумерном случае? (Каре NxM в нулевой момент поворачивается кто-куда (включая кругом), затем каждый солдат, увидев перед глазами не_затылок соседа, поворачивается туда, куда этот сосед смотрит.) Здесь тоже, очевидно, всё устаканится, но столь ясного доказательства, как в одномере, у меня нет. И числа посчитать тоже пока не могу.
Не обязательно.
<<^
v*^
v>>
Периметр стабилен, а человек в центре, как ни повернется, увидит не затылок.
Можно придумать и другие осциляторы, большего размера.
P>7) Что ещё умного можно тут спросить?
Фактически, мы имеем дело с клеточным автоматом (наподобие Конвеевской "Жизни").
Было бы занятно написать программулю — симулятор и полюбоваться на возможные развития событий.
Здравствуйте, Кодт, Вы писали:
P>>1) Классика. Доказать, что болтанка успокоится, т.е. будет сделано не более чем конечное числа поворотов кругом. К>Не более чем за два такта с каждого края шеренги стабилизируется не менее одного человека.
Не ясно, почему некоторое время жизнь не может теплиться в центре...
Т.е. не ясен смысл словосочетания "с каждого края".
В любом случае имхо есть более "убойные" доказательства.
P>>6) Что будет в двумерном случае? Здесь тоже, очевидно, всё устаканится
К>Не обязательно. К>
К><<^
К>v*^
v>>>
К>
А я проглядел
К>Фактически, мы имеем дело с клеточным автоматом (наподобие Конвеевской "Жизни"). К>Было бы занятно написать программулю — симулятор и полюбоваться на возможные развития событий.
Эх, нашёлся б неленивый человек
Меня всегда потрясало, что целые группы профессиональных математиков не жалели весьма продолжительного времени изобретая, "планерное ружьё". И изобрели ведь, мерзавцы
P>>1) Классика. Доказать, что болтанка успокоится, т.е. будет сделано не более чем конечное числа поворотов кругом.
P>>2) Сколько максимально поворотов кругом будет сделано (считаем каждый поворот каждого солдата)?
P>>3) Сколько в среднем поворотов кругом будет сделано?
P>>4) Какова вероятность того, что ровно K из полного числа N солдат в итоге будут повёрнуты направо?
P>>5) Успокоится ли болтанка на кольце (кольцо из новобранцев изначально смотрит на сержанта в центре)?
M>Так, ответ на вопросы 1,2,3 я уже дал. Ответ на 4й очевиден — сколько вначале было перевернуто направо, столько и всегда будет повернуто.
Экий ты быстрый. Хотелось бы увидеть конкретные формулы ответов,
содержащие символ N для пунктов 2) и 3) и символы N и K для пункта 4)
M>В кольце болтанка не успокоится никогда, если она началась. Потому что число солдат, смотрящих по часовой стрелке и против, постоянно, значит всегда найдется испуганная пара.
ОК
M>Да, мне пришло в голову действительно красивое решение. M>На самом деле, можно считать, что солдаты "испугавшись" не поворачиваются, а меняются местами, смотря в ту же сторону. M>Ничего с точки зрения задачи не изменилось, а вот решение становится очевидным — солдаты просто "всплывают" к тому краю, в сторону уоторого они смотрят.
Здравствуйте, Кодт, Вы писали:
К>Лемма 1. Области L и R не уменьшаются. Очевидно. К>Лемма 2. Когда M = 0, шеренга стабилизируется. Очевидно. К>Лемма 3. за конечное число тактов (не более M/2) M обязательно отдаст не менее одного человека в L или в R. К>Доказательство:
Ну ужааасно долго, всем лень читать
К>Кстати, о вероятности того, что шеренга стабилизируется с конкретными значениями L и R. К>За один поворот количество смотрящих влево и вправо не меняется. Поэтому — сколько человек смотрело влево, столько и будет. К>Таким образом, это задача о количестве перестановок. К>P(L,R) = C(L, L+R) / 2^(L+R)
Здравствуйте, Pushkin, Вы писали:
M>>Да, мне пришло в голову действительно красивое решение. M>>На самом деле, можно считать, что солдаты "испугавшись" не поворачиваются, а меняются местами, смотря в ту же сторону. M>>Ничего с точки зрения задачи не изменилось, а вот решение становится очевидным — солдаты просто "всплывают" к тому краю, в сторону уоторого они смотрят.
Тогда решение 1-3 становится очевидным
Пусть у нас в шеренге из M клеточек стоят и смотрят налево L человек. (А тех, кто смотрит направо — нет). Они некоторым образом распределены по всей длине шеренги.
За один шаг человек делает шаг влево, если клетка перед ним была свободна.
Конечное положение — когда люди стоят на L левых клетках.
Количество комбинаций из L человек равно C(L,M).
Количество поворотов равно количеству шагов, совершенных людьми. Т.е. суммарной дистанции.
Максимальное количество: все L человек стоят справа. Они проходят суммарный путь L*(M-L).
Очевидно, что абсолютный максимум достигается при L=M/2. (в случае нечетного M — округлить в любую сторону).
Т.е. M=2m --> d=m^2, M=2m+1 --> d=m(m+1)
Среднее количество... Тут нужно посчитать, сходу формулу не рожу.
Кстати, электронно-дырочная модель демонстрирует, что движение левосмотрящих влево происходит неравномерно.
Т.е. если несколько человек смотрят друг другу в затылок, то сначала первый делает шаг вперед, потом двое, и так далее, пока не наберут дистанцию. Затем точно так же они останавливаются.
Поэтому вот еще вопросы:
7) За какое (среднее, максимальное) время достигается стабилизация, с учетом параллелизма?
8) Сколько раз (в среднем, максимально) повернется на месте новобранец? Как это зависит от его положения в строю?
Здравствуйте, Кодт, Вы писали:
К>Поэтому вот еще вопросы: К>7) За какое (среднее, максимальное) время достигается стабилизация, с учетом параллелизма? К>8) Сколько раз (в среднем, максимально) повернется на месте новобранец? Как это зависит от его положения в строю?
На эти вопросы я ответы не нашёл и потому их не поставил.
Ответ на вопрос 8) усреднённый по всем новобранцам получается из вопросов 2),3) делением на N.
Перекуём баги на фичи!
