У князя Гвидона было три сына. У некоторых потомков князя Гвидона было по три сына, остальные умерли бездетными. А всего у Гвидона оказалось 111 потомков. Сколько из них умерло бездетными?

Среди 111 потомков Гвидона всего 37 троек братьев. У каждой тройки братьев был родитель - либо сам Гвидон, либо кто-то из потомков. Это значит, что родителями были 36 потомков Гвидона, а тогда остальные 75 потомков умерли бездетными.

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

Оценка. Наименьшее количество асфальтированных дорог - 99. В самом деле, уберём все дороги, как асфальтированные, так и нет - тогда страна распадётся на 100 городов. Если мы будем проводить одну асфальтированную дорогу, то количество связных частей в стране либо не изменится, либо уменьшится на 1. Чтобы все города оказались связанными между собой, потребуется провести как минимум 99 асфальтированных дорог. Аналогично требуется провести 99 неасфальтированных дорог.

Пример. Занумеруем все города от 1 до 100. Соединим асфальтированными дорогами каждый город сл следующим по номеру (т.е. город k с городом k+1). Соединим неасфальтированными дорогами город k с городом k+2, а ещё город 1 с городом 4.

При решении этой задачи:
1) Надо обратить внимание, что если между любыми двумя городами есть ровно один путь, то это означает, что граф является деревом.

2) Проанализировать: если столица соединена с 50 городами, какое количество городов остается? Осталось 49 городов.  

У маленького Лёни есть 100 камей разного веса и маленькие двухчашечные весы, на каждую чашку которых можно положить только один камень (и весы укажут, который из них тяжелее). За какое наименьшее количество взвешиваний маленький Лёня сможет определить самый тяжёлый камень? Зачем маленькому Лёне понадобился самый тяжёлый камень, автор задачи не знает.

Пример. Взвесим любые два камня. Более лёгкий отбросим, более тяжёлый оставим. Будем продолжать эту процедуру, пока не останется один камень - он и будет самым тяжёлым. На это понадобится 99 взвешиваний, потому что каждым взвешиванием мы отбрасывали один камень

Оценка. Проведём ребро между двумя камнями, если мы их взвешивали. Если полученный граф оказался несвязным (т.е. не любые камни соединены путём из рёбер), то про камни из разных компонент связности у нас нет никакой информации, какой легче или тяжелее. А значит, граф из камней должен быть связным, а на это требуется хотя бы 99 рёбер.

ПРи решении этой задачи:
1) Можно провести аналогию с задачей 5 (про куб).: как мы рассуждали при ее решении.

2) Нужно актуализировать: сколько в квадрате 10х10 всего клеток; сколько частей получится, если разрезать квадрат на половинки клеток по диагоналям.

Сто человек обменялись рукопожатиями. Перед этим у пятерых из них на руках находился зловредный вирус СЩМШВ-23. Вирус передаётся только через рукопожатия. В итоге вирус оказался на руках у 90 человек. А какое наименьшее количество рукопожатий было сделано?

С каждым рукопожатием количество заражённых людей либо не увеличивается, либо увеличивается на одного. В конечном итоге количество заражённых людей увеличилось на 85. Значит, и наименьшее количество рукопожатий - 85.

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

Чтобы каркас куба не распался на части, требуется как минимум семь неперекушенных рёбер. В самом деле, в кубе 8 вершин. Если все рёбра будут перекушены, то каркас куба распадётся на 8 частей. Будем вновь соединять перекушенные рёбра, и тогда с каждым соединением количество частей уменьшится на 1. Чтобы куб не распался на части (т.е. куб состоял из одного куска), требуется 7 неперекушенных рёбер. Всего рёбер в кубе 12, а значит, маленький Саша сможет перекусить 5 рёбер.

Петя решил склеить пазл и повесить на стену. За одну минуту он склеивал вместе три куска — начальных, или ранее склеенных. В результате весь пазл склеился в одну цельную картину за час. А сколько минут понадобилось бы Пете, если бы он за минуту склеивал не три, а четыре куска в один?

За минуту количество кусков уменьшается на два, а значит, в изначальном пазле был 121 кусок. Если за минуту склеивать по четыре куска, то количество кусков будет уменьшаться на 3, а тогда, чтобы сделать из 121 куска один, понадобится 40 минут.

При решении этой задачи полезно:
1) проанализировать: как изменяется количество кусков при каждом склеивании;

2) ответить на вопрос: сколько кусков было в пазле первоначально.

Петя решил склеить пазл и повесить на стену. За одну минуту он склеивал вместе два куска — начальных, или ранее склеенных. В результате весь пазл склеился в одну цельную картину за два часа. А сколько деталей было в пазле?

В конце остался один кусок. За минуту количество кусков сокращалось на 1. А значит, за два часа количество кусков уменьшилось на 120. Следоватеьно, изначально был 121 кусок.

В стране 10 городов. Некоторые пары городов соединены дорогами (каждая дорога соединяет ровно два города). Оказалось, что между любыми двумя городами есть ровно один путь. А сколько дорог в стране?

Докажем сперва, что есть город, из которого выходит ровно одна дорога. Рассмотрим произвольный город А и наиболее удалённый от него город (по количеству дорог) Б. Допустим, что из города Б ведёт две дороги. Рассмотрим (единственный) путь из А в Б, и пусть есть дорога из Б в город В, которая не принадлежит пути из А в Б. По условию путь из А в В единственный, а значит, он проходит через Б. Но тогда В более удалён от А, нежели Б, и мы приходим к противоречию.
Итак, есть город, из которого выходит ровно одна дорога. Удалим этот город вместе с выходящей из него дорогой и получим 9 городов с тем же условием. Применив такую операцию 9 раз, мы придём к одному городу без дорог. А значит, всего в стране 9 дорог.

В графстве Шир есть столица и ещё 100 городов. Между некоторыми парами городов проложены дороги так, что между любыми двумя городами есть единственный путь. Из столицы выходит 50 дорог. Каково наименьшее количество городов, соединённых ровно с одним городом, может быть?

Оценка. Из задачи "Деревья-2" мы знаем, что в графстве Шир проложено 99 дорог, т.е. у всех городов 198 концов дорог в совокупности. Уберём мысленно по одному концу дороги из каждого города - останется 98 концов дорог. От одного города отходит ещё 49 концов дорог, остаётся ещё 50 концов дорог. Эти концы дорог мы можем придать максимум 50 городам (чтобы из каждого выходило две дороги). Остальные 49 городов будут иметь по одному концу дороги.

Пример легко строится. Назовём один город столицей. Пусть столица соединена с 50 городами, которые мы назовём городами первого уровня. Осталось ещё 49 городов (назовём их городами второго уровня); соединим каждый из них с одним (каждый со своим) городом первого уровня. Итого из одного города первого уровня и из 49 городов второго уровня выходит по одной дороге.

У маленького Лёни есть квадрат 10х10. Некоторые клетки маленький Лёня решил разрезать по диагонали. Маленький Лёня не хочет, чтобы квадрат с проведёнными разрезами распался на части. Какое наибольшее количество разрезов сможет сделать маленький Лёня?

Оценка. Рахрежем квадрат на половинки клеток. Неважно, как именно будут проведены диагонали клеточек - главное, что таких половинок клеточек окажется 200 штук. Если мы их начнём склеивать по стороне, то нам нужно будет как минимум 199 склеиваний (каждым склеиванием мы уменьшаем количество частей на 1). Посмотрим, сколько "склеек" (т.е. внутренних границ) между полуклеточками изначально есть в квадрате 10х10. Есть 10 горизонтальных рядов, в каждом из которых по 9 вертикальных границ - итого вертикальных границ 90. Аналогично горизонтальных границ тоже 90. И ещё есть 100 диагональных границ (каждая клеточка состоит из двух полуклеточек). Итого 280 границ. Чтобы осталось 199 границ, нужно разрезать 81 границу.

Пример. Выберем квадрат 9х9 (например, без нижней строчки и без левого столбца) и порежем каждую клетку по диагонали влево-вниз.

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

Оценка. Докажем, что каждая авиакомпания должна иметь не менее 9 авиалиний. Пусть сперва нет никаких авиалиний, тогда имеется 10 несоединённых между собой компонент (городов). Каждая авиалиния либо уменьшает количество компонент, соединяя две компоненты, либо не меняет их число. В конце все города должны образовывать одну компоненту, а значит, требуется всего не менее 9 авиалиний одной компании. Всего авиалиний в стране 45, то есть авиакомпаний не более 5.

Пример строится многими способами.

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

Назовём компонентой группу соединённых между собой точек. Изначально у нас пять компонент (каждая точка по отдельности). Каждый вновь проведённый отрезок либо лежит в одной компоненте, либо соединяет две компоненты, уменьшая на 1 количество компонент. Значит, необходимо 4 отрезка, чтобы осталась одна компонента.