Подземка в Нью-Йорке

год. На рынке Нью-Йорка есть две фирмы, которые хотят начать строить метро: и . В Нью-Йорке есть только густонаселенных района. Метростроители по очереди решают, какие два района соединить, за "свой ход" метростроитель может построить только один перегон. (Перегоны метро могут соединять между собой любые два района).

К тому же известно, что жители будут пользоваться только тем перегоном, который был построен раньше (если есть хотя бы два перегона, соединяющие два одних и тех же района). Таким образом, метростроителям не имеет смысла строить перегон между двумя районами, если между ними уже существует хотя бы один перегон.

Кольцевой веткой считается та, по которой можно проехаться от одной станции до другой и вернуться обратно, не проезжая по одному и тому же перегону два раза. Предпочтения жителей Нью-Йорка таковы, что та фирма, которая первой построила свою кольцевую ветку, выигрывает рынок всех районов полностью (люди в Нью-Йорке любят карусели). Но если такой фирмы нет – то фирмы делят рынок всего Нью-Йорка пополам.

а) Докажите, что независимо от выбранных тактик и стратегий фирм, всегда будет фирма-победитель.

б) Возможно ли, чтобы ни одна из компаний не стала фирмой-победителем при каком-то другом числе районов в городе? Если Ваш ответ – "да", то докажите это, в противном случае приведите контрпример.