Есть кучка из 2017 камней. Петя и Вася по очереди берут из неё камни (начинает П...

August 2021 1 24 Report

Есть кучка из 2017 камней. Петя и Вася по очереди берут из неё камни (начинает Петя). Разрешается брать строго меньше половины от текущего числа камней. Проигрывает тот, кто не может сделать ход. Кто выиграет?

Answers & Comments

ProGroomer

Verified answer

Посмотрим, какое количество камней могло остаться в конце игры:
Такое, что половина этого количества ≤ 1 (иначе можно взять 1 камень и это будет не конец игры).
То есть могло остаться 0, 1 или 2
Если осталось 0 (или 1), то на предыдущем ходе количество камней было меньше, чем 0 * 2 = 0 (или 1 * 2 = 2), то есть < 0 камней (1 камень), чего быть не могло. Значит осталось 2 камня.
Теперь мы знаем, что тот, кому после очередного хода выпала кучка с 2 камнями, проигрывает.
Значит тот, кому выпала кучка с более, чем 2 камнями, но менее, чем с 2 * 2 - выигрывает (это кучка из 3 камней. Он берет 1 камень и выигрывает).
Проводя аналогичные рассуждения мы увидим, что тот, кому выпадает кучка с 4 камнями - проигрывает (единственный возможный ход - взять 1 камень, что приводит к 3 камням, а тот, кто начинает с кучки из 3 камней выигрывает).

Можно бы было дальше посмотреть, что тот, у кого в кучке 8 камней проиграет, а тот, у кого в кучке 5 .. 7 камней - выиграет. Но мы остаток докажем методом математической индукции.
Пытаемся доказать предположение, что тот, кому попалась кучка из $2^n$ (n строго больше 1) элементов проиграет, а тот, кому попалась кучка с числом камней, не равным степени 2 - выигрывает.

База индукции у нас уже есть. Предположим, что тот, у кого выпало $2^k$ камней - проигрывает, а $2^{k-1}+1\, ...\, 2^k-1$ - выигрывает. Докажем, что тот, кому выпало $2^k+1\, ...\, 2^{k+1}-1$ камней выиграет, а тот, кому выпало $2^k$ камней - проиграет.

1) Пусть выпало $2^k + l$ камней, $0 \ \textless \ l \ \textless \ 2^k$ . Тогда мы можем взять эти l камней. Дейтсвительно, из того, что
$l \ \textless \ 2^k$
следует, что
$2l \ \textless \ 2^k+l \Rightarrow l \ \textless \ {2^k+l\over 2}$
Итак, оппонент после этого хода попадает на кучку из $2^k$ камней и, по предположению индукции, проигрывает

2) Пусть выпало $2^{k+1}$ камней. Тогда можно взять любое количество от 1 до $2^k -1$ (так как $2^k$ ровно в 2 раза меньньше, чем $2^{k+1}$ , а по условию можно взять строго меньше, чем в 2 раза). Тогда мы получим кучку с количеством камней от
$2^{k+1}-(2^k-1)=2^k+1$
до
$2^{k+1}-1$
Начиная с которой по пункту 1) этого доказательства оппонент выигрывает.
Что и требовалось доказать.

Таким образом, так как 2017 - это не степень двойки, то начиная с 2017 Петя победит. Его стратегия - забирать камни так, чтобы в кучке оставалось число камней, являющееся точной степенью 2.

4 votes Thanks 1

Knvlva Очень сложноноосень правильно)))

Knvlva извини, случайно ткнула в кнопку отметить как нарушение

Knvlva случайно!

Answers & Comments

Verified answer

v treugolnike abc a 15 b 75 provedena vysota ch 2 najdite ab

kak budet dvenadcat po angl

rifmy k slovu karusel 1 3 rifmy

morfemnyj po chastyam slova i orfograficheskij razbory slova obstoyatelstvo

opredelite rasstoyanie mezhdu yuzhnoj amerikoj i avstraliej po 20 yuzhnoj shiroty pozh

u tani est ochen mnogo krasnyh zhyoltyh i sinih rezinok dlya volos ona zaplela s

perechislite vse razdely biologii

kto napechatal pervuyu knigu na rusi

skolko oktav u fortepiano perechislite ih pozhalujsta

dvuznach chislo ya vstavila nol mezhdu ciframi desyatkov i edinic v etom chisle po

рекомендуемые вопросы

Helpful Links

Helpful Social