Вход | Регистрация


Информационные технологии :: Математика и алгоритмы

Хамелеоны на острове

Хамелеоны на острове
Я
   Ненавижу 1С
 
30.10.18 - 21:09
На острове есть хамелеоны трёх цветов: 40 красных, 50 жёлтых и 60 зеленых.
Когда два хамелеона разных цветов встречаются, то они перекрашиваются в третий цвет.
Три хамелеона не встречаются никогда. Других перекрашиваний нет. Не размножаются временно.
Могут ли все стать одного цвета?
 
 
   Zamestas
 
1 - 30.10.18 - 21:17
(0) Нет.
   ДНН
 
2 - 30.10.18 - 21:26
(1) А решение?
   RomanYS
 
3 - 30.10.18 - 23:47
(2) обозначим f=(1*r+2*y+3*b)%3=(1*r+2*y)%3
f сохраняется при указанных преобразованиях, и не равна 0, что требуется для конечного состояния.
   Пробел
 
4 - 31.10.18 - 04:49
нет, количество хамелеонов не равно между собой. Останется либо 10 желтых, либо 20 зеленых, либо 10 зеленых либо смешение хамелеонов разных цветов.
   Пробел
 
5 - 31.10.18 - 04:51
(3) что такое f, r, y, b? % - это остаток от деления?
   vcv
 
6 - 31.10.18 - 05:35
Предполагаем, что хамелеоны не могут стать одного цвета.
40 красных пошли на речку купаться, встретили 40 желтых и все они стали зелёными. 10 желтых, оставшихся готовить дома обед, отправили пять своих искать остальных. Эти пятеро встретили пять зелёных (бывших желтых) хамелеонов и стали красными. Когда-же эти пять красных хамелеонов пришли домой и столкнулись с оставшимися дома желтыми хамелеонами, все они стали зелёными.
На острове остались только зелёные хамелеоны.
Исходное предположение опровергнуто, хамелеоны могут стать одного цвета.
   Convert
 
7 - 31.10.18 - 06:16
(6) А куда еще 5 красных дел???
   Случайный прохожий
 
8 - 31.10.18 - 06:30
(6) Что-то у тебя там не сходится :)
   Convert
 
9 - 31.10.18 - 07:05
(0) Короче, не могут стать они одного цвета
   Случайный прохожий
 
10 - 31.10.18 - 07:25
(9) Хорошее доказательство! Ну ладно, воспримем как аксиому :)
 
 Рекламное место пустует
   Cyberhawk
 
11 - 31.10.18 - 07:28
Надо, чтоб кто-нибудь написал код на 1Сс графическим изображением блужданий этих хамелеонов.
Можно штуки в виде раскрашенных строк динамического списка / ТЗ сделать.
И чтоб оно само там долбилось.
   Convert
 
12 - 31.10.18 - 07:29
(10) Если я выложу доказательство, то будет скучно, никто уже не будет хамелеонов на речку отправлять и обед готовить))
   Zmich
 
13 - 31.10.18 - 07:29
Так выложено же доказательство в (3), о чем разговор?
   Convert
 
14 - 31.10.18 - 07:30
(13) И сколько человек его поймет?
   Случайный прохожий
 
15 - 31.10.18 - 07:33
(13) С инета формулу и я могу выложить. В той формуле о синих хамелеонах сказано, а у нас в задаче - зеленые. Значит данное решение нам не подходит :)
   Convert
 
16 - 31.10.18 - 07:43
(15) У меня, кстати, не такое доказательство получилось...
   Автосервис
 
17 - 31.10.18 - 07:58
(16) Поделишься?
   Convert
 
18 - 31.10.18 - 08:00
(17)
Будем считать, что перекрашивание происходит по очереди, т.е. встречаются хамелеоны только 1 на 1 (если встречаются 5, то считаем, что прошли 5 встреч по очереди и это будет 5 перекрашиваний)
Возьмем и посмотрим остаток от деления на 3 от количества хамелеонов каждого цвета на начальном этапе.
Красных - 1, желтых - 2, красных -0.
(1,2,0)....теперь посмотрим как меняется остаток от деления при первом преобразовании. И получается, что при встрече любых разных цветов за одну встречу остаток от деления на 3 будет (0,1,2), при следующей встрече любых разных цветов получим остатки от деления на 3 (2,0,1),  проведем еще одну встречу и получим остатки от деления на 3 (1,2,0). Получается зацикливание. Значит при любых встречах у нас остатки от деления на 3 количества хамелеонов каждого цвета должны быть либо (1,2,0) либо (0,1,2) либо (2,0,1).
А если допустить, что удалось каким-то образом сделать так, чтобы все хамелеоны оказались одного цвета, то остатки от деления на 3 (0,0,0)...противоречие....значить предположение не верно
   Zmich
 
