На доске 40×3 (40 столбцов и 3 строки) стоят несколько фишек, причём в каждой клетке не более одной фишки. Петя выбирает n столбцов и одну строку и убирает все расположенные на них фишки.
При каком наименьшем n Петя заведомо может убрать хотя бы половину фишек?
Шаг 1. Выбор строки.
Петя может выбрать строку с наибольшим числом фишек. Пусть M – максимальное число фишек в одной из строк, то есть M = max{a, b, c}. Тогда M ≥ T/3.
Шаг 2. Фишки, расположенные не в выбранной строке.
Если Петя выбирает строку с M фишками, то оставшиеся фишки (на двух других строках) составляют T – M. Фишки в этих двух строках распределены по 40 столбцам. При неблагоприятном распределении противника фишки можно распределить “равномерно” по столбцам, то есть в каждом столбце оказывается примерно (T – M)/40 фишек (на двух оставшихся стр...
Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит
Попробуй решить по шагам
Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение
