В 120-квартирном доме живут 119 человек. Квартира называется перенаселённой, если в ней живёт не менее 15 человек. Каждый день жильцы одной из перенаселённых квартир ссорятся и разъезжаются по разным квартирам. Верно ли, что переезды рано или поздно прекратятся?

задан 10 Окт '17 18:14

Решение задачи основано на том, что 119 - это не спроста!

1 + 2 + 3 + ... + 15 = 120

(11 Окт '17 19:58) kipot_l

@kipot_l: специфика треугольного числа как раз была понятна сразу. Идея полуинвариантов также хорошо известна. Тем не менее, я не нашёл подходящей функции (или оценки) не только сходу, но даже при сравнительно долгом размышлении (сегодня и по пути на работу думал, и во время перекуров). Поэтому я как бы всецело "заинтригован". Более того, я вспоминал задачу из "Кванта" про манипуляцию 15 стаканчиками, достаточно сложную (ссылку могу дать). В решении там рассматривался полуинвариант, но здесь я все аналогичные характеристики перебрал, и ничего не подошло!

(11 Окт '17 20:32) falcao

@falcao, у меня с этой задачей получился небольшой конфуз. Я слепил неправильное решение, используя в качестве "полуинварианта" общее количество жильцов в перенаселённых квартирах и в квартирах, где N = 14. Потом посмотрел задачу в Инете. Увидел только, что надо использовать: S = 1 + 2 + 3 + ... + 15 = 120.

А не всякие изобретения типа: S = 15*7 + 14 = 119 ...

(11 Окт '17 23:02) kipot_l

@falcao, После самостоятельного анализа этой идеи получилось следующее: Упорядочим квартиры по количеству жильцов:

1 класс > 15 жильцов;

2 класс = 14 жильцов;

16 класс = 0 жильцов.

Отметим, что для того, чтобы в каждом классе содержалось не менее 1 элемента, необходимо не менее 120 жильцов. Покажем, что перенаселённые квартиры исчезнут через конечное число расселений.

(11 Окт '17 23:13) kipot_l

Для этого достаточно показать, что:

1) в такой классификации всегда есть пустая ненулевая строка;

2) пустая строка в классификации не может исчезнуть без появления новой пустой строки;

3) пустая строка в классификации может «двигаться» только вверх.

Процесс закончится образованием нулевой строки в первом классе.

Для 120 жильцов расселения могут прекратиться, а могут и не прекращаться, а происходить циклически.

(11 Окт '17 23:13) kipot_l

@falcao, что тут считать инвариантом, полуинвариантом, не знаю. Пустую строку в классификации?

(11 Окт '17 23:17) kipot_l

@falcao, Если про переворачивание стаканчиков, то я вроде решал, только для 7-ми стаканчиков. А далее можно рассмотреть эту задачу для 3-х, 8, 9, 10 стаканчиков... Чтобы было предельно понятно ученикам...

(11 Окт '17 23:30) kipot_l

@kipot_l: идея доказательства мне теперь понятна, и ясно также, что здесь уменьшается. Ясно, что из соображений количества мы не можем указать одновременно квартиры с населением >=15, >=14, ... , >=1. Значит, где-то есть "зазор". Если k -- число квартир до этого "зазора", то значение k всегда строго уменьшается. Максимальная длина будет для конфигурации 15,14,...,3,2.

Для числа стаканчиков я бы брал треугольные числа. Если это 1+2+3, то граф можно нарисовать явно. А для больших значений задача уже сложна -- примерно как для произвольного n.

(11 Окт '17 23:41) falcao

@falcao, про стаканчики именно про вот такую задачу идёт речь (?):

На столе стоят 7 стаканов, все вверх дном. Разрешается за один ход перевернуть любые 4 стакана. Можно ли за несколько ходов добиться того, чтобы все стаканы стояли правильно?

Инвариант - чётность. Обе задачи из книги С.А. Генкина "Ленинградские математические кружки".

(12 Окт '17 0:03) kipot_l
1

@falcao, вот, выкопал в Инете, якобы решение про 119 жильцов:

http://school28ola.sk6.ru/sites/default/files/archive/2014_matematika_8_ochnyiy_teoriya_solution.pdf

Прошу оценить, а то я уже ничего не соображаю...

(12 Окт '17 0:31) kipot_l

@kipot_l: с рассмотрением количества пар -- хорошее решение. Там совсем другая идея, и оценка чуть похуже (типа 67), но всё равно красиво.

Задача с переворачиванием стаканов -- совсем на другую тему. Она достаточно простая. Я имел в виду вот это. Ссылка на "Квант" там сейчас вроде не открывается, но можно её найти непосредственно через журнал.

(12 Окт '17 2:55) falcao
показано 5 из 11 показать еще 6
10|600 символов нужно символов осталось
0

Распределим квартиры по убыванию числа жителей: $% a_1, a_2,...$%

Тогда чтобы процесс не прекращался необходимо : $%a_1\ge 15, a_2\ge 14,..., a_{14}\ge 2, a_{15}\ge1 $%

ссылка

отвечен 12 Окт '17 10:21

@Sergic Primazon, Ваше утверждение присутствует в анализе этой задачи. Осмелюсь его уточнить. Чтобы процесс мог стать циклическим, достаточно, чтобы имелись такие квартиры:

a1=15, a2=14, ... a14=2, a15=1, а16=0 (!); S = 120.

Но это не ответ и не решение задачи.

При S = 119 процесс не может стать циклическим и закончится через конечное число шагов. В этом суть.

Единственно известное мне решение задачи - по ссылке: http://school28ola.sk6.ru/sites/default/files/archive/2014_matematika_8_ochnyiy_teoriya_solution.pdf

(12 Окт '17 19:19) kipot_l

@kipot_l: понятно ведь, что @Sergic Primazon имел в виду. Это та же идея, которая уже звучала в комментариях. Если процесс длится ещё один шаг, то должна быть квартира >=15. Если ещё два шага, то должна быть помимо неё квартира >=14, так как после расселения в квартиру добавляется не более одного жильца, и без неё у нас не получится >=15. И так далее, по шагам: если возможны ещё три расселения, то налицо три квартиры >=15, >=14, >=13. В итоге окажется наличие квартир >=15, >=14, ... , >=1, что невозможно по количеству.

(12 Окт '17 20:53) falcao

@falcao, всё сказанное Вами это только слова, слова... Если имеется 5-6 квартир >=15, то можно прекрасно жить (расселяться) 5-6 шагов без квартир по 13-14 жильцов...

Далее, если квартиры с 14 жильцами нет на 2-ом шаге, то она может появиться на 3-4 шаге...

И можно долго гонять зайца по кругу...

(13 Окт '17 18:33) kipot_l

@kipot_l: Вы бы лучше проанализировали сказанное, потому что идея вполне понятная, и она работает. Это же обычная индукция. Утверждение: если процесс будет длиться ещё k шагов, то должны быть квартиры численностью >=15, ... , >=15-(k-1) в количестве k штук. Индукция: при k=1 это очевидно. Пусть k > 1. Расселили одну квартиру >=15. Процесс далее будет длиться ещё k-1 шаг. Налицо >=15,...,>=15-(k-2) по предположению. После расселения в этих квартирах добавилось не более одного. Значит, до расселения было >=14,...,>=15-(k-1), плюс расселяемая квартира >=15.

(13 Окт '17 19:47) falcao

Кстати, любая квартира >=15 автоматически >=14, а также >=13, поэтому я согласен, что расселяться в Вашем примере можно без квартир по 14 или 13 жильцов ровно.

(13 Окт '17 19:48) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×7

задан
10 Окт '17 18:14

показан
832 раза

обновлен
13 Окт '17 19:48

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

по почте:

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

по RSS:

Ответы

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

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