В компании из n человек (n>3) каждый узнал по новости. Созвонившись, двое рассказывают друг другу все известные им новости. Как за 2n-4 звонка все смогут узнать все новости?




Скачать 36.28 Kb.
НазваниеВ компании из n человек (n>3) каждый узнал по новости. Созвонившись, двое рассказывают друг другу все известные им новости. Как за 2n-4 звонка все смогут узнать все новости?
Дата публикации24.05.2014
Размер36.28 Kb.
ТипРассказ
skachate.ru > Информатика > Рассказ

Индукция


Математическая индукция помогает коротко записать строгое решения, но не объясняет, как его придумать, и в чем его смысл.

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

  1. В компании из n человек (n>3) каждый узнал по новости. Созвонившись, двое рассказывают друг другу все известные им новости. Как за 2n–4 звонка все смогут узнать все новости?

^ Целься сверху. Если конструкция для n+1 не единственна, то связь с конструкцией для n надо осуществлять «спуском из n+1», а не «подъёмом из n». В частности, надо убедиться, что всякая конструкция для n+1 получается из конструкции для n.

Пример. Если в графе число ребер не меньше числа вершин, то в нем есть цикл.

  1. На клетчатой бумаге нарисован многоугольник площади n со сторонами на линиях сетки. Докажите, что его периметр не превосходит 2n+2.
^

Доказывай больше


Для шага индукции может потребоваться больше свойств, чем мы хотим доказать. Нередко эти дополнительные свойства доказывают тоже по индукции, расширив на них доказываемое утверждение. Например, вместо неравенства 1/12 + 1/23 +…+1/(n–1)n < 1 легче доказывать равенство 1/12 + 1/23 +…+1/(n–1)n = 1 – 1/n.

  1. Дан равносторонний треугольник со сторонами длины 1. За один ход можно увеличить одну из сторон треугольника, но так, чтобы он остался треугольником. Докажите, что после n ходов наибольшая сторона будет меньше (n+2)-го члена ряда Фибоначчи 1, 1, 2, 3, 5, 8, 13, …

Рекурсия


Редукция сводит решение задачи к более простой. Пусть удается свести к такой же задаче с меньшим значением полуинварианта. Если полуинвариант не может уменьшаться бесконечно, а для его крайних значений задача решена, то это – рекурсия. Такую цепочку редукций тоже оформляют как индукцию, объявляя полуинвариант параметром индукции.

Пример. Сумма углов в невыпуклом n-угольнике равна 180(n–2).

  1. В городе 100 домов. Какое наибольшее число замкнутых непересекающихся заборов можно построить так, чтобы любые два забора ограничивали разные группы домов?

  2. Докажите, что любая правильная дробь может быть представлена в виде (конечной) суммы попарно различных дробей с числителем 1 и натуральным знаменателем.

Индукция незаменима при логической рекурсии

Он думал, что я думала, что думал он я сплю

  1. Двум логикам сообщили на ухо два натуральных числа, а вслух сообщили, что числа отличаются на 1. Далее их по очереди много раз спрашивают, знают ли они число другого, и те вслух говорят «Да» или «Нет». Докажите, что рано или поздно кто-то скажет «Да».

  2. 10 бандитов ограбили банк на миллион долларов и уселись в ряд за стол делить деньги. Сначала первый предлагает, кому сколько: мне столько-то, второму столько-то и т.д., и все 10 голосуют. Если «за» не менее половины, то предложение принимается, каждый получает предложенную долю, и все расходятся. Если более половины голосуют «против», первого убивают, и тогда уже второй бандит предлагает кому сколько на тех же условиях, и т.д.

Каждый бандит руководствуется в первую очередь желанием выжить, во вторую (если жизнь вне опасности) – получить побольше денег, в третью (если на жизнь и сумму это не влияет) – не убивать без необходимости (дело-то не последнее!). Как распределятся деньги, если все бандиты будут действовать и рассуждать абсолютно логически?

Московские сборы, 9.2 класс, А.Шаповалов www.ashap.info 11 апреля 2013 г.
^

Индукция. Для самостоятельного решения


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

И2. Есть гири с номерами от 1 до n, для каждого k вес k-й гирьки целый и не превосходит k. Докажите, что все гири можно разбить на две кучки равного веса.

