на карточках написано по три различных числа. Каждое число встречается на карточках не более 10 раз. Докажите, что если карточек больше 285, то можно найти 11 карточек, на которых все числа различные.
Ответы
Ответ:
приведём алгоритм выбора непересекающихся карточек
Пошаговое объяснение:
берём случайную карточку. назовём её а1. откладываем в сторону все карточки, на которых встречается хотя бы одно из чисел из карточки а1. их при дальнейшем выборе не трогаем. на каждое число не более 9 таких совпадений, значит всего мы отложили не более 27 карточек. вместе с а1 их теперь 28. берём случайную карточку из оставшихся (а2). она точно не имеет общих чисел с а1, т.к. все карточки, имеющие общие числа с а1, отложены. вместе с а2 откладываем не более 27 карточек, пересекающихся с а2. продолжая так делать, мы получим 10 карточек а1 - а10, и не более 270 отложенных карточек. берём новую карточку из остатка колоды (а11), она не имеет пересечений с а1-а10. таким образом, если карточек 281 или больше, то этот алгоритм позволяет выбрать 11. непересекающихся карточек. если карточек больше 285, то их больше 281, и мы, применяя наш алгоритм, можем выбрать 11 непересекающихся карточек. ч т.д.