3. В игровом мире 7 башен с номерами 2, 3, 5, 7, 11, 13, 17 (все числа - простые). Магические мосты соединяют башни, только если сумма их номеров также является простым числом. Постройте граф мостов и найдите, какие башни не соединены ни с одной другой.

Решение:

Номера башен: {2, 3, 5, 7, 11, 13, 17}. Мост соединяет две башни, если сумма их номеров — простое число.

Проверим все возможные пары башен и сумму их номеров:

• 2 + 3 = 5 (простое) — соединяем
• 2 + 5 = 7 (простое) — соединяем
• 2 + 7 = 9 (не простое)
• 2 + 11 = 13 (простое) — соединяем
• 2 + 13 = 15 (не простое)
• 2 + 17 = 19 (простое) — соединяем
• 3 + 5 = 8 (не простое)
• 3 + 7 = 10 (не простое)
• 3 + 11 = 14 (не простое)
• 3 + 13 = 16 (не простое)
• 3 + 17 = 20 (не простое)
• 5 + 7 = 12 (не простое)
• 5 + 11 = 16 (не простое)
• 5 + 13 = 18 (не простое)
• 5 + 17 = 22 (не простое)
• 7 + 11 = 18 (не простое)
• 7 + 13 = 20 (не простое)
• 7 + 17 = 24 (не простое)
• 11 + 13 = 24 (не простое)
• 11 + 17 = 28 (не простое)
• 13 + 17 = 30 (не простое)

Особый случай: Сумма с числом 2. Если одна из башен имеет номер 2, то сумма с другой башней может быть простым числом, только если другая башня имеет четный номер (что возможно только для 2) или если сумма является простым числом. Так как все остальные башни имеют нечетные номера, то сумма 2 + нечетное число будет нечетным числом. Если это нечетное число простое, то башни соединяются.

Проверим пары с 2:

• 2 + 3 = 5 (простое)
• 2 + 5 = 7 (простое)
• 2 + 11 = 13 (простое)
• 2 + 17 = 19 (простое)

Проверим пары без 2:

• 3 + 2 = 5 (уже учтено)
• 5 + 2 = 7 (уже учтено)
• 7 + 2 = 9 (не простое)
• 11 + 2 = 13 (уже учтено)
• 13 + 2 = 15 (не простое)
• 17 + 2 = 19 (уже учтено)

Итак, мосты соединяют следующие пары башен:

• (2, 3)
• (2, 5)
• (2, 11)
• (2, 17)

Все башни, кроме башни с номером 2, являются нечетными простыми числами. Сумма двух нечетных простых чисел всегда является четным числом, большим 2. Единственное четное простое число — это 2. Следовательно, сумма любых двух башен, кроме тех, где участвует башня №2, не будет простым числом.

Граф мостов:

Башня 2 соединена с башнями 3, 5, 11, 17.

Башни 3, 5, 11, 17 не соединены между собой, а также не соединены с башней 7.

Башни, которые не соединены ни с одной другой:

Башня с номером 7 не соединена ни с одной другой башней, так как:

• 7 + 2 = 9 (не простое)
• 7 + 3 = 10 (не простое)
• 7 + 5 = 12 (не простое)
• 7 + 11 = 18 (не простое)
• 7 + 13 = 20 (не простое)
• 7 + 17 = 24 (не простое)

Ответ: Башня с номером 7 не соединена ни с одной другой.