Уроки 56–57. Дерево всех слов данной длины

Материалы к урокам: лист определений «Дерево всех слов данной длины», бумажные задачи 63–72 (2 часть), компьютерный урок «Дерево всех слов данной длины» (задачи 528–532).

На первом уроке ребята изучают новый лист определений, решают 3–4 обязательные задачи. На втором уроке ребята решают компьютерные задачи уроков и дорешивают все оставшиеся задачи из бумажного учебника.

Дерево всех слов данной длины

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

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

Напомните детям, что для того, чтобы не запутаться, мы строим деревья букв, придерживаясь лексикографического порядка: каждый раз, выписывая следующие буквы после каждой буквы, мы располагаем буквы в алфавитном порядке сверху вниз. Так же построено и дерево Q на листе определений.

Попросите детей, рассматривая этот лист определений, найти в мешке слова, которые они считают словами русского языка. Очевидно, что словами русского языка являются РОК, СОК, СОР, а если брать не словарные формы, то и РОС, КОС. Однако ОКР (опытно-конструкторские работы) и особенно ОРС (отдел рабочего снабжения, были орсовские магазины), также слова русского языка.

Справка об экзотических словах русского языка

КОР устар. оскорбление, брань. Отсюда: укор, наперекор, корить и пр.
КОС диал. скворец.
ОРК злобное мифологическое существо в германо-скандинавской мифологии.
ОСК представитель осков, италийского племени, обитавшего в Кампании.
СКО «филум» [семья] из восьми папуасских языков.

Решение бумажных задач

Задача 63. Данная задача похожа на задачу с листа определений. Различаются эти задачи числом букв в мешке. В результате на соответствующих уровнях в деревьях (дереве G и дереве Q с листа определений) располагается разное число бусин. Так, в дереве G корневых бусин будет три (поскольку на первом месте каждого из слов может быть одна из трех букв мешка R). За каждой из корневых бусин будут следовать две (столько останется, если одну бусину из мешка уже взяли), а за каждой бусиной второго уровня – одна. Несмотря на это различие, надеемся, что ребята справятся с построением дерева самостоятельно.

Некоторым ребятам будет сложно изобразить дерево на листе так же красиво, как в учебнике, и здесь, возможно, потребуется ваша помощь. Чтобы, с одной стороны, не подсказывать ребятам решение, а с другой обеспечить правильное размещение дерева в окне, посоветуйте учащимся сначала нарисовать дерево на черновике. Напомните им, что желательно строить дерево в лексикографическом порядке. Теперь уже можно обсуждать, как рационально использовать место в окне.
После того как дерево построено, аккуратно выписываем в мешок К все пути.


Необходимость отвечать на вопросы побуждает ребят проверить свое решение. Отвечая на вопрос: «Все ли пути дерева G есть в мешке К?», нужно иметь в виду, что совпадение числа листьев дерева G и числа слов в мешке К есть необходимое, но недостаточное условие правильности ответа. Если эти числа не совпадают, можно точно утверждать, что ученик допустил ошибку. Однако, если числа совпадают, это еще не значит, что все пути дерева есть в мешке. Например, ученик мог по невнимательности дважды выписать один и тот же путь, а какой-то другой пропустить. Для утвердительного ответа на вопрос необходимо не только сосчитать количество слов и путей, но и внимательно снова просмотреть пути дерева, ставя пометки около слова, соответствующего каждому пути.

Задача 64. Здесь впервые от ребят требуется построить дерево вычислений целиком и придумать, как будут обозначаться арифметические действия. При этом может возникнуть следующая техническая трудность: если ребята обычно пользуются фломастерами, то их цвета (особенно синий и зеленый) могут оказаться настолько яркими и насыщенными, что чисел в бусинах будет не видно (именно поэтому в наших деревьях бусины раскрашены бледными тонами). Как мы говорили раньше, цветовой способ различения в дереве арифметических действий, предложенный на листе определений, – вопрос договоренности. Выбор такого способа непринципиален и может быть любым другим, лишь бы в дереве было отражено, какое именно действие происходит с числами, чтобы получился некий результат. Поэтому мы предлагаем детям самим показывать в каждой подобной задаче, как они будут обозначать в дереве арифметические действия. Предлагаем вам несколько способов (возможно, вы или дети изобретете другие). Первый – использовать те же цвета, что и на листе определений «Дерево вычислений» (голубой, светло-зеленый, розовый, желтый). Тогда для этого урока придется попросить детей принести карандаши или фломастеры соответствующих цветов. Второй способ – не раскрашивать соответствующую бусину, а просто обводить любым цветом по границе бусины. В этом случае можно использовать стандартные цвета, которые дети обычно использовали при решении задач (красный, синий, желтый, зеленый). Третий способ – использовать штриховку (простым карандашом) четырех разных типов, например вертикальную, горизонтальную, диагональную, клетку. Главное, чтобы при любом способе дети не забыли отразить введенные обозначения в свободных клетках образца.

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

Но сначала дерево нужно построить.

Прежде чем начать рисовать дерево, надо внимательно изучить арифметическое выражение и пронумеровать порядок действий:


Теперь есть два варианта: можно начинать строить дерево «снизу вверх», от корня к листьям, или, наоборот, от листьев к корню. В любом случае надо рисовать дерево сначала на черновике.

1. От корня к листьям. При таком построении порядок действий нужно изучать с конца, начиная с самого последнего.

Уровень 1. В нашем случае последнее, 4-е действие – сложение. Значит, корневая бусина должна быть помечена как результат сложения.

Уровень 2. Какие числа мы складываем в 4-м действии? Складываем два числа: одно – результат деления (2-е действие), другое – тоже результат деления (3-е действие). Поэтому на втором уровне должны находиться две бусины, помеченные как результат деления. На рисунке мы пока для простоты поставим в бусинах знаки деления и умножения, ведь мы работаем на черновике. При перерисовывании набело в учебник нужно будет эти бусины пометить, как договорились, а в самих бусинах написать результат действий. Вот что у нас получилось.


Уровень 3. Одна бусина второго уровня (вообще говоря, любая из двух, но правильнее – левая) у нас соответствует 2-му действию, в котором мы делим результат сложения (1−е действие) на 3. Поэтому следующие после этой бусины второго уровня будут «результат суммы» и 3. Вторая (правая) бусина второго уровня соответствует результату деления 72 и 8, поэтому следующие за ней бусины будут 72 и 8. Данные в примере числа всегда листья в дереве вычислений, поэтому можно сразу выпустить из них стрелки.


Уровень 4. Остались незадействованными только слагаемые 24 и 6, они расположены на четвертом уровне и следуют после бусины-суммы третьего уровня. Построение дерева завершено.


2. От листьев к корню. Выпишем все числа данного в задаче арифметического выражения по порядку.


Это будут листья дерева. Конечно, наверняка все листья не будут расположены на одном уровне. Но мы же работаем на черновике и поэтому имеем некоторую степень свободы (лучше потом перерисуем).

Теперь будем выполнять действия арифметического выражения по порядку, начиная с первого, – достраивать соответствующие этим действиям бусины дерева. Выполняем первое действие – рисуем бусину-результат этого действия.


Выполняем 2-е действие. То, что получилось сейчас, конечно, является неправильно нарисованным деревом – бусины расположены не на своих уровнях. Но исправим это потом. Сейчас для нас главное – общая структура дерева.


Выполняем 3-е действие.


Выполняем последнее, пятое действие, рисуем корневую бусину.


Теперь надо аккуратно снова нарисовать это дерево (лучше начиная снизу, с корневой бусины) так, чтобы все бусины были расположены на своих уровнях. При этом правильно, если «горизонтальный» порядок листьев сохранится.

Осталось перерисовать дерево в учебник. При этом нужно не забыть соблюсти обозначения арифметических действий и заполнить дерево – вычислить значение выражения. Наконец, вычисляем значение выражения в примере, а затем сравниваем результаты (в обоих случаях должно получиться 19).

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

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

Задача 65. Эта задача требует переноса знаний о деревьях всех слов данной длины из данного мешка на новые объекты – геометрические бусины. В остальном задача 65 аналогична задаче 63. Неудивительно, если кто-то из ребят сам не увидит аналогии, ведь в этом возрасте дети скорее выделяют внешние признаки, чем внутреннюю структуру. Некоторых придется подтолкнуть: отвлеките такого ребенка от внешнего – букв и бусин, сосредоточьте его внимание на самом процессе вынимания объектов из мешка и составления цепочки. Когда обсудите процесс, спросите, не встречался ли уже где-нибудь такой же процесс, и вернитесь к задаче 63. После того как связь установлена, ребенок решит задачу самостоятельно и быстро.
Ответ:


Задача 66. Необязательная. Как и во многих математических задачах нашего курса, главное здесь – построить математическую модель жизненной ситуации или выделить в реальном процессе определенную связь между величинами. Ситуация в этой задаче не слишком сложная. Пять (первых) выстрелов Гриша сделал в любом случае. Каждое попадание добавляет к любому числу выстрелов еще 2 выстрела, значит, 12 «лишних» выстрелов получились от 6 попаданий. При этом совершенно неважно, на каком шаге происходили эти попадания, в частности, сколько из этих призовых выстрелов было в числе первых 5 выстрелов, а сколько в числе последующих. Однако эта простая идея может и не прийти в голову ребятам. В таком случае предложите им воспользоваться методом проб и ошибок – рассмотреть конкретные случаи. Пусть Гриша из 5 выстрелов попал 3 раза и больше не попал в цель. Сколько всего выстрелов он сделал? Получаем 11. Это мало, поэтому будем добавлять призовые выстрелы до тех пор, пока не получится 17 выстрелов.

К решению этой задачи можно подойти, используя дерево. Рисуем 5 корневых бусин, а дальше выбираем (произвольно) призовые бусины-выстрелы и пристраиваем к ним по две следующие бусины (на любом уровне) до тех пор, пока бусин в дереве не станет 17. Теперь считаем, сколько в дереве не листьев (можно их пометить цветом), это число и дает нам число попаданий (6). Заметьте, что вид дерева может у разных детей быть различным, в том числе и по числу уровней. Уровней в дереве может быть от трех и до семи. На рисунке мы приводим лишь два из возможных деревьев – одно 3-уровневое и одно 7-уровневое. Естественно у всех таких деревьев число бусин, листьев и не листьев будет одинаковым (соответственно 17, 11 и 6).


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

Задача 67. Эта задача точно такая же, как задача 65, и очень хорошо, если кто-то из детей это поймет и сможет объяснить, что он имеет в виду: ведь в той задаче речь идет о цветных бусинах и цепочках, а здесь – о цифрах и числах. Такая аналогия может быть полезна и детям, которые запутались или что-то пропустили.

В отличие от предыдущих подобных задач эта задача сформулирована немного по-другому, при помощи истинности выделенного утверждения. Это сделано для того, чтобы перекинуть мостик к последующим, более сложным подобным задачам, в формулировке которых тоже будут использованы утверждения.
Ответ:


Задача 68. Необязательная. Условие этой задачи сформулировано достаточно сложно. Ответом должна быть цепочка цепочек Л длины 5. Длина каждой ее бусины-цепочки должна быть больше 5 (т. е. или 6, или больше), две бусины-цепочки должны быть одинаковые. При склеивании цепочки цепочек Л должна получиться цепочка ⊕Л.

Некоторые ученики при решении задач быстро сами «натыкаются» на верное решение и чаще всего не могут объяснить, как его нашли. Оказывается, что ребята что-то заметили, догадались, и поиск решения в этом случае носит характер внезапного озарения. Конечно, скорее всего, это не случайность, а следствие раннего развития определенной математической (логической, геометрической) интуиции у таких учеников. Таким детям, может быть, не понадобится ваша помощь. Тем же учащимся, кто запутался и не видит даже подходов к решению, вы не сможете предложить «наткнуться», «догадаться» или «заметить» подобное решение. Если вы укажете, что именно нужно «заметить», то решите задачу за ученика, а если нет – все равно не выведете его к решению. Поэтому у учителя в распоряжении должен быть другой способ – не тот, который предполагает внезапное озарение, а тот, до которого можно дойти путем логических рассуждений. Именно поэтому в данной книге мы иногда даем два решения. Первое начинается словами «скорее всего, ваши ученики будут делать так»; оно часто оказывается случайным, интуитивным и труднообъяснимым. Второе решение – путь логических рассуждений, которые можно провести с любым учеником, а также использовать, чтобы сдвинуть ребенка с мертвой точки. Подобной особенностью отличаются и комментарии к данной задаче.

Вернемся к решению нашей задачи 68. Возможно, кто-то из детей сразу заметит (это бросается в глаза, если внимательно рассмотреть цепочку ⊕Л), что первая и вторая строчки заканчиваются одинаково – шестью бусинами от красной круглой до желтой треугольной. Таким образом, ребята сразу же найдут две одинаковые цепочки-бусины, длина которых больше пяти. Остается лишь проверить, что длина первой, третьей и пятой бусин также будет больше пяти. В данном случае условие выполняется, и мы получаем следующий ответ:


Ребят, которые нашли ответ таким образом (очень быстро), можно попросить найти еще одно решение.

Какие же рассуждения могут помочь вам при работе с учеником, который не знает, с чего начать? Нам нужно разбить цепочку ⊕Л на пять частей, две из которых должны быть одинаковыми. Первый вопрос: какие именно части будут одинаковыми и может ли одна из них быть началом цепочки? Видим, что не может из-за желтых квадратных бусин, которых в ⊕Л всего две, потому что если бы такое было возможно, то в первой части желтый квадрат был бы третьим по счету. Тогда во второй части желтый квадрат должен быть также третьим по счету. В таком случае первая цепочка будет иметь длину 4, что противоречит условию. Отсюда можно сделать два вывода: во-первых, ни одна из одинаковых частей не первая; во-вторых, оба желтых квадрата цепочки ⊕Л лучше включить в первую часть, чтобы они не мешали. Тогда вторая часть может начинаться с первого по счету желтого треугольника. Посмотрим, может ли одна из одинаковых частей быть второй. Ищем следующий по счету желтый треугольник и проверяем, совпадают ли пять следующих за ним бусин с теми, что следуют за первым желтым треугольником (красная круглая, синяя треугольная и т. д.). Оказывается, что совпадают. Итак, мы выяснили, что одинаковыми могут быть вторая и третья бусины. Длина каждой из них – шесть бусин, а длина первой части – восемь бусин. Теперь осталось разделить все оставшиеся бусины на две цепочки так, чтобы длина каждой была больше пяти бусин. Можно, например, разделить их поровну. Получаем еще одно решение:


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

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

Задача 69. Дерево, которое ребята рисуют в этой задаче, очень похоже на дерево из задачи 57, только здесь требуется построить дерево в три уровня, а бусины дерева не 0 и 1, а черные и белые бусины.
Ответ:


Задача 70. Необязательная. В таких задачах ваша помощь должна быть минимальной, ведь задачи необязательные и поэтому обычно предлагаются тем ребятам, которые имеют интерес и способности к ним. Если вы все же хотите натолкнуть учащегося на мысль, предложите ему рассмотреть один любой случай, например, что Змея убил Илья Муромец, и определить истинность высказываний всех богатырей. Получаем, что высказывание Ильи Муромца ложно, Добрыни ложно, Алеши ложно. Такой вариант нам не подходит, поскольку в условии сказано, что один богатырь сказал правду, а остальные слукавили. Теперь пусть учащийся самостоятельно разберет оставшиеся два случая и выяснит, кто убил Змея.
Ответ: Змея убил Добрыня Никитич.

