Question

Остап бендер и киса воробьянинов билеты на пароме через волгу. в очередной рейс отправилось 2015 пассажиров. их всех запустили на паром, после чего остап и киса стали продавать билеты. каждый пассажир купит билет, если его об этом попросят трижды. сначала остап просит приобрести билет одного из еще безбилетных пассажиров, потом то же самое делает киса (просит приобрести билет одного из еще безбилетных пассажиров), потом снова остап, потом снова киса, и так далее до тех пор, пока все пассажиры не будут с билетами. продажу какого наибольшего количества билетов может обеспечить себе остап, как бы ни действовал киса?

Answer 1

Остап может обеспечить продажу всех билетов. Для этого предлагается следующий алгоритм. Остап просит первого пассажира в первый раз. У Кисы есть две возможности - попросить того же пассажира, или другого. Если он попросит того же, то Остап просит его в третий раз и заносит себе в копилку первый проданный билет, после чего Кисе все равно придется придется просить второго пассажира. Остап в первый раз попросит третьего, и т.д. В результате каждый раз, как только Киса делает вторую Остап делает третью и получает очередное очко. Первые же будут чередоваться, но поскольку Остап был первым, а число пассажиров нечетно, он же сделает первую и для последнего пассажира, после чего у Кисы не останется ни одного хорошего хода