19 - 31.10.18 - 08:04
(14). Ну а что там непонятного? Составляется для r красных, y желтых, g зеленых выражение
f=(r+2y+3g)%3. Оно не изменится, какие бы хамелеоны не встретились.

Красный+желтый = 2 зеленых:
((r-1)+2(y-1)+3(g+2))%3 = (r+2y+3g+3)%3 = (r+2y+3g)%3

Красный+зеленый = 2 желтых
((r-1)+2(y+2)+3(g-1))%3 = (r+2y+3g)%3

Желтый+зеленый = 2 красных
((r+2)+2(y-1)+3(g-1))%3 = (r+2y+3g-3)%3 = (r+2y+3g)%3

Т.е. эта характеристика инвариантна. Изначально
r=40, y=50, g=60. Вычисляем f=(40+2*50+3*60)%3 = (40+100+180)%3 = 320%3 = 2.
Если бы получились одного цвета, то их стало бы 150, что делится на 3, т.е. остаток от деления на 3 ревен 0, а у нас 2. Значит, такого быть не может.
   Convert
 
20 - 31.10.18 - 08:11
(19) Так ты сравни это с (3) Там нет доказательства инвариантности, а значит это решение ни чем не лучше, чем в (1)
   RomanYS
 
21 - 31.10.18 - 08:37
(20) согласен, но лень пока побеждает)
   Повелитель
 
22 - 31.10.18 - 08:40
(0) Классно ты завуалировал задачу, когда все на земле станут неграми )))
   Garykom
 
23 - 31.10.18 - 09:01
Если хамелеонов разных цветов одинаковое кол-во то задачка решаема, значит можно упростить задачу преобразовав ее к эквивалентной за вычетом этого равного кол-ва:

0 красных + 10 желтых + 20 зеленых

Аналогично задача эквивалентна если не вычитать а поделить на одно число все кол-ва:
4 красных + 5 желтых + 6 зеленых

Если же применить оба преобразования то выйдет странное:
0 красных + 1 желтых + 2 зеленых

Тут как не преобразовывай один фиг будут цифры 0, 1 и 2 разных цветов - итого задача превратить всех в один цвет нерешаема.
   Timon1405
 
24 - 31.10.18 - 09:14
(0) вроде, в оригинале это был остров Серобуромалин
   Ненавижу 1С
 
25 - 31.10.18 - 11:22
(24) было дело
   Трипиэль
 
26 - 31.10.18 - 11:37
(0) Может быть так: чтобы все хамелеоны стали одинакового цвета, необходимо выровнять в количестве хотя бы 2 цвета. Каждое действие либо не изменяет разницу в количестве пары цветов (-1 и -1), либо изменяет на 3 единицы (-1 и +2). Исходные разницы 10 и 20 единиц, ни ту, ни другую никак не выровнять такими действиями.
   Случайный прохожий
 
27 - 31.10.18 - 11:40
(26) "ни ту, ни другую никак не выровнять такими действиями" - это не доказательство :)
   Ненавижу 1С
 
28 - 31.10.18 - 11:40
(26) другими словами остаток от деления на три у разницы в количестве любых двух цветов сохраняется, изначально ни для одной пары она не нулевая, а требуется нулевая
   Трипиэль
 
29 - 31.10.18 - 11:43
(27) у нас "шаг сближения" 0 или 3. надо этими "шагами" "съесть расстояние" в 10 или 20.
(28) да

я уже не помню какая терминология в подобных задачах)
   Ненавижу 1С
 
30 - 31.10.18 - 14:35
В кабинете есть юзеры трех типов: 40 опытных, 50 пиздец-опытных и 60 умеющих отрывать пасьянс косынка.
Когда два юзера разных типов встречаются, то они становятся третьим типом.
Три юзера не встречаются никогда. Других типов нет. Не размножаются временно.
Могут ли все они делать годовой отчет без красняка?


Список тем форума
Рекламное место пустует  Рекламное место пустует
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.
Рекламное место пустует