Question

В локальной сети а) 2018, б) 2019 рабочих станций и один сервер. Сможет ли Вася соединить их проводами так, чтобы каждая рабочая станция была соединена ровно с четырьмя компьютерами, одним из которых будет сервер?
Это задача!
Компьютер это локальный сервер или сервер.

Answer 1

Соединим сперва все станции с сервером, получается, теперь нужно соединить станции так, чтобы каждая была соединена с тремя другими.

а) Расположим станции по кругу, соединим 1 с 1010, 2 с 1011 и так далее (проведём 1009 диаметров), теперь соединим каждую из станций с двумя соседними. Теперь каждая станция соединена с тремя другими.

б) 2019 * 3 = 6057 (сумма степеней всех вершин). 6057 - число нечётное. Тут хорошо бы вспомнить лемму о рукопожатиях (сумма степеней всех вершин графа равна удвоенной сумме рёбер). (С переходом в эту задачу, если на одном конце провода есть станция, она должна быть и на другом конце провода). Так что нельзя.

Ответ: а) Можно. б) Нельзя.