Поиск минимального числа обменов при сборе коллекции — практикум с ответами для 5 класса

Практикум по коллекциям, 5 класс. Главная цель — находить наименьшее число обменов, а не просто перебирать способы. В коллекции нужны по одному предмету каждого вида. Повторы — запас для обмена.

Модель одного обмена

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

Краткое правило: посчитай виды, которых в коллекции ещё нет. Если недостающих видов m, нужно как минимум m обменов: один обмен может добавить не больше одного нового вида. Столько обменов и достаточно — каждый повтор заменяется одним недостающим видом. Значит минимум = число недостающих видов.

Найди ошибки в шести решениях

Буквы A, B, C… обозначают разные виды марок. В каждом пункте назови ошибку, минимальное количество обменов и возможную последовательность действий.

1. Неверно: нужны виды A, B, C, D; имеются A, A, B, B. «Один обмен соберёт коллекцию целиком».
2. Неверно: нужны A, B, C, D, E; имеются A, A, B, B, C. «Три повтора, значит три обмена».
3. Неверно: нужны A, B, C, D; имеются A, B, C, D. «Для надёжности надо обменять одну марку».
4. Неверно: нужны A, B, C, D, E, F; имеются A, A, A, B, B, C. «Два обмена хватит, ведь повторяются лишь A и B».
5. Неверно: нужны A, B, C, D; имеются A, A, A, B. «Три обмена, потому что буква A встречается три раза».
6. Неверно: нужны A, B, C, D, E; имеются A, A, C, C, E. «Обменяем одну лишнюю A, и готово».

Исправленные решения и объяснения

1. Нет C и D — это 2 обмена, не один. Например, A→C и B→D. После первого обмена остаётся ещё один отсутствующий вид.
2. Отсутствуют D и E — 2 обмена. В коллекции две лишние марки: вторая A и вторая B. Действия: A→D, B→E. Считать нужно лишние экземпляры, а не общее число экземпляров повторяющихся букв.
3. Все четыре вида уже есть. 0 обменов. Любая лишняя операция не улучшает готовую коллекцию.
4. Имеются лишь три разных вида: A, B, C. Нужны D, E, F — 3 обмена. Можно отдать две лишние A и одну B, получив D, E, F. Двух обменов недостаточно, потому что они принесут максимум два новых вида.
5. Не хватает C и D — 2 обмена. Две из трёх A являются лишними: A→C и A→D. Первая A должна остаться в коллекции.
6. Не хватает B и D — 2 обмена. Заменяем вторую A на B и вторую C на D. После одного обмена один вид всё ещё отсутствует.

Девять самостоятельных задач

Для каждого номера запиши: число разных имеющихся видов; список недостающих видов; наименьшее число обменов. Подчеркни конкретные повторы, которыми можно пожертвовать.

7. Нужны A–F; есть A, A, B, C, D, D.
8. Нужны A–D; есть A, B, C, C.
9. Нужны A–G; есть A, A, B, B, C, C, D.
10. Нужны A–D; есть A, B, C, D.
11. Нужны A–F; есть A, A, A, B, C, D.
12. Нужны A–E; есть A, B, B, D, D.
13. Нужны A–H; есть A, B, C, D, E, F, G, G.
14. Нужны A–E; есть A, A, B, B, B.
15. Нужны A–G; есть A, B, B, C, D, E, E.

Ответы к самостоятельным задачам

Проверка минимальности

В задаче № 14 есть пять предметов, но только два разных вида. Три нужных вида отсутствуют; меньше трёх обменов не хватит по самому определению обмена. Три лишних экземпляра есть, и по условию их можно обменять на C, D, E. Значит трёх достаточно и меньше невозможно. Такой двусторонний аргумент — нижняя граница плюс пример её достижения — доказывает минимальность, а не просто предлагает решение.

Почему само слово «минимум» требует доказательства

Любой обмен заменяет лишь одну марку. Следовательно, после одного обмена число представленных в коллекции разных видов может увеличиться максимум на один. Если не хватает трёх видов, никакая хитрая последовательность из двух обменов не сделает коллекцию полной: третий вид взять просто неоткуда. Это доказательство нижней границы.

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

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