Комбинаторика на Верченко
Ошибка.
Попробуйте повторить позже
Катя и Юра играют в следующую игру. Имеется пустая таблица из одной строки, состоящая из 
пустых ячеек: ( 
),
которые игроки заполняют числами от 0 до 2022. Первым ходит Юра, который выбирает число 
такое, что 
и заполняет 
ячеек. Второй ходит Катя, которая заполняет оставшиеся ячейки. Победитель определяется по следующему правилу: если в результате
получается «счастливая» комбинация чисел - полностью заполненная таблица, в которой числа можно разбить на две непересекающиеся
группы, суммы чисел в которых одинаковы, то выигрывает Катя, в противном случае выигрывает Юра. Например, комбинация ( 
)
не является «счастливой», так как в ней присутствует нечетное число нечетных чисел. С другой стороны, комбинация
является «счастливой», так как 
. У кого из игроков имеется выигрышная стратегия? Ответ
обосновать.
Источники:
Подсказка 1.
Сразу поймём, что нет никакого смысла рассматривать случаи, когда первый игрок заполняет ячеек меньше, чем k-1. Ведь Юра может оставить Кате всего лишь одну ячейку. Так что будем считать, что если он заполнил меньше k-1 ячейки, то Катя заполняет оставшиеся ячейки, кроме последней, нулями.
Подсказка 2.
Теперь если мы докажем, что числа на k-1 ячейках можно разбить на такие 2 группы, что суммы чисел в них будут отличаться не менее чем на 2022, то Катя сможет победить, поставив в последнюю ячейку число, уравнивающее суммы этих групп. Сейчас работать с числами не очень удобно. Попробуйте упорядочить их и разбить на подходящие группы.
Подсказка 3.
Если мы упорядочим числа и распределим в группы через один, то сумма в группах будет отличаться не более чем на 2022. Победа!
Очевидно, что достаточно рассмотреть случай, когда игрок, делающий первый ход, заполняет максимально возможное число ячеек, равное
. Расположим эти 
число в порядке не убывания: 
. Здесь в индексах указаны номера позиций, на
которых стоят эти числа в таблице. Образуем два множества позиций, которые заполнены: 
и 
, беря
указанные числа через одно. Тогда суммы чисел на этих позициях могут отличаться друг от друга не более, чем на 2022.
Поэтому оставшуюся незаполненной позицию можно заполнить числом от 0 до 2022 так, чтобы получилась «счастливая»
комбинация.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
