Комбинаторика, теория чисел

[mr.tumkan]

1)На острове Невезения, где живут только рыцари, которые всегда говорят правду, и лжецы, которые всегда лгут, прошли выборы президента. Кандидатов было двое: Ёлкин и Палкин. На вопрос наблюдателя ООН: "За кого Вы голосовали?" большинство жителей ответили: "За Ёлкина", а на вопрос: "Кто стал президентом?" большая часть жителей ответила: "Палкин". Известно, что рыцари, голосовавшие за проигравшего кандидата, составляют не менее четверти всего населения. Докажите, что президентом стал Палкин.

От противного: Пусть президентом стал Елкин, тогда большая часть жителей сказав, что Палкин стал президентом, соврали. Значит большая часть -- лжецы. А так как на вопрос "за кого голосовали", большая часть должна соврать сказав, Палкин, а по условию "За кого Вы голосовали?" большинство жителей ответили: "За Ёлкина", то получаем противоречия, значит президентом стал Палкин на самом деле.

2) Найдите все простые числа вида $p^4+4$, где $p$ -- простое.

Ясно, что $p^4+4=(p-1)(p+1)(p^2+1)+5$. Притом $(p-1)(p+1)(p^2+1)$ делится на $2,3,4$. А что еще тут можно придумать? Закономерности не найти...

3) ) Пусть $p_1, p_2, . . . , p_n, . . .$ — все простые числа, выписанные в порядке возрастания. Докажите, что при $n\geqslant 12$ выполняется неравенство $p_n>3n$

С чего тут можно начать?

4) Каждая из 100 девушек послала одному или нескольким из 100 юношей свою фотографию. Всего было послано больше 100 фотографий. Докажите, что какой-то из юношей может выкинуть все полученные им фотографии, но при этом фотография каждой девушки останется у кого-либо из остальных юношей.

Почему так? Если, например, все девушки отослали по одной фотографии каждому из 100 мужчин, за исключением Юли, а Юля отправила Коле и Васе, то ясно, что если Вася выкинет 2 фотки (фотку Юли и Маши), то разве будет хоть у кого-то фотка той самой Маши?

[nnosipov]

mr.tumkan в сообщении #921644 писал(а):

Закономерности не найти...

Потому что не там ищете. Попробуйте разложить $p^4+4$ на множители.

-- Ср окт 22, 2014 00:08:31 --

mr.tumkan в сообщении #921644 писал(а):

С чего тут можно начать?

Знаете про метод индукции?

[Brukvalub]

По 2)Нужно иначе разложить на множители.
По 4: А если фотки выбросит НЕ Вася? В условии сказано: "Докажите, что какой-то из юношей может выкинуть все полученные им фотографии"

[ИСН]

mr.tumkan в сообщении #921644 писал(а):

3) (...)
С чего тут можно начать?

C того, почему при $n\ge2$ будет $p_n>$... минуточку, а больше чего оно будет, например? и почему?

mr.tumkan в сообщении #921644 писал(а):

4) Каждая из 100 девушек послала одному или нескольким из 100 юношей свою фотографию. Всего было послано больше 100 фотографий. Докажите, что какой-то из юношей может выкинуть все полученные им фотографии, но при этом фотография каждой девушки останется у кого-либо из остальных юношей.

А здесь обратить внимание на слово

Цитата:

какой-то

Разве это то же самое, что "любой"?

[nnosipov]

mr.tumkan в сообщении #921644 писал(а):

2) Найдите все простые числа вида $p^4+4$, где $p$ -- простое.

Понял, зачем это странное требование простоты числа $p$. Нужно на самом деле, чтобы $p$ не делилось на $5$. И тогда $p^4+4$ будет делиться на ...

[mr.tumkan]

nnosipov в сообщении #921657 писал(а):

mr.tumkan в сообщении #921644 писал(а):

2) Найдите все простые числа вида $p^4+4$, где $p$ -- простое.

Понял, зачем это странное требование простоты числа $p$. Нужно на самом деле, чтобы $p$ не делилось на $5$. И тогда $p^4+4$ будет делиться на ...

$p^4+4$ имеет остаток $0$ или $1$ при делении на $5$, если один, то число $p^4+4$ -- простое, если ноль, то $p^4=5n$. А как дальше? Я не вижу другого разложения...

-- 21.10.2014, 20:31 --

ИСН в сообщении #921655 писал(а):

mr.tumkan в сообщении #921644 писал(а):

3) (...)
С чего тут можно начать?

C того, почему при $n\ge2$ будет $p_n>$... минуточку, а больше чего оно будет, например? и почему?

mr.tumkan в сообщении #921644 писал(а):

4) Каждая из 100 девушек послала одному или нескольким из 100 юношей свою фотографию. Всего было послано больше 100 фотографий. Докажите, что какой-то из юношей может выкинуть все полученные им фотографии, но при этом фотография каждой девушки останется у кого-либо из остальных юношей.

А здесь обратить внимание на слово

Цитата:

какой-то

Разве это то же самое, что "любой"?

Теперь понятно, что по индукции все выходит в задаче про $p_1,...,p_n,...$
Про слово какой-то теперь понятно, но с чего теперь начать решение задачи?

[ИСН]

mr.tumkan в сообщении #921660 писал(а):

если ноль, то $p^4=5n$. А как дальше? Я не вижу другого разложения...

И не надо. Найдёте в другой раз. Задача решена, и всё.

-- менее минуты назад --

mr.tumkan в сообщении #921660 писал(а):

Про слово какой-то теперь понятно, но с чего теперь начать решение задачи?

Допустим, никто не может - т.е. любой не может выкинуть свои фотки, потому что какая-то девушка послала свою только ему одному. Сколько у нас таких любых? А девушек сколько?

[mr.tumkan]

Спасибо, все теперь понятно.