alt text

задан 12 Май '17 18:42

Когда мы не можем выбрать? Когда при последнем выборе, мы выбираем достоинства, которые мы уже выбирали ранее.
Всего 13 достоинств в каждой по 4-и карты.
1-ый выбор: Выбираем любую карту,
2-ой выбор: Т.к. в пред. стопке было 13 карт, то она вмещает себя хотя бы 4-и различных достоинства(один из которых мы выбрали) и на этом ходу мы
точно можем выбрать не повторящ. ранее.
3-ий выбор: Опять же, в пред. стопке было хотя бы 4-и различных, два из
которых мы выбрали уже, выбираем 3.
4-ый выбор: Выбираем остав.

(12 Май '17 19:41) Williams Wol...

@Williams Wol...: здесь не 4 стопки с 13 картами в каждой, а наоборот -- 13 стопок с 4 картами. Поэтому выбор надо совершать 13 раз, а не 4.

(12 Май '17 21:43) falcao
10|600 символов нужно символов осталось
1

Здесь надо проверить, что выполнено условие из теоремы Холла о паросочетаниях. Рассмотрим какие-то k из 13 стопок, и проверим, что среди 4k карт, которые в них входят, встречаются карты как минимум k различных достоинств. Допустим, что это не так, и что различных достоинств строго меньше k. Для каждого из таких достоинств во всей колоде имеется ровно 4 карты данного достоинства. Тогда всего карт получается строго меньше 4k -- противоречие.

Для формулировки на языке юношей и девушек получается такая модель: "юноши" -- номера стопок, "девушки" -- достоинства карт. "Знакомство" между "юношей" и "девушкой" означает, что в данной стопке имеется хотя бы одна карта данного достоинства. Выше мы проверили, что любые k "юношей" знакомы в совокупности как минимум с k "девушками".

ссылка

отвечен 12 Май '17 21:42

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,296

задан
12 Май '17 18:42

показан
427 раз

обновлен
12 Май '17 21:43

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru