Лауреаты конкурса «Свободный полёт - 2013»

    О фонде  Конкурс Свободный полёт  Конкурс творческих идей  Собрание конкурсных работ  Физика  Математика  Это интересно 

Задача о потомках и ее обобщение

Рассмотрим известную задачу.

«У царя было 3 сына. Каждый из 10 его потомков имел 2 сына, а остальные умерли бездетными (дочерей не было). Сколько было бездетных потомков?»

Сначала попытайтесь решить эту задачу сами. Выясните при этом смысл замечания об отсутствии дочерей.

Решение можно формулировать парой фраз. «Все потомки кроме трех первых являются сыновьями потомков. Число сыновей потомков равно 10х2 = 20. Всего потомков 20+3 = 23. Число бездетных потомков равно 23 – 10 = 13».

Это решение основано на том, что у братьев нет общих потомков. При наличии дочерей такого основания не было бы.

При простом обобщении, когда 3 s 0, 10 n и 2 m 0, решение такое же: всего потомков (), число бездетных равно

( n • m + s - n )            (1)

Для дальнейших обобщений лучше подходит модификация задачи, связанная со структурой некой железной дороги (ж.д.).

Пусть в структуре ж.д. нет замкнутых циклов и все пути исходят из одной станции, которую будем называть начальной. К остальным станциям подходит один путь. Если из такой станции выходит хотя бы один путь, будем называть ее узловой, если ни один – конечной. Участок пути между двумя станциями будем называть перегоном. Дано: n - число узловых станций, Nk - число путей, исходящих из k-ой станции (k = 0,1,2,…, n ; нулевая – это начальная станция). Найти число конечных станций и число перегонов. ….

Можно предложить два способа решения этой задачи.

1. К каждой конечной станции от начальной ведет одна дорога. Каждая дорога ведет к одной конечной станции. Т.е. число возможных дорог равно числу конечных станций. Из начальной станции исходит N0 дорог, затем после k-ой узловой станции их число увеличивается на величину (Nk-1). Следовательно, число конечных станций

            (2)

Число перегонов равно числу всех станций кроме начальной:

            (3)

2. Все перегоны исходят из начальной или узловой станций. Это значит, что число перегонов равно сумме всех путей, выходящих из этих станций, т.е. равно правой части (3). Откуда приходим и к (2). Отметим, что этот метод полностью аналогичен приведенному выше методу решения задачи о потомках (только терминология другая).

Если N0 = s , N1=N2=…=Nn=m, то число бездетных (число конечных станций), получаемое из (2), равно величине (1).

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

Варианты обобщений: наличие замкнутых циклов, начальных станций больше чем одна и т.д. вплоть до анализа неких сложных разветвляющих структур («большие» молекулы и т.п.).