Номер 6, страница 45 - гдз по математике 5 класс учебник Дорофеев, Шарыгин

Вопросы. 2.5. Логика перебора при решении задач. Глава 2. Натуральные числа - номер 6, страница 45.

Какие ветви дерева окажутся лишними, если каждую цифру можно использовать только один раз?

Эта задача относится к комбинаторике и рассматривает так называемое "дерево вариантов" или "дерево решений". Такое дерево используется для наглядного представления всех возможных исходов последовательных событий. В данном случае, событиями являются выборы цифр для составления числа или последовательности.

Ключевое условие задачи — каждую цифру можно использовать только один раз. Это означает, что мы имеем дело с составлением последовательностей без повторений.

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

Пример для наглядности:

Допустим, нам нужно составить все возможные трехзначные числа из цифр {1, 2, 3}, не повторяя их. Построим соответствующее дерево вариантов и определим лишние ветви.

• Уровень 1: Выбор первой цифры (сотни).
  На этом шаге все варианты допустимы. У нас есть три основные ветви: 1, 2 и 3.
• Уровень 2: Выбор второй цифры (десятки).
  На этом уровне появляются первые лишние ветви.
  • Если первая цифра была 1, то на втором шаге мы можем выбрать 1, 2 или 3. Ветвь, ведущая к цифре 1, будет лишней, так как цифра 1 уже использована. Допустимыми остаются только ветви к 2 и 3.
  • Если первая цифра была 2, то лишней будет ветвь, ведущая к 2.
  • Если первая цифра была 3, то лишней будет ветвь, ведущая к 3.
• Уровень 3: Выбор третьей цифры (единицы).
  Здесь мы отталкиваемся от допустимых путей, полученных на втором уровне.
  • Рассмотрим путь "1 → 2". На третьем шаге мы должны выбрать третью цифру. Лишними будут ветви, ведущие к цифрам 1 и 2, так как они уже использованы в этой последовательности. Единственной допустимой ветвью будет та, что ведет к цифре 3. Таким образом, мы получаем корректное число 123.
  • Для пути "1 → 3" лишними будут ветви к 1 и 3. Допустимой будет ветвь к 2, образуя число 132.
  • Аналогичные рассуждения применяются ко всем остальным путям, начинающимся с 2 и 3.

Таким образом, лишними оказываются все те ветви, которые приводят к повторению цифры в создаваемой последовательности. Если обозначить последовательность цифр как $d_1, d_2, d_3, \dots, d_k$, то ветвь, соответствующая выбору цифры $d_k$ на $k$-м шаге, является лишней, если $d_k = d_i$ для любого $i < k$.

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