Školjka

U državi postoji $g$ gradova i $c$ cesta, pri čemu svaka cesta povezuje točno dva različita grada, a između dva grada postoji najviše jedna cesta. Ceste su označene brojevima $1,2,\ldots,c$. Tonći svoje putovanje mora proći tako da kad zapiše oznake cesta redom kojim ih je prolazio dobije (strogo) rastući niz brojeva. Dokaži da postoji grad takav da krenuvši iz toga grada Tonći može proći barem $\frac{2c}{g}$ cesta.