Задача 105098

Тема:    [ Процессы и операции ]

Сложность: 3- Классы: 6,7,8

Условие

Авторы: Шень А.Х., Доценко В.В.

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

Решение

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

Ответ

25 шагов.

Замечания

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

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

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