Города и провинции Криптоландии
Когда число городов в Криптоландии достигло 44, власти решили провести терри-
ториальную реформу, создав 4 провинции по 34 городов в каждой. В качестве
названий городам планировалось присвоить различные обозначения (a1, …, a4) –
наборы из 4-х целых чисел, в которых ai принимают значения от 0 до 3. При этом
обозначения каждой пары городов из одной провинции должны были отличаться не
нее чем в двух позициях. Укажите какой-либо способ построения такой системы
названий.
- Решение
Решение
Если число городов mk, а число провинций m и в каждой по mk-1
городов, то отнесем к каждой провинции с номером i города с названиями
(a0, …, ak-1), удовлетворяющими условиям: сумма a0+ …+ ak-1 кратна i.
Очевидно, что каждый город будет отнесен к какой-либо провинции,и
любые два города в одной провинции будут отличаться не менее чем в 2-х
символах.