Выберите серию
Петя решил склеить пазл и повесить на стену. За одну минуту он склеивал вместе два куска — начальных, или ранее склеенных. В результате весь пазл склеился в одну цельную картину за два часа. А сколько деталей было в пазле?
Ответ:
Варианты ответов:
В конце остался один кусок. За минуту количество кусков сокращалось на 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.
Пример строится многими способами.