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