понедельник, 27 октября 2014 г.

Выборы

Выборы были организованы таким образом, что каждый избиратель писал на своём бюллетене имена N кандидатов. Далее этот бюллетень помещался в одну из N+1 избирательных урн. При подсчёте голосов было отмечено, что каждая урна содержала по крайней мере один бюллетень. Также установлено, что если из каждой урны случайно выбрать по одному бюллетеню, то имя одного из кандидатов обязательно бы присутствовало во всех N+1 выбранных бюллетенях. Докажите, что в этом случае существует имя кандидата, которое будет присутствовать на всех бюллетенях хотя бы одной из урн.

update
Первый - Dendr.
Ответ
Предположим, что нет такого кандидата, чьё имя обязательно будет присутствовать на всех бюллетенях хотя бы одной из урн. Возьмём произвольный бюллетень в первой урне. В нём перечислено N кандидатов. Обозначим их числами от 1 до N. Исходя из нашего предположения мы теперь может найти во второй урне бюллетень, в котором не будет кандидата 1; в третьей урне найдётся бюллетень, в котором не будет кандидата 2 и так далее. Соберем эти N+1 бюллетеней вместе. Получается, что из каждой урны выбрано по одному бюллетеню, но не найдётся ни одного кандидата, чьё имя присутствовало бы на всех выбранных бюллетенях. А это противоречит условию задачи. Следовательно, наше изначальное предположение неверно. То есть, существует имя кандидата, которое будет присутствовать на всех бюллетенях хотя бы одной из урн.

3 комментария:

  1. Во-первых, очевидно, что если в урне один бюллетень, тогда условие выполнено автоматически. Пусть в каждой урне больше бюллетеней.

    Пронумеруем урны от 1 до N+1 и предположим, что для первых N на самом деле нет такого кандидата, который был бы во всех бюллетенях одной из этих урн.

    Докажем, что в (N+1)-й таковой обязательно найдется. Будем вынимать из урн бюллетени по одному в порядке возрастания номеров, пока не дойдем до N-й. По условию задачи, на любом этапе в вынутых бюллетенях есть хотя бы одна общая фамилия. Но не больше N: просто больше некуда.

    Допустим, мы прошли K урн, и в них 1<=M<=Т общих кандидатов.
    Рассмотрим бюллетени в (K+1)-й урне. В любом из них обязательно присутствует хотя бы один из M кандидатов. Но также, по предположению доказательства, любой из них есть не во всех бюллетенях. Это означает, что какой бы бюллетень мы не достали, в нем будет присутствовать от 1 до (M-1) фамилий, общих с первыми K бюллетенями.

    Иными словами, если мы будем доставать бюллетени по одному из урн, то количество общих кандидатов будет строго уменьшаться, пока не достигнет 1.
    Очевидно, что K=1 соответствует M(1)=N. Так как для K=N должно выполняться M(N)>=1, а само M уменьшалось по крайней мере на единицу (N-1) раз, то M(N)<=N-(N-1)=1. Следовательно, M(N)=1.

    Итак, в предположении, что общего кандидата для всех бюллетеней каждой из урн 1-N не существует, должно выполняться условие: если достать из каждой из этих урн по одному бюллетеню, то в них будет один и только один общий кандидат. Пусть это Мистер Икс.

    Рассмотрим теперь бюллетени из урны (N+1).
    В любом из них, по условию, должен быть хотя бы один кандидат, общий для всех остальных. Понятно, что это не кто иной, кроме как Мистер Икс. В таком случае, он встречается во всех бюллетенях этой урны. ЧТД

    ОтветитьУдалить
    Ответы
    1. поправка
      3 абзац 1 строка, в неравенстве читать 1<=M<=N

      Удалить
    2. Похоже, что всё правильно. Моё доказательство отличается, позже опубликую в ответе.

      Удалить