ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 105098
Тема:    [ Процессы и операции ]
Сложность: 3-
Классы: 6,7,8
В корзину
Прислать комментарий

Условие

Даны шесть слов:
   ЗАНОЗА
   ЗИПУНЫ
   КАЗИНО
   КЕФАЛЬ
   ОТМЕЛЬ
   ШЕЛЕСТ
За один шаг можно заменить любую букву в любом из этих слов на любую другую (например, за один шаг можно получить из слова ЗАНОЗА слово ЗКНОЗА. Какое наименьшее число шагов нужно, чтобы сделать все слова одинаковыми (допускаются бессмысленные)?


Решение

После всех замен буквы в каждой колонке должны стать одинаковыми. Число замен будет наименьшим, если в каждой колонке сохранить наиболее частую букву (любую из них, если таких букв несколько). Например, в первой колонке можно оставить буквы З или К, они обе требуют четырёх замен. Минимальное число замен равно  4 + 4 + 5 + 4 + 4 + 4 = 25.


Ответ

25 шагов.

Замечания

Среди слов, которые могут получиться в результате, есть осмысленные, например, ЗЕЛЕНЬ, КАПЕЛЬ или КАФЕЛЬ.

Источники и прецеденты использования

олимпиада
Название Московская математическая олимпиада
год
Номер 64
Год 2001
вариант
Класс 8
задача
Номер 3

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .