perplexus.info :: Numbers : Country With n Cities

Country With n Cities (Posted on 2024-08-25)

In a country with n cities, there is a recurrent one -way flight between every pair of cities. Every flight has a constant price in the range $100, $120, $140, $160, $180.

A $N flight ticket gives unlimited access to flights that cost $N, and tickets can be traded for tickets of lower prices.

For example, with a $160 ticket, Brad could take a $160 ticket, trade his ticket for a $120 ticket, then take a $120 flight.

Alice loves flying and wonders how many successive flights she can take with one ticket.

Determine the minimum value of n needed to guarantee, that she can take 4 such flights.

No Solution Yet Submitted by K Sengupta

Rating: 2.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)

re: I do not understand

| Comment 2 of 3 |

(In reply to I do not understand by Steve Herman)

I do agree that the flights must be distinct. What you need to prove is that no matter how the costs are assigned to the flights then there is such a four-flight sequence embedded within the weighted graph.

Posted by Brian Smith on 2024-08-26 09:48:18

Please log in:

Login:
Password:
Remember me:

Sign up! \| Forgot password

Search:

Search body:

Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info