Жетоны в сумке

Question

У нас есть n токенов.Каждый жетон красного, синего или зеленого цвета.Эти n токенов находятся в сумке

Повторяйте до тех пор, пока пакет не опустеет:

1) Если в сумке более двух токенов.возьмите два случайных жетона из сумки.В противном случае опустошите пакет.

2) В соответствии с двумя токенами, которые мы получили на шаге 1), мы делаем следующие вещи:

* Случай 1: Если один из токенов красный,ничего не делать.

* Случай 2: Если оба жетона зеленого цвета, мы помещаем один зеленый жетон и 2 синих жетона обратно в сумку.

* Случай 3: Если мы получили один синий жетон,а другой токен не красного цвета, тогда мы кладем 3 красных жетона обратно в сумку.

Предположим, что у нас всегда достаточно жетонов, чтобы положить их обратно в сумку, докажите по индукции, что этот процесс всегда завершается.

---

Итак, для моего базового случая я положил n = 1, и, поскольку у нас меньше 2 токенов, мы просто опустошаем пакет, и процесс завершается.

Я не знаю, гдеиди оттуда.

Это то, что я записал в своей записной книжке, просто думая о проблеме:

R = красный, B = синий, G = зеленый

Если мы вынимаем RR, мы ничего не делаем, и в сумке теперь есть n = n-2 токена

Если мы вынимаем RB, мы ничего не делаемg и в сумке теперь есть n = n-2 жетона

Если мы достанем RG, мы ничего не делаем, и в сумке теперь есть n = n-2 жетона

Если мы достанем BB,мы положили 3 красных жетона обратно, и теперь в сумке содержится +1 жетон (так как мы вытащили 2 и добавили 3 обратно)

Если мы возьмем BG, сделайте то же самое, что и выше

Еслимы вынимаем GG, 1 зеленый и 2 синих возвращаются обратно, и теперь в сумке содержится +1 токен

Я думаю, что из этого видно, что со временем сумка будет заполнена или почти заполнена красными токенамипоскольку есть только одна ситуация, когда мы возвращаем токены, которые не являются красными, и две ситуации, когда мы возвращаем 3 красных токена.И всякий раз, когда мы вытаскиваем красный токен, мы ничего не делаем и просто уменьшаем размер токена в пакете до тех пор, пока пакет не опустеет.

Количество зеленых токенов будет уменьшаться относительно количества синих и красных токенов.Мы хотим вытащить красный или синий токен, а не зеленый.

Я не уверен, как доказать это с помощью индукции.Любая помощь будет высоко ценится

РЕДАКТИРОВАТЬ: Спасибо, я думаю, я получил это сейчас

Answer 1

У вас есть три правила:

1. Если один из жетонов красный, ничего не делать.
2. Если оба жетона зеленые, мы помещаем один зеленый жетон и 2 синих жетонаобратно в сумку.
3. Если мы получили один синий жетон, а другой жетон не красный, то мы положили 3 красных жетона обратно в сумку.

Исходя из этого:

1. Предположим, у вас в сумке два зеленых жетона.Ты тянешь их обоих.Один зеленый жетон возвращается. Количество зеленых жетонов уменьшается на 1. В худшем случае вы положите один зеленый жетон в сумку на каждые два вынимаемых вами.В всегда кончатся зеленые жетоны.
2. Каждый раз, когда вы тянете GG, вы добавляете в сумку два синих жетона.Но пункт № 1 говорит, что у вас всегда кончится зеленый, и поэтому вы не сможете добавить больше синего.После этого, всякий раз, когда вы вытаскиваете синий жетон, он остается вне сумки.
3. Каждый красный жетон, который вы извлекаете, остается, если вы не потянете BG или BB.Но в пункте № 2 говорится, что у вас кончится синева, и в этот момент в сумку больше не попадет красное.

Вам придется записать это в формальное доказательство по индукции, ноэто основной подход.

Answer 2

Доказательством служит количество зеленых жетонов в сумке.Базовый случай: когда изначально в сумке нет зеленых жетонов, в сумке никогда не будет зеленых жетонов, поскольку ни одно правило не добавляет их.В этом случае ни одно правило не добавляет синих жетонов, и мы можем удалить только конечное число красных жетонов, прежде чем удалить все синие жетоны, которые не могут быть заменены.Затем все красные жетоны должны быть удалены.

Гипотеза об индукции: для всех начальных конфигураций с до или включением k зеленых жетонов процесс в конечном итоге завершается.

Шаг индукции: мы должны показать процессостанавливается для всех начальных конфигураций с k + 1 зелеными токенами.Для первого розыгрыша есть 6 случаев: 1. Красный / Красный - красные удаляются, и мы остаемся в той же ситуации с k + 1 зелеными.Это может произойти только конечное число раз, прежде чем возникнет другой случай.2. Red / Green - красный и зеленый удалены, и теперь у нас осталось k зеленых жетонов;мы знаем из индукционной гипотезы, что процесс заканчивается с этой точки.3. Красный / Синий - красный и синий удалены, и мы остаемся в той же ситуации k + 1 зеленых.Это может произойти только конечное число раз, прежде чем возникнет другой случай.4. Зеленый / Зеленый - два зеленых удалены, давая случай k-1.По предположению индукции, мы знаем, что процесс заканчивается с этой точки.5. Зеленый / Синий - один зеленый удален, поэтому мы находимся в ситуации с k зелеными.Мы знаем, что процесс заканчивается с этой точки зрения гипотезой.6. Синий / Синий - два блюза удалены.Это может произойти только конечное число раз до того, как возникнет другая ситуация.

Важно: случаи 1, 3 и 6 не могут образовывать замкнутый цикл, поскольку ни один из них не добавляет синих жетонов.Следовательно, эти случаи в целом могут происходить только конечное число раз, прежде чем один из других случаев должен быть обнаружен;поскольку случаи 2, 4 и 5 дают конфигурацию, из которой процесс завершается по предположению индукции, все исходные конфигурации с k + 1 зелеными токенами должны завершаться.

Примечание: если у вас есть R красный, G зеленый и Bсиние жетоны в сумке, сколько розыгрышей вы можете сделать в худшем случае, прежде чем вам гарантированно придется нарисовать зеленый?В худшем случае вы рисуете двойной блюз B / 2, пока не исчерпаете себя, производя дополнительные 1.5B красных жетонов, а затем рисуете (R + 1.5B) / 2 пары красных жетонов до исчерпания, в общей сложности (R + 2.5B) /2 розыгрыша.Это означает, что вы должны в конечном итоге нарисовать грин, постоянно уменьшая количество грин, доступных для рисования, независимо от конфигурации сумки, начальной или другой.Поскольку число зеленых токенов конечно, неотрицательно и уменьшается, процесс должен завершиться.

Answer 3

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