Cool Folders ® :: Форум Игротека :: Про светофоры и кольцевую дорогу

Про светофоры и кольцевую дорогу

Дата : 13-09-06, Срд, 00:45:23

В Москве построили очередную кольцевую дорогу и расположили на ней некоторое количество светофоров, например N>1. Изначально все светофоры красные. После этого инспектор ГИБДД начинает управлять светофорами по след. алгоритму, начиная с произвольного светофора:

1. Посмотри на светофор.
2. Если светофор красный - смени цвет следующего светофора (т.е., красный - на зеленый, зеленый на красный),
если светофор зеленый - ничего не переключай!
3. Посмотри на следуюший (по кругу) светофор.
4. Исполняй строчку 2.

Внимание, вопрос:

1. (Простой) Будут ли когда-либо все светофоры зелеными?
2. (Посложнее) Докажите что в некоторый момент все светофоры опять станут красными.

P.S. Спасибо Грызю за замеченные очепятки!!!

[ 13-09-06, Срд, 11:12:04 Отредактировано: madoldman ]
[ 13-09-06, Срд, 13:28:22 Отредактировано: madoldman ]
[ 13-09-06, Срд, 13:31:01 Отредактировано: madoldman ]

Про светофоры и кольцевую дорогу

№ 2

Большой Грызь

Дата : 13-09-06, Срд, 01:58:30

Не совсем понял. "Следующий" в 3-ем пункте - это тот же следующий, который переключали или не переключали в пункте 2-ом?

Если да, тогда все светофоры зелеными стать не могут в принципе. Ибо после того, как в самом первом цикле в пункте 2 один из светофоров станет зеленым, следующий за этим зеленым светофор всегда будет красным.

Only those who attempt the absurd will achieve the impossible.. (Escher)

Про светофоры и кольцевую дорогу

№ 3

madoldman

Дата : 13-09-06, Срд, 03:48:51

Автор: Большой Грызь
Дата : 13-09-06, Срд, 08:58:30

Не совсем понял. "Следующий" в 3-ем пункте - это тот же следующий, который переключали или не переключали в пункте 2-ом?

Да

Автор: Большой Грызь
после того, как в самом первом цикле в пункте 2 один из светофоров станет зеленым, следующий за этим зеленым светофор всегда будет красным.

Это - не верное утверждение. Рассмотрим, для примера, три светофора. Тогда, их состояния во времени:
К,К,К
К,З,К
К,З,К
З,К,К
З,К,К
З,К,З

Как видно из примера, третий светофор стал таки зеленым в некоторый момент.

Про светофоры и кольцевую дорогу

№ 4

Большой Грызь

Дата : 13-09-06, Срд, 03:50:42

А как получилось вот это вот:

К,З,К
З,К,К

Как второй светофор превратился в красный?

Only those who attempt the absurd will achieve the impossible.. (Escher)

Про светофоры и кольцевую дорогу

№ 5

madoldman

Дата : 13-09-06, Срд, 03:58:59

Автор: Большой Грызь
Дата : 13-09-06, Срд, 10:50:42
Как второй светофор превратился в красный?

Извиняюсь, вкралась опечатка

Надо четыре!

КККК
КЗКК
КЗКК
КЗКЗ
КЗКЗ
КККЗ
ККЗЗ

Как видно из примера, третий светофор стал таки зеленым

в некоторый момент.

Про светофоры и кольцевую дорогу

№ 6

Большой Грызь

Дата : 13-09-06, Срд, 04:00:13

Всё равно непонятно

КЗКЗ
КККЗ

И опять второй светофор. Каким образом он стал красным?

Only those who attempt the absurd will achieve the impossible.. (Escher)

Про светофоры и кольцевую дорогу

№ 7

Большой Грызь

Дата : 13-09-06, Срд, 04:01:18

Т.е. исходя из условия, если светофор стал зеленым, то он им и останется.. Ибо нет пункта, переключающего зеленый светофор.

Что-то не так в условии

Only those who attempt the absurd will achieve the impossible.. (Escher)

Про светофоры и кольцевую дорогу

№ 8

madoldman

Дата : 13-09-06, Срд, 04:04:31

Да и с тремя тоже работает:
ККК, КЗК, КЗК, ЗЗК, ЗЗК, КЗК, ККК, ККЗ,...

Про светофоры и кольцевую дорогу

№ 9

Большой Грызь

Дата : 13-09-06, Срд, 04:06:32

Автор: madoldman
Дата : 13-09-06, Срд, 11:04:31

Да и с тремя тоже работает:
ККК, КЗК, КЗК, ЗЗК, ЗЗК, КЗК, ККК, ККЗ,...

Опять же

Выделенное.. Каким образом первый светофор превратился в красный?

Only those who attempt the absurd will achieve the impossible.. (Escher)

Про светофоры и кольцевую дорогу

№ 10

madoldman

Дата : 13-09-06, Срд, 04:08:20

ОК, все понял!

опечатка конечно-же в условии. Пункт 2 должен звучать:
2. Если светофор красный - переключи следуюший (по кругу): красный на зеленый, а зеленый на красный
если светофор зеленый - ничего не переключай!

Про светофоры и кольцевую дорогу

№ 11

Большой Грызь

Дата : 13-09-06, Срд, 04:08:33

Может в этом пункте ошибка:

2. Если светофор красный - переключи следуюший (по кругу) на зеленый,

Судя по Вашим примерам этот пункт должен быть таким:

2. Если светофор красный - переключи следуюший (по кругу) с красного на зеленый или наоборот

Only those who attempt the absurd will achieve the impossible.. (Escher)

Про светофоры и кольцевую дорогу

№ 12

Большой Грызь

Дата : 13-09-06, Срд, 04:08:58

Теперь совсем другое дело

Only those who attempt the absurd will achieve the impossible.. (Escher)

Про светофоры и кольцевую дорогу

№ 13

Krasnaja Shapka

Дата : 13-09-06, Срд, 08:44:19

ну первый вопрос очень простой - не будут, иначе не было бы второго вопроса

Если ясность вашего объяснения исключает ложное толкование, все равно кто-то поймет вас неправильно.

Про светофоры и кольцевую дорогу

№ 14

маргаритка

Дата : 13-09-06, Срд, 16:24:20

Про светофоры и кольцевую дорогу

№ 15

madoldman

Дата : 13-09-06, Срд, 18:59:17

Автор: Krasnaja Shapka
Дата : 13-09-06, Срд, 15:44:19

ну первый вопрос очень простой - не будут, иначе не было бы второго вопроса

Это правильное "мета"-доказательство, но только в том случае если составитель задачи и вопросов не ошибается.
А вот это - как видно из дискуссии выше - не верно!

Про светофоры и кольцевую дорогу

№ 16

Krasnaja Shapka

Дата : 14-09-06, Чтв, 02:44:04

это да... просто не хотел нормальное док-во сюда постить...

... да что там док-во... - два слова и вывод..

я над вторым думаю....

Если ясность вашего объяснения исключает ложное толкование, все равно кто-то поймет вас неправильно.

Про светофоры и кольцевую дорогу

№ 17

Krasnaja Shapka

Дата : 14-09-06, Чтв, 07:12:35

для второго вопроса получается чисто умозрительное доказательство... берем четное кол-во светофоров - у них снова все красные станут на 2n-1 ходе... при нечетном - на (n-1)*(n+0.5)-ом ходе... если я ничего не перепутал...
т.е. красивого док-ва у меня нет... у меня какое-то некрасивое...

Если ясность вашего объяснения исключает ложное толкование, все равно кто-то поймет вас неправильно.
[ 14-09-06, Чтв, 14:14:20 Отредактировано: Krasnaja Shapka ]

Про светофоры и кольцевую дорогу

№ 18

madoldman

Дата : 14-09-06, Чтв, 19:06:55

Автор: Krasnaja Shapka
Дата : 14-09-06, Чтв, 14:12:35
берем четное кол-во светофоров - у них снова все красные станут на 2n-1 ходе... при нечетном - на (n-1)*(n+0.5)-ом ходе... если я ничего не перепутал...

1. Формула для четных похоже неправильная (для 4 у мну получилось что нужно 16 ходов, а не 7).
2. Есть довольно симпатичное док-во которое не использует такого рода формулы. Хотя, если у вас есть док-во как посчитать время возврашения, пусть даже не слишком элегантное, черкните пажалста. Я эту задачку использую для обьяснения марковских процессов, так что вычисление времени возврата - вешь полезная, пригодится!

Про светофоры и кольцевую дорогу

№ 19

Krasnaja Shapka

Дата : 15-09-06, Птн, 03:53:52

Автор: madoldman
Дата : 15-09-06, Птн, 02:06:55

1. Формула для четных похоже неправильная (для 4 у мну получилось что нужно 16 ходов, а не 7).

гм... кккк => кзкк => кзкк => кзкз => кзкз => кккз => кк... а да... перепутал... мне показалось, что для четных все просто и я не перепроверял.... тогда для четных формула
n^2 - 1... т.е. не 16, а 15 ходов надо... не блин... эта формула тоже фигня... для 2, 4, 8 - подходит, а для 6 нет...

Автор: madoldman
Дата : 15-09-06, Птн, 02:06:55

Хотя, если у вас есть док-во как посчитать время возврашения, пусть даже не слишком элегантное, черкните пажалста.

какое там док-во... взял, пару раз походил... нашел аналогию... придумал функцию

))

при чем для нечетных все ок... а вот четные... что-то у меня уже получается, что такой функции не выведешь... короче для всех где-то между n*(n - 1) и n^2

))

Если ясность вашего объяснения исключает ложное толкование, все равно кто-то поймет вас неправильно.

Про светофоры и кольцевую дорогу

№ 20

Лапоть

Дата : 18-09-06, Пнд, 11:01:02

A := A XOR (A[i-1] XOR (A[i-2] XOR ... A[0]))

Красный - 1, Зелёный - 0.

Дома поиграю с XORами.

Про светофоры и кольцевую дорогу

№ 21

Паша

Дата : 01-11-06, Срд, 18:47:16

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

Про светофоры и кольцевую дорогу

№ 22

Krasnaja Shapka

Дата : 02-11-06, Чтв, 06:13:24

Автор: Паша
Дата : 02-11-06, Чтв, 01:47:16

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

можно поподробнее.... как из трех красных - два получаются (а из 4 - 3)... т.е. они то в конце концов получаются... но вот почему?..

Если ясность вашего объяснения исключает ложное толкование, все равно кто-то поймет вас неправильно.