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

Решение:

В таблице представлены дороги между населёнными пунктами, обозначенными цифрами от 1 до 7. На схеме населённые пункты обозначены буквами A, B, C, D, E, F, G. Нам нужно определить, какие номера из таблицы могут соответствовать пунктам B и C.

Рассмотрим пункт B на схеме. Он соединён дорогами с пунктами A, C, D. В таблице пункт B должен иметь связи с тремя другими пунктами. Посмотрим на строки таблицы, где есть три звездочки:

• Строка 2: связи с 1, 4, 7.
• Строка 4: связи с 1, 3, 7.

Рассмотрим пункт C на схеме. Он соединён дорогами с пунктами B, D, E. В таблице пункт C также должен иметь связи с тремя другими пунктами.

Теперь сопоставим пункты B и C с номерами в таблице, учитывая их связи.

Если B соответствует номеру 2, то его соседи в таблице — 1, 4, 7. Если C соответствует номеру 4, то его соседи в таблице — 1, 3, 7. Пункты B и C на схеме соединены. В таблице номера 2 и 4 имеют общего соседа — пункт 1.

Проверим другие варианты.

Пункты B и C являются соседями. В таблице, если B=2, C=4, то между ними нет прямой дороги, но они оба имеют дороги к пункту 1. Если B=4, C=2, то результат тот же.

Рассмотрим связи пунктов B и C на схеме: B связан с A, C, D. C связан с B, D, E. Оба связаны с D.

Если B - это 2, то его соседи 1, 4, 7. Если C - это 4, то его соседи 1, 3, 7. Общий сосед 1. B и C на схеме соединены. В таблице 2 и 4 не соединены. Значит, B и C не могут быть 2 и 4.

Посмотрим на пункты, имеющие 3 связи:

• Пункт 2: связан с 1, 4, 7.
• Пункт 4: связан с 1, 3, 7.
• Пункт 7: связан с 1, 2, 4.

Если B = 2, C = 7:

• B (2) связан с 1, 4, 7.
• C (7) связан с 1, 2, 4.

В этом случае B и C соединены (2 и 7 связаны). B связан с 1, 4, 7. C связан с 1, 2, 4. На схеме B связан с A, C, D. C связан с B, D, E.

Если B = 4, C = 7:

• B (4) связан с 1, 3, 7.
• C (7) связан с 1, 2, 4.

В этом случае B и C соединены (4 и 7 связаны). B связан с 1, 3, 7. C связан с 1, 2, 4. На схеме B связан с A, C, D. C связан с B, D, E.

Из связей следует, что B и C должны иметь по 3 связи. В таблице такие номера: 2, 4, 7. (На самом деле, номер 7 имеет 3 связи: 1, 2, 4).

Итак, пункты B и C имеют по 3 связи. Возможные номера для них — 2, 4, 7. Из схемы видно, что B и C соединены напрямую. Проверим, какие пары из (2, 4, 7) соединены в таблице:

• 2 и 4: не соединены
• 2 и 7: соединены
• 4 и 7: соединены

Значит, пара (B, C) может быть (2, 7) или (4, 7).

Рассмотрим, что B и C соединены напрямую. Значит, они должны иметь дорогу друг с другом.

Рассмотрим пункт D на схеме. Он соединен с B, C, E. Значит, пункт D имеет 3 связи.

Пункты с 3 связями в таблице: 2 (1,4,7), 4 (1,3,7), 7 (1,2,4).

Если B=2, C=7. D может быть 4. Связи B(2): 1,4,7. Связи C(7): 1,2,4. Связи D(4): 1,3,7. B и C соединены (2-7). B и D соединены (2-4). C и D соединены (7-4). Это подходит.

Если B=4, C=7. D может быть 2. Связи B(4): 1,3,7. Связи C(7): 1,2,4. Связи D(2): 1,4,7. B и C соединены (4-7). B и D не соединены (4-2). Это не подходит.

Следовательно, B=2 и C=7 (или наоборот).

В возрастающем порядке это 2 и 7.

Ответ: 27