Дано N палочек. Два игрока ходят по очереди. за один ход игрок может либо добавить в кучу...

Question

Дано N палочек. Два игрока ходят по очереди. за один ход игрок может либо добавить в кучу 1 палочку, либо удвоить количество палочек. Выигрывает тот, кто своим ходом сделает в куче N палочек или больше (N взять свое).
Вопрос 1: Сколько палочек может быть в куче, чтобы своим первым ходом гарантированно выиграл 1-й игрок, 2-й игрок.
*Вопрос 2: Сколько палочек может быть в куче, чтобы 1-й игрок выиграл не первым ходом, а ровно вторым

Comments

желательно со схемой(деревом)палочек:)

Answer 1

ОТВЕТ1: ходы А=+1, Б=х2. для 1 игрока: >=N/2 ( ходит Б) для 2 игрока: >=(N/2)-1, если первый сходит А. N/4 <= x < N/2, если первый сходит Б. Объединяем промежутки: (N/2)-1 ( ходит Б) ОТВЕТ2: например (N/2)-2

Comments

спасибо большое за решение!Только не могли бы пояснить почему мы делим N на 2,4?И по идее же от одной кучки(то бишь от одного числа)идут две стрелки(например,было 7 камней,а после хода первого игрока стало 8 и 14,так как он прибавил 1 и умножил на 2)

---

идут две кучки( как в примере для второго игрока), но нам нужно чтоб игрок точно победил( не важно к какой кучке это приведёт)

---

допустим Н=10. делим на 2, чтоб узнать наименьшее кол-во камней, необходимых для выигрыша(5*2=10- выигрыш)

---

про 4: допустим, что первый игрок ходит умножением кучки на 2. палочек должно быть меньше чем N/2( ведь нам не нужно чтоб он победил) НО нам нужно, чтоб после хода 1 игрока, кол-во палочек стало >=N/2( чтобы 2 игрок победил) значит делим (N/2) на 2( ведь 1 игрок ходит умножением) . тут и получается N/4 - минимальное кол-во палочек для победы второго игрока, если первый ходит умножением

---

спасибо большое еще раз за помощь и за объяснение!:)