1) В 50 коробках лежат 100 конфет. Девочка и мальчик берут поочередно по конфете. Может ли мальчик добиться того, чтобы последние 2 конфеты лежали в одной коробке?
Выигрышной стратегии за мальчика я не вижу. Может быть, Вы сможете ее найти.
2) В строчку выписаны натуральные числа от 1 до 20. Двое по очереди ставят перед этими числами знак + или — (изначально перед числами ничего не стоит, т.е каждый сделает по 10 ходов). Первый хочет добиться, чтобы значение получившегося выражения было как можно меньше по абсолютной величине, а второй — как можно больше. Какое наибольшее по абсолютной величине значение может обеспечить второй игрок?
Думаю, ответ 12(если первый ставит в 1, второй — в 20, первый — в 19, второй — в 18..), но строго д-ва не знаю :(
В первой задаче выигрышная стратегия есть — на каждом шагу мальчик должен поддерживать одинаковое число конфет в коробках (т.е. если девочка взяла из первой — брать из второй и наоборот). После того, как в каждой коробке останется по две конфеты, наоборот, повторить девочкин ход. И тогда как раз в одной коробке останется две, а во второй — 0.
UPD: невнимательно прочитал условие, каюсь.
Там 50 коробок, а не две. И вообще не указано, как распределены конфеты по коробкам, а это важно.
Ну что ж, по принципу Дирихле, в какой-то коробке точно будут две конфеты. Видимо, задача в том, чтобы вне зависимости от первоначального распределения найти способ, позволяющий оставить две конфеты.
1,3,1,3... и так 25 раз Т.е не обязательно, что в какой-то коробке будут 2 конфеты
Имеется в виду "как минимум две конфеты". То есть если есть три, то есть и две.
Вторую задачу нужно уточнить. Если оба игрока могут ставить и +, и -, то первый может обеспечить себе хотя бы 10-ку (поставив минус перед 20, дальше второй — плюс перед 19 и т.д.) А вообще, на эту задачу можно написать решающий алгоритм, если правильная стратегия неочевидна.
второму выгоднее поставить не + перед 19, а минус, поскольку 39 > 1 (нас интересует абс. величина). Что именно нужно уточнить?
Могут ли оба игрока ставить оба знака? Или же одному принадлежит только +, второму только -?
Да, могут оба знака.
[спойлер4]
Кто нибудь может подсказать как решить эту задачу (и еще 6-ю по ссылке выше): [hidden]
в первой задаче кажется работает такая стратегия:
если есть коробка с одной конфетой, опустошаем ее, иначе берем конфету из коробки, в которой не 2 конфеты (такая всегда будет, т. к. кол-во конфет перед ходом мальчика нечетное). Соображения по поводу того, почему это работает:
девочке нужно как можно больше коробок с одной конфетой, мальчику — наоборот. Худший случай, когда в одной коробке 51 конфета, в остальных по одной. Но здесь мальчик все равно успевает.
Как это доказать строго еще не придумал.
Такая идея мне приходила в голову, но я тоже не понимаю, как ее д-ть
Для мальчика проигрышная ситуация, если набор конфет перед последним ходом 1 1 1.
Если попытаться восстановить цепочку ходов, которая привела к такой ситуации, получится следующее:
1 1 1
1 1 2
1 1 1 2
1 1 2 2
1 1 1 2 2
1 1 2 2 2
...
Видно, что для такой ситуации нужна 51 коробка.
upd: ошибся, цепочка ходов неоднозначна, например, может быть 1 1 1 3 вместо 1 1 2 2, но, в любом случае, для каждого хода мальчика нужна дополнительная коробка с 1.
Если на каком-то шагу на ходе мальчика нету коробок с 1 конфетой, то он победил. Потому, что он берет с коробки там, где не 2, а когда девочка делает 1 в коробке, то он забирает с этой коробки.
Если же на каждом шагу мальчик забирает с коробки, где 1 конфета, то 49 коробок станут пустими, то есть оставшиеся 2 конфеты будут в 1 коробке.
Если на каком-то шагу на ходе мальчика нету коробок с 1 конфетой, то он победил. Ваше объяснение мне не очень понятно.
Тогда на каждом шагу после этого шага есть 2 варианта:
1) нету коробок с одной конфетой — тогда он берет там где не 2(почему он так может обяснил NuM)
2) девочка своим ходом сделала в какой-то коробке 1 конфету, тогда мальчик ее забирает.
В обоих ситуациях после хода мальчика не остаеться коробок с 1 конфетой. Поетому и в конце не будет коробки с одной конфетой.
Да, все правильно. Спасибо