Олимпиадные задачи по математике - сложность 4 с решениями
а) Четыре порта 1, 2, 3, 4 расположены (в этом порядке) на окружности круглого острова. Их связывает плоская сеть дорог, на которых могут быть перекрёстки, то есть точки, где пересекаются, сходятся или разветвляются дороги. На всех участках дорог введено одностороннее движение так, что, выехав от любого порта или перекрёстка, нельзя вернуться в него снова. Пусть <i>f<sub>ij</sub></i> означает число различных путей, идущих из порта <i>i</i> в порт <i>j</i>. Докажите неравенство <i>f</i><sub>14</sub><i>f</i><sub>23</sub> ≥ <i>f</i><sub>13</sub><i>f</i><sub>24</sub>.
б) Докажите, что если портов шесть: 1, 2, 3, 4, 5, 6 (по кругу в этом поря...
В королевстве 16 городов. Король хочет построить такую систему дорог, чтобы из каждого города можно было попасть в каждый, минуя не более одного промежуточного города, и чтобы из каждого города выходило не более пяти дорог.
а) Докажите, что это возможно.
б) Докажите, что если в формулировке заменить число 5 на число 4, то желание короля станет неосуществимым.