Bariz - Problem

Source: St Petersburg Olympiad 2018, Grade 10, P1

Tags: combinatorics, graph theory

RagvaloD

22.06.2018 22:14

Misha came to country with $n$ cities, and every $2$ cities are connected by the road. Misha want visit some cities, but he doesn`t visit one city two time. Every time, when Misha goes from city $A$ to city $B$, president of country destroy $k$ roads from city $B$(president can`t destroy road, where Misha goes). What maximal number of cities Misha can visit, no matter how president does?

Let $K_n$ be a complete graph representing the cities.Since Misha cannot visit a city twice,we may assume that she destroys all the roads of the city when she leaves that.Assume that after visiting $t$ cities this is not possible for her to continue.then we should have: $$t-1+k \geq n-1 \implies t \geq n-k$$this is because all the roads of the previous $t-1$ cities are allready destroyed and president also destroyed $k$ cities.also,if president always destroys the roads to the cities Misha has not visited yet,the equality will hold,so the answer is $n-k$.