Задача 71. Основная часть этого задания – построение мешка W трехзначных чисел, для каждого из которых истинно заданное утверждение. Для правильного выполнения этого задания необходимо, во-первых, понимание того, какие числа должны быть в мешке W (т. е. уяснение смысла утверждения). Во-вторых, нужен определенный принцип перебора таких чисел, чтобы ни одного не пропустить. Уяснению смысла утверждения способствует выполнение первой части задания – работа с числами из мешка Z. В мешке Z подходящих чисел оказывается три: 222, 111, 121. Очень полезно в этой задаче переформулировать утверждение без отрицания (без слова «нет»). На самом деле данное утверждение означает, что числа должны состоять только из цифр 1 и 2 (при этом цифры могут повторяться).

Чтобы не запутаться при переборе всех таких чисел, мы предлагаем детям в задаче построить дерево U, мешок всех путей которого и будет решением. На первом уровне в дереве U будут две бусины – 1 и 2 (возможные первые цифры). За каждой из них будут следовать также две бусины – 1 и 2 (возможные вторые цифры). Наконец, за каждой бусиной второго уровня также будут следовать две те же самые бусины. После построения дерева остается выписать все пути в мешок, и мы получим искомый мешок W.

Как легко убедиться, построенное дерево U очень похоже на дерево N из задачи 69 (математики говорят, что эти деревья гомоморфны), только надо заменить черные и белые бусины на 1 и 2 соответственно. Так же похожи и полученные мешки всех путей этих деревьев.

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


Решение компьютерных задач

Задача 528. Задача аналогичная бумажной задаче 65 (см. комментарий к задаче 65), но электронные возможности позволяют выполнить задание легче и быстрее.

Задача 529. Это сюжетная комбинаторная задача, которые обычно предлагаются детям в курсе математики. Если кто-то из детей растерялся и знает с чего начать, попытайтесь аккуратно показать ребенку, что задача аналогична предыдущей. Действительно, как показано на картинке, стулья стоят в ряд. При этом гнома всего три и естественно каждый из них посаженный на один стул не может быть посажен еще и на другой. Значит речь идет о построении всех возможных цепочек из гномов выбираемых из трех без возвращений, то есть по сути из трех бусин, вынутых из мешка. Сильным и средним детям лучше по возможности вообще не помогать. Пусть начинают решать задачу методом проб и ошибок, рано или поздно они увидят аналогию. При построении дерева первый уровень будет соответствовать первому по счету стулу, второй – второму, третий – третьему. Таким образом каждый путь дерева будет представлять собой один способ посадки гномов.

Задача 530. Здесь, скорее всего, помогать ребятам не придется. Из условия понятно, что на первом уровне должны стоять 3 бусины из мешка А. После каждой из них будут следовать 2 бусины из мешка Б, ведь для каждой первой второй бусиной может быть любая из них. После каждой бусины второго уровня будет следовать бусина мешка В. Поскольку она одна, других вариантов просто нет.

Задача 531. В этой задаче снова нам поможет дерево. При этом каждый уровень дерева будет соответствовать разряду искомых чисел: первый уровень – разряду десятков, второй уровень – разряду единиц. В разряде десятков может стоять любая из трех данных цифр, поэтому на первом уровне дерева будет 3 числа. В разряде единиц может стоять тоже любая из данных цифр, поэтому у каждой бусины первого уровня будет 3 следующих (1, 2 и 3). В результате получаем, что всего искомых чисел 9.

Задача 532. Тем кто запутался и не знает, с чего начать предложите действовать методом проб и ошибок, компьютерные возможности позволяют сделать множество разных проб или построении дерева. Сильным и средним детям можно сразу задать вопрос, на какую из компьютерных задач этого урока данная задача похожа больше всего. Конечно на задачу 531 (хотя по сюжету они и отличаются). Действительно, если в предыдущей задаче число взять не двузначное, а трехзначное, а цифр наоборот взять не три, а две, то задача станет по содержанию полностью аналогична данной. Поэтому и дерево строится совершенно аналогичным образом (см. комментарий к задаче 531).