И3. Отряд девочек отправился в поход. После того, как они вернулись, их родителям стало известно, что хотя бы одна из них искупалась в походе без разрешения, и каждый решил высечь свою дочь, если узнает о том, что она купалась. Каждое утро девочки ходят в школу и обмениваются слухами о том, кто искупался в походе и кого высекли родители, которые сообщают вечером родителям (исключая информацию о том, купались ли они сами). Через 13 дней несколько отцов, получив очередную порцию информацию, догадались о провинности их дочерей и высекли их. Сколько детей получило в этот вечер наказание?

И4'. Докажите, что в выпуклом n-угольнике нельзя выбрать больше n диагоналей так, чтобы любые две из них имели общую точку (общая точка может быть и концом диагонали).

И5. Можно ли отметить на плоскости несколько точек так, чтобы на расстоянии 1 от каждой отмеченной точки находилось ровно 10 отмеченных?

И6. На доске написаны 11 чисел: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024. За ход разрешено стереть любые два и записать вместо них модуль их разности. Докажите, что ровно за 10 ходов можно получить на доске любое нечетное число от 1 до 1023.

Московские сборы, 9.2 класс, А.Шаповалов. 11 апреля 2013 г.

Похожие:

В компании из n человек (n>3) каждый узнал по новости. Созвонившись, двое рассказывают друг другу все известные им новости. Как за 2n-4 звонка все смогут узнать все новости? icon«Новости раздела Новости»
Я не являюсь владельцем проектов, которые размещенные на сайте, Все проекты представлены исключительно для ознакомления
В компании из n человек (n>3) каждый узнал по новости. Созвонившись, двое рассказывают друг другу все известные им новости. Как за 2n-4 звонка все смогут узнать все новости? iconТекст 6 Прочитайте тест и выполните задания 1-13
Что за причуда: в двадцатом веке -письма! (3)Как будто нет телеграфа и телефона. (4)Как будто нельзя за пять минут (теперь это делается...
В компании из n человек (n>3) каждый узнал по новости. Созвонившись, двое рассказывают друг другу все известные им новости. Как за 2n-4 звонка все смогут узнать все новости? iconПодготовила: Ученица 10 «Б» класс
Как рассказал корреспонденту агентства «Минск-Новости» куратор проекта Сергей Тимохов, все картины выполнены в виде иллюстраций к...
В компании из n человек (n>3) каждый узнал по новости. Созвонившись, двое рассказывают друг другу все известные им новости. Как за 2n-4 звонка все смогут узнать все новости? iconНовости (Категория модуля «Новости»)
Фиксированная по ширине. Кроме слайдера на главной странице (см шаблон «Главная широкая»)
В компании из n человек (n>3) каждый узнал по новости. Созвонившись, двое рассказывают друг другу все известные им новости. Как за 2n-4 звонка все смогут узнать все новости? iconНовости Сети
Если вы хотите, чтобы ваши новости были включены в Ленту новостей мпд, присылайте их на адрес
В компании из n человек (n>3) каждый узнал по новости. Созвонившись, двое рассказывают друг другу все известные им новости. Как за 2n-4 звонка все смогут узнать все новости? iconНовости Сети
Если вы хотите, чтобы ваши новости были включены в Ленту новостей мпд, присылайте их на адрес
В компании из n человек (n>3) каждый узнал по новости. Созвонившись, двое рассказывают друг другу все известные им новости. Как за 2n-4 звонка все смогут узнать все новости? iconНовости Сети
Если вы хотите, чтобы ваши новости были включены в Ленту новостей мпд, присылайте их на адрес 
В компании из n человек (n>3) каждый узнал по новости. Созвонившись, двое рассказывают друг другу все известные им новости. Как за 2n-4 звонка все смогут узнать все новости? iconНовости Сети
Если вы хотите, чтобы ваши новости были включены в Ленту новостей мпд, присылайте их на адрес
В компании из n человек (n>3) каждый узнал по новости. Созвонившись, двое рассказывают друг другу все известные им новости. Как за 2n-4 звонка все смогут узнать все новости? iconНовости Сети
Если вы хотите, чтобы ваши новости были включены в Ленту новостей мпд, присылайте их на адрес
В компании из n человек (n>3) каждый узнал по новости. Созвонившись, двое рассказывают друг другу все известные им новости. Как за 2n-4 звонка все смогут узнать все новости? iconНовости Сети
Если вы хотите, чтобы ваши новости были включены в Ленту новостей мпд, присылайте их на адрес

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2014
контакты
skachate.ru
Главная страница