Сообщение Re: Размножение бактерий от 24.01.2017 14:44
Изменено 24.01.2017 14:46 Chorkov
Re: Размножение бактерий
Здравствуйте, nikholas, Вы писали:
N>На четверти плоскости с неотрицательными целыми координатами живут бактерии.
N>Бактерия с координатами (m,n) может разделиться две с координатами (m+1,n) и (m,n+1), но только если эти две точки были пустыми. Сама бактерия при этом исчезает.
N>В начальный момент времени есть только одна бактерия с координатами (0,0)
N>Доказать, что как бы бактерии не делились, всегда будет хотя бы одна с обеими координатами <= 2
Введем понятие "поколение".
Очевидно его можно вычислить из координат бактерий: p=(x+y)/2
При каждом делении исчезает одна бактерия в поколении и 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
Т.е. эта позиция недостижима.
Очевидно, любая другая позиция, являющаяся подмножеством этой, тоже недостижима, поскольку ее вес будет еще меньше.
N>На четверти плоскости с неотрицательными целыми координатами живут бактерии.
N>Бактерия с координатами (m,n) может разделиться две с координатами (m+1,n) и (m,n+1), но только если эти две точки были пустыми. Сама бактерия при этом исчезает.
N>В начальный момент времени есть только одна бактерия с координатами (0,0)
N>Доказать, что как бы бактерии не делились, всегда будет хотя бы одна с обеими координатами <= 2
Введем понятие "поколение".
Очевидно его можно вычислить из координат бактерий: p=(x+y)/2
При каждом делении исчезает одна бактерия в поколении и 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
Т.е. эта позиция недостижима.
Очевидно, любая другая позиция, являющаяся подмножеством этой, тоже недостижима, поскольку ее вес будет еще меньше.
Re: Размножение бактерий
Здравствуйте, 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
Т.е. эта позиция недостижима.
Очевидно, любая другая позиция, являющаяся подмножеством этой, тоже недостижима, поскольку ее вес будет еще меньше.
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
Т.е. эта позиция недостижима.
Очевидно, любая другая позиция, являющаяся подмножеством этой, тоже недостижима, поскольку ее вес будет еще меньше.