2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Комбинаторика, теория чисел
Сообщение21.10.2014, 19:54 
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 фотки (фотку Юли и Маши), то разве будет хоть у кого-то фотка той самой Маши?

 
 
 
 Re: Комбинаторика, теория чисел
Сообщение21.10.2014, 20:06 
mr.tumkan в сообщении #921644 писал(а):
Закономерности не найти...
Потому что не там ищете. Попробуйте разложить $p^4+4$ на множители.

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

mr.tumkan в сообщении #921644 писал(а):
С чего тут можно начать?
Знаете про метод индукции?

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

 
 
 
 Re: Комбинаторика, теория чисел
Сообщение21.10.2014, 20:12 
Аватара пользователя
mr.tumkan в сообщении #921644 писал(а):
3) (...)
С чего тут можно начать?
C того, почему при $n\ge2$ будет $p_n>$... минуточку, а больше чего оно будет, например? и почему?
mr.tumkan в сообщении #921644 писал(а):
4) Каждая из 100 девушек послала одному или нескольким из 100 юношей свою фотографию. Всего было послано больше 100 фотографий. Докажите, что какой-то из юношей может выкинуть все полученные им фотографии, но при этом фотография каждой девушки останется у кого-либо из остальных юношей.
А здесь обратить внимание на слово
Цитата:
какой-то
Разве это то же самое, что "любой"?

 
 
 
 Re: Комбинаторика, теория чисел
Сообщение21.10.2014, 20:14 
mr.tumkan в сообщении #921644 писал(а):
2) Найдите все простые числа вида $p^4+4$, где $p$ -- простое.
Понял, зачем это странное требование простоты числа $p$. Нужно на самом деле, чтобы $p$ не делилось на $5$. И тогда $p^4+4$ будет делиться на ...

 
 
 
 Re: Комбинаторика, теория чисел
Сообщение21.10.2014, 20:28 
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,...$
Про слово какой-то теперь понятно, но с чего теперь начать решение задачи?

 
 
 
 Re: Комбинаторика, теория чисел
Сообщение21.10.2014, 20:41 
Аватара пользователя
mr.tumkan в сообщении #921660 писал(а):
если ноль, то $p^4=5n$. А как дальше? Я не вижу другого разложения...
И не надо. Найдёте в другой раз. Задача решена, и всё.

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

mr.tumkan в сообщении #921660 писал(а):
Про слово какой-то теперь понятно, но с чего теперь начать решение задачи?

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

 
 
 
 Re: Комбинаторика, теория чисел
Сообщение22.10.2014, 13:49 
Спасибо, все теперь понятно.

 
 
 [ Сообщений: 8 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group