Задача
В олимпиадах
Олимпиада ICEF Evening School — 2019
Раздел
Баллы
15
Темы
Свойства
Сложность
Голосов еще нет
13.05.2019, 10:22 (Дарья Елицур)
13.05.2019, 10:22
13.05.2019, 10:22
(0)
1900 год. На рынке Нью-Йорка есть две фирмы, которые хотят начать строить метро: BRT и IRT. В Нью-Йорке есть только 6 густонаселенных района. Метростроители по очереди решают, какие два района соединить, за «свой ход» метростроитель может построить только один перегон. (Перегоны метро могут соединять между собой любые два района).
К тому же известно, что жители будут пользоваться только тем перегоном, который был построен раньше (если есть хотя бы два перегона, соединяющие два одних и тех же района). Таким образом, метростроителям не имеет смысла строить перегон между двумя районами, если между ними уже существует хотя бы один перегон.
Кольцевой веткой считается та, по которой можно проехаться от одной станции до другой и вернуться обратно, не проезжая по одному и тому же перегону два раза. Предпочтения жителей Нью-Йорка таковы, что та фирма, которая первой построила свою кольцевую ветку, выигрывает рынок всех районов полностью (люди в Нью-Йорке любят карусели). Но если такой фирмы нет – то фирмы делят рынок всего Нью-Йорка пополам.
К тому же известно, что жители будут пользоваться только тем перегоном, который был построен раньше (если есть хотя бы два перегона, соединяющие два одних и тех же района). Таким образом, метростроителям не имеет смысла строить перегон между двумя районами, если между ними уже существует хотя бы один перегон.
Кольцевой веткой считается та, по которой можно проехаться от одной станции до другой и вернуться обратно, не проезжая по одному и тому же перегону два раза. Предпочтения жителей Нью-Йорка таковы, что та фирма, которая первой построила свою кольцевую ветку, выигрывает рынок всех районов полностью (люди в Нью-Йорке любят карусели). Но если такой фирмы нет – то фирмы делят рынок всего Нью-Йорка пополам.
а) Докажите, что независимо от выбранных тактик и стратегий фирм, всегда будет фирма-победитель.
б) Возможно ли, чтобы ни одна из компаний не стала фирмой-победителем при каком-то другом числе районов в городе? Если Ваш ответ – «да», то докажите это, в противном случае приведите контрпример.
Все задачи этой олимпиады
11 класс
Задача | Баллы |
---|---|
Банки и заголовки | 10 |
Бертранвиль | 20 |
Дженга | 15 |
КилоМетровые пути | 10 |
Королевство гномов | 20 |
Ценные бумаги и фильмы | 10 |
Шоко-лиго-полис | 15 |
9-10 класс
Задача | Баллы |
---|---|
Банки и заголовки | 10 |
Белая ворона | 15 |
Бертранвиль | 20 |
Весенние каникулы | 15 |
Королевское болото | 10 |
Подземка в Нью-Йорке | 15 |
Чистый Флекс | 15 |