Архив задач олимпиады по математике и криптографии
Города
Число городов в Криптоландии равно 44. В качестве названий города имеют различные цифровые комбинации вида (a,b,c,d), где a,b,c и d – целые числа из множества {0,1,2,3}. Два города, названия которых отличаются одной цифрой, называются соседними. Например, города (3201) и (3001) соседние, а (1111) и (3311) – нет. У каждого города есть флаг определенного цвета, причем флаги соседних городов всегда имеют несовпадающие цвета. Власти объявили конкурс на создание системы флагов для городов, имеющей наименьшее возможное число различных цветов. Найдите это наименьшее число. Ответ обоснуйте.
Заметим, что среди городов (0000), (1000), (2000) и (3000) любые два являются соседними. Значит, цветов надо минимум четыре. Покажем, что четырех цветов достаточно. Имеющиеся у нас цвета будем называть цвет-0, цвет-1,цвет-2, цвет-3. Флаг города будет окрашен в цвет, номер которого равен остатку от деления на 4 суммы цифр в названии этого города. (Например, для города (3201) этот остаток равен 2, значит его флаг будет окрашен в цвет-2.) У соседних городов эти остатки всегда различны, так как их названия отличаются одной цифрой. Следовательно, 4-х цветов достаточно.