2014 dxdy logo

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

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




На страницу 1, 2  След.
 
 Задача на делимость и про попугаев.
Сообщение08.11.2014, 12:08 
1) Какое наибольшее количество натуральных чисел, не превосходящих 100, можно выбрать так, чтобы для любых пяти выбранных чисел их сумма или произвед. делилось на 3?
Что я заметил:
а) Если все пять выбранных чисел делятся на три, то утверждение выполнено (а таких 33)
б) Чтобы произведение делилось на три, нужно, чтобы хотя бы одно из чисел делилось на три.
в) С учетом пункта б), можно сказать, что нужно заметить, что помимо того, что одно из чисел должно делится на 3, еще и сумма остатков остальных чисел должна делится на 3.
Всевозможные ситуации тогда (которые нас устраивают):
00000
01122
02220
01110
00021
11112
22221
То есть мы можем попробовать взять 27 чисел, которые делятся на три и одну из предложенных комбинаций, затем проверить -- будут ли любые пять чисел, извлеченные из это совокупности удовлетворять условиям задачи.
00000+
01122-
02220-
01110-
00021-
11112-
22221-
Таким образом нужно взять 33 числа, которые делятся на 3.
Верны ли рассуждения?

2) 100 грустных попугаев кидаются друг в друга одним бананом. Грустный попугай, попавший бананом в другого грустного попугая, становится веселым и больше уже не грустнеет. Попугай, в которого попали, выбывает из игры. Каких попугаев больше выбыло из игры — веселых или грустных — к моменту, когда в игре остался один попугай?

За каждый ход выбывает по два попугая. Не может остаться один попугай после очередного хода. Таким образом, такого момента, когда останется один попугай -- не наступит. Правильно?

 
 
 
 Re: Задача на делимость и про попугаев.
Сообщение08.11.2014, 12:34 
1) У меня получилось 38.

2)
champion12 в сообщении #928142 писал(а):
За каждый ход выбывает по два попугая. Не может остаться один попугай после очередного хода. Таким образом, такого момента, когда останется один попугай -- не наступит. Правильно?

Думаю неправильно. Веселый попугай остается в игре и продолжает кидаться бананом.

PS Когда писал предполагаемый ответ на первую задачу так и хотелось написать: 38 попугаев.

 
 
 
 Re: Задача на делимость и про попугаев.
Сообщение08.11.2014, 14:41 
Evgenjy в сообщении #928152 писал(а):
1) У меня получилось 38.

2)
champion12 в сообщении #928142 писал(а):
За каждый ход выбывает по два попугая. Не может остаться один попугай после очередного хода. Таким образом, такого момента, когда останется один попугай -- не наступит. Правильно?

Думаю неправильно. Веселый попугай остается в игре и продолжает кидаться бананом.

PS Когда писал предполагаемый ответ на первую задачу так и хотелось написать: 38 попугаев.


А как так получилось 98?

2) Ок про попугаев.

Я буду обозначать $i|j|k$ -- номер хода, количество грустных попугаев, количество веселых попугаев.

$1|98|1$
$2|96|2$
$3|94|3$
$4|92|4$

Увидел закономерность. $k|98-2(k-1)|k$

В конце должен остаться один попугай, потому $98-2(k-1)+k=1$, отсюда $k=99$, что невозможно. Видно загвоздка в том, что рано или поздно веселых и невеселых станет примерно поровну, потому далее изменится структура. Как же тут быть тогда?

-- 08.11.2014, 14:53 --

Кажется я понял. Число невеселых попугаев всегда будет четно, потому один невеселый попугай не может остаться, значит останется один веселый попугай, верно?

А загвоздка была уж точно в том, что $98-2(k-1)>0$

 
 
 
 Re: Задача на делимость и про попугаев.
Сообщение08.11.2014, 15:13 
champion12 в сообщении #928194 писал(а):
А как так получилось 98?

Получилось 38, а не 98.

 
 
 
 Re: Задача на делимость и про попугаев.
Сообщение08.11.2014, 15:15 
Аватара пользователя
champion12 в сообщении #928194 писал(а):
значит останется один веселый попугай, верно?

Возможно (не читал). Но спрашивали-то нас о другом.

 
 
 
 Re: Задача на делимость и про попугаев.
Сообщение08.11.2014, 15:35 
champion12 в сообщении #928142 писал(а):
100 грустных попугаев кидаются друг в друга одним бананом.

Условие Вашей задачи явно не полно. Не ясна, например, очередность хода (кто бросает банан). При тех условиях, которые сформулированы результат может получится любой.

 
 
 
 Re: Задача на делимость и про попугаев.
Сообщение08.11.2014, 15:36 
Аватара пользователя
champion12 в сообщении #928142 писал(а):
нужно заметить, что помимо того, что одно из чисел должно делится на 3, еще и сумма остатков остальных чисел должна делится на 3.

Почему "еще и"? В условии вроде сказано "или"?

-- 08.11.2014, 16:59 --

Как только после первого броска появился один веселый попугай, он может на каждом шаге выбивать грустных, пока не останется один. Итого вылетит 99 грустных и 0 веселых.

И наоборот, если на каждом шаге очередной грустный будет выбивать веселого и сам веселеть, то вылетит 98 веселых и 1 грустный.

Возможны и промежуточные варианты.

 
 
 
 Re: Задача на делимость и про попугаев.
Сообщение08.11.2014, 16:43 
provincialka в сообщении #928226 писал(а):
champion12 в сообщении #928142 писал(а):
нужно заметить, что помимо того, что одно из чисел должно делится на 3, еще и сумма остатков остальных чисел должна делится на 3.

Почему "еще и"? В условии вроде сказано "или"?

Спасибо! Точно, это все меняет.

Если взять 33 числа, которые делятся на три и еще 4 числа, которые не делятся на три, то получится 37 чисел, если взять любые 5 из них, то их произведение делится на три (так как содержит 3 множителем).
А если думать про сумму, то максимум можно взять 33 числа, которые делятся на три. Если будем брать разные комбинации чисел с разными остатками при делении на 3, то получится, что не для любых 5 чисел их сумма будет делится на 3.
Тогда ответ 37, верно?

-- 08.11.2014, 16:44 --

provincialka в сообщении #928226 писал(а):

Как только после первого броска появился один веселый попугай, он может на каждом шаге выбивать грустных, пока не останется один. Итого вылетит 99 грустных и 0 веселых.

И наоборот, если на каждом шаге очередной грустный будет выбивать веселого и сам веселеть, то вылетит 98 веселых и 1 грустный.

Возможны и промежуточные варианты.


Спасибо. То есть условие задачи не полно?

 
 
 
 Re: Задача на делимость и про попугаев.
Сообщение08.11.2014, 16:47 
Аватара пользователя
champion12 в сообщении #928259 писал(а):
Спасибо. То есть условие задачи не полно?
Ну да, ведь Evgenjy уже сказал вам об этом. Я только описала это подробнее.

-- 08.11.2014, 17:49 --

provincialka в сообщении #928260 писал(а):
и еще 4 числа, которые не делятся на три,
Почему только четыре?

 
 
 
 Re: Задача на делимость и про попугаев.
Сообщение08.11.2014, 17:22 
provincialka в сообщении #928260 писал(а):
Почему только четыре?

Потому как произведения не будут делится на 3, да и суммы не факт , что будут делится

 
 
 
 Re: Задача на делимость и про попугаев.
Сообщение08.11.2014, 17:36 
Аватара пользователя
Все произведения, содержащие одно из 33 чисел будут делиться на 3. Так что исследовать надо только пятерку значений, из которых ни одно на 3 не делится. Тогда надо проверить сумму. Вопрос заключается только в этом: можно ли подобрать 6 не делящихся на 3 чисел, так, чтобы сумма любых пяти делилась на 3?

 
 
 
 Re: Задача на делимость и про попугаев.
Сообщение08.11.2014, 18:12 
provincialka в сообщении #928279 писал(а):
Все произведения, содержащие одно из 33 чисел будут делиться на 3. Так что исследовать надо только пятерку значений, из которых ни одно на 3 не делится. Тогда надо проверить сумму. Вопрос заключается только в этом: можно ли подобрать 6 не делящихся на 3 чисел, так, чтобы сумма любых пяти делилась на 3?

Нет, если все они имеют остаток 1 при делении на 3, так как сумма таких пяти будет иметь остаток два

-- 08.11.2014, 18:14 --

Но можно найти такие 5 чисел, если они имеют остатки 21111

-- 08.11.2014, 18:15 --

Только пока что не ясно причем тут 6 чисел

 
 
 
 Re: Задача на делимость и про попугаев.
Сообщение08.11.2014, 18:21 
Аватара пользователя
champion12 в сообщении #928298 писал(а):
Только пока что не ясно причем тут 6 чисел
Ну, пять ведь вы уже нашли? А вопрос стоял о том, чтобы найти максимальное количество чисел. Надо попробовать сначала шесть. Получится - ищем семь.
champion12 в сообщении #928298 писал(а):
Нет, если все они имеют остаток 1 при делении на 3,
А если не все? Или не 1?

 
 
 
 Re: Задача на делимость и про попугаев.
Сообщение08.11.2014, 18:35 
Спасибо все понял

 
 
 
 Re: Задача на делимость и про попугаев.
Сообщение08.11.2014, 18:48 
Аватара пользователя
Так часто бывает. Человек говорит "спасибо, всё понял" и уходит. Потом в каком-то далёком королевстве на островах южных морей происходит революция, террор, геноцид. Что, как он понял? - неизвестно.

 
 
 [ Сообщений: 20 ]  На страницу 1, 2  След.


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