Question

СРОЧНО!!! Помогите, пожалуйста. Задача на логику. Докажите, что если взять географическую карту и выбрать на ней любые 6 городов, то окажется верным по крайней мере одно утверждение из двух: среди этих шести городов найдутся три города, попарно связанные прямыми дорогами, или найдутся три города, между которыми нет связывающих их прямых дорог. (прямая дорога между двумя городами - это дорога, выходящая из одного города и заканчивающаяся в другом, не проходящая через третий город. )

Answer 1

Ответ:

9 дорог

Построй графы

Объяснение:

Answer 2

Для доказательства данного утверждения, давайте рассмотрим два случая:

Случай 1: Среди выбранных 6 городов есть три, попарно связанные прямыми дорогами. В этом случае, у нас уже есть три города, между которыми есть прямые дороги, и утверждение выполняется.

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

Итак, вне зависимости от выбора 6 городов на географической карте, одно из двух утверждений всегда будет верным: либо найдутся три города, попарно связанные прямыми дорогами, либо найдутся три города, между которыми нет связывающих их прямых дорог.