Выберите серию
В стране 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) ответить на вопрос: сколько кусков было в пазле первоначально.