На четверти плоскости с неотрицательными целыми координатами живут бактерии.
Бактерия с координатами (m,n) может разделиться две с координатами (m+1,n) и (m,n+1), но только если эти две точки были пустыми. Сама бактерия при этом исчезает.
В начальный момент времени есть только одна бактерия с координатами (0,0)
Доказать, что как бы бактерии не делились, всегда будет хотя бы одна с обеими координатами <= 2
Здравствуйте, nikholas, Вы писали:
N>На четверти плоскости с неотрицательными целыми координатами живут бактерии. N>Бактерия с координатами (m,n) может разделиться две с координатами (m+1,n) и (m,n+1), но только если эти две точки были пустыми. Сама бактерия при этом исчезает. N>В начальный момент времени есть только одна бактерия с координатами (0,0) N>Доказать, что как бы бактерии не делились, всегда будет хотя бы одна с обеими координатами <= 2
В какой момент времени? При каких начальных условиях? С какой вероятностью они делятся в каждый очередной момент времени? Например, размножение началось с двух бактерий по координатам 1 000 000 000 х 1 000 000 000 (миллиард). За 1000 единиц условного времени, как бы они не делились, ни одна из них не достигнет координат <=2
PS: не люблю математику, а особенно — вот такую. С кучей умозрительных умолчаний, которые очевидны (и считаются обязательными к исполнению) только тем, кто провёл 5 лет в автоклаве для физматиков.
Здравствуйте, nikholas, Вы писали:
N>На четверти плоскости с неотрицательными целыми координатами живут бактерии. N>Бактерия с координатами (m,n) может разделиться две с координатами (m+1,n) и (m,n+1), но только если эти две точки были пустыми. Сама бактерия при этом исчезает. N>В начальный момент времени есть только одна бактерия с координатами (0,0) N>Доказать, что как бы бактерии не делились, всегда будет хотя бы одна с обеими координатами <= 2
Введем понятие "поколение".
Очевидно его можно вычислить из координат бактерий: p=x+y
При каждом делении исчезает одна бактерия в поколении и k и появляются две в поколении k+1.
Введем "вес бактерии". Пусть он зависит от ее поколения: m(p)=2^(-k). Суммарный вес всех бактерий сохраняется при каждом делении.
Для одной бактерии 0-го поколения суммарный вес равен 1.
Рассмотри ситуацию когда заполнено все поле, кроме квадрата ( x<=2 && y<=2 ).
Суммарный вес равен:
M = 2*m(3) + 4*m(5) +6*m(6) + summ_{i=7...inf}( (i+1)*m(i) )
= 0.9375
Т.е. эта позиция недостижима.
Очевидно, любая другая позиция, являющаяся подмножеством этой, тоже недостижима, поскольку ее вес будет еще меньше.
Здравствуйте, Chorkov, Вы писали:
C>Здравствуйте, nikholas, Вы писали:
N>>На четверти плоскости с неотрицательными целыми координатами живут бактерии. N>>Бактерия с координатами (m,n) может разделиться две с координатами (m+1,n) и (m,n+1), но только если эти две точки были пустыми. Сама бактерия при этом исчезает. N>>В начальный момент времени есть только одна бактерия с координатами (0,0) N>>Доказать, что как бы бактерии не делились, всегда будет хотя бы одна с обеими координатами <= 2
C>Введем понятие "поколение". C>Очевидно его можно вычислить из координат бактерий: p=x+y C>При каждом делении исчезает одна бактерия в поколении и k и появляются две в поколении k+1. C>Введем "вес бактерии". Пусть он зависит от ее поколения: m(p)=2^(-k). Суммарный вес всех бактерий сохраняется при каждом делении. C>Для одной бактерии 0-го поколения суммарный вес равен 1.
C>Рассмотри ситуацию когда заполнено все поле, кроме квадрата ( x<=2 && y<=2 ). C>Суммарный вес равен: C>M = 2*m(3) + 4*m(5) +6*m(6) + summ_{i=7...inf}( (i+1)*m(i) ) C> = 0.9375 C>Т.е. эта позиция недостижима. C>Очевидно, любая другая позиция, являющаяся подмножеством этой, тоже недостижима, поскольку ее вес будет еще меньше.
Придумал более простое объяснение:
Пусть в нашей сетке клетки имеют разную площадь. (С ростом индекса ячейки, по каждой из координат, размер шага сетки уменьшается вдвое.)
(Каждой точке с целочисленными координатами исходной задачи, соответствует клетка этой сетки.)
Площадь ячейки (0,0) примем за единицу. Тогда общая "площадь вселенной" конечна и равна четырем.
При делении бактерия занимает две ячейки, вдвое меньшей площади, следовательно общая площадь занимаемая бактериями сохраняется.
Если из вселенной исключить клетки "с обеими координатами <= 2" (выделено желтым), то остаток площади вселенной составит 4-(1+1/2+1/4)^2 = 0.9375 .
Т.е. бактерии там не уместятся, пусть число ячеек и бесконечно.
Здравствуйте, Слава, Вы писали:
N>>На четверти плоскости с неотрицательными целыми координатами живут бактерии. N>>Бактерия с координатами (m,n) может разделиться две с координатами (m+1,n) и (m,n+1), но только если эти две точки были пустыми. Сама бактерия при этом исчезает. N>>В начальный момент времени есть только одна бактерия с координатами (0,0) N>>Доказать, что как бы бактерии не делились, всегда будет хотя бы одна с обеими координатами <= 2
С>В какой момент времени?
В любой. Написано же в условиях:
С>При каких начальных условиях?
Написано же в условиях
N>>В начальный момент времени есть только одна бактерия с координатами (0,0)
С>С какой вероятностью они делятся в каждый очередной момент времени?
С любой.
С>PS: не люблю математику, а особенно — вот такую. С кучей умозрительных умолчаний, которые очевидны (и считаются обязательными к исполнению) только тем, кто провёл 5 лет в автоклаве для физматиков.
Нет там никаких умозрительных умолчаний. По-моему ты просто ленишься читать условия. Или не понимаешь значения слов вроде "может", "как бы", "всегда", "хотя бы одна" и тд, хотя они не требуют каких-то специальных познаний.
Здравствуйте, vsb, Вы писали:
С>>В какой момент времени? vsb>В любой. Написано же в условиях: vsb>Написано же в условиях vsb>С любой.
vsb>Нет там никаких умозрительных умолчаний.
Есть-есть. Типичный подсчёт ангелов на кончике иглы и игры с бесконечностями.
vsb>По-моему ты просто ленишься читать условия. Или не понимаешь значения слов вроде "может", "как бы", "всегда", "хотя бы одна" и тд, хотя они не требуют каких-то специальных познаний.
Я выше привёл отрицательный пример. Любой — значит и такой, какой указал я. И в указанном мной случае утверждение "как бы бактерии не делились, всегда будет хотя бы одна с обеими координатами <= 2" будет неверным.
Здравствуйте, Слава, Вы писали:
vsb>>По-моему ты просто ленишься читать условия. Или не понимаешь значения слов вроде "может", "как бы", "всегда", "хотя бы одна" и тд, хотя они не требуют каких-то специальных познаний.
С>Я выше привёл отрицательный пример. Любой — значит и такой, какой указал я. И в указанном мной случае утверждение "как бы бактерии не делились, всегда будет хотя бы одна с обеими координатами <= 2" будет неверным.
В этой задаче задано конкретное начальное условие: "В начальный момент времени есть только одна бактерия с координатами (0,0)". Ты его изменил, так что ты привёл отрицательный пример к другой задаче.
