12
$\begingroup$

In a certain country, there are $n$ cities. Between every pair of cities, there is a fixed travel cost to go from one city to the other.

An idiot and a genius both decide to tour this country by visiting every city once. They start their tours at the same city. When choosing which city to visit next, the idiot always picks the city that is most expensive to travel to, of the ones not yet visited. Conversely, the genius always chooses the city that is cheapest to travel to. They do not revisit their starting city.

For some really special value of $n$ and travel costs, is it possible for the idiot to spend strictly less than the genius? If not, I demand proof.

Clarification: Travelling from City X to City Y costs the same as travelling from City Y to City X.

(This was a problem I encountered at my math summer camp. I don't know the solution.)

(I'm assuming that the solution has some form of math so I'm tagging with mathematics. Please change if this isn't very right.)

Improve this question
$\endgroup$
7
  • $\begingroup$ Could you clarify if the costs for traveling A-B and B-A should be the same or if they can differ. $\endgroup$
    – gtwebb
    Commented Oct 17, 2016 at 2:39
  • $\begingroup$ They are the same. $\endgroup$
    – greenturtle3141
    Commented Oct 17, 2016 at 2:40
  • $\begingroup$ Are you saying that, at each stage of the journey, the traveler goes to the {most|least} expensive of the cities not yet visited? So, if they start at City A, and go to B and then C, that the fourth stop cannot be City A or B? $\endgroup$
    – Peregrine Rook
    Commented Oct 17, 2016 at 3:48
  • 1
    $\begingroup$ Since you didn't allow the "straight line" answer, do we assume there are N-1 paths to/from a city? In other words, a single city can be reached from any other city without traveling through another city. $\endgroup$
    – halfmang
    Commented Oct 17, 2016 at 16:43
  • 1
    $\begingroup$ @jstnthms yes, that will be true. $\endgroup$
    – greenturtle3141
    Commented Oct 17, 2016 at 18:41

5 Answers 5

Reset to default
6
$\begingroup$

I encountered this problem in Peter Winkler's book "Mathematical Puzzles: A Connoisseur's Collection". I didn't check the solution there, so it might be more elegant than my proof below, but anyway:

No, it is impossible that the idiot pays less than the genius.

In order to see this, we will show that for every travel cost of the idiot, there is a travel cost of the genius, which is equal or cheaper, and all these genius' travels are different.

Let's assume the idiot travelled the towns in order $1 \rightarrow 2\rightarrow ... \rightarrow n$. If the genius visited town $n-1$ before town $n$, then we pair the idiot's travel $(n-1, n)$ with the genius' travel $(n-1, *)$. Notice that $C(n-1,*)\leq C(n-1,n)$ and everything is fine so far. If the genius visited also town $n-2$ before town $n$, then we pair the idiot's travel $(n-2, n-1)$ with the genius' travel $(n-2,*)$. Notice that $C(n-2,*)\leq C(n-2,n)\leq C(n-2,n-1)$, so again everything is fine. We continue like this, until we get to some town $k$ which the genius visited after town $n$. Then we pair the idiot's travel $(k,k+1)$ with the genius' travel $(n,*)$. Notice that $C(n, *)\leq C(n,k)\leq C(k,k+1)$, so once again everything is fine. Now we continue by checking whether the genius visited town $k-1$ before $k$ and pairing the idiot's travel $(k-1,k)$ with either $(k-1,*)$ or with $(k,*)$ from the genius.

We keep going like this, until eventually pair all idiot's travels with genius' travels and solve the problem.

Improve this answer
$\endgroup$
2
  • $\begingroup$ To clarify, does the * mean "some city the genius ended up going to"? If so, the $<$ signs should be $\leq$ for equality possibility? $\endgroup$
    – greenturtle3141
    Commented Oct 18, 2016 at 19:59
  • $\begingroup$ @greenturtle3141 that's correct, you can/should place everywhere non-strict inequalities, I just didn't bother to type "\leq" every time:) $\endgroup$
    – Puzzle Prime
    Commented Oct 18, 2016 at 20:07
5
$\begingroup$

For the genius to end up paying more for their route than the idiot, there must exist at least one expensive trip between a pair of cities that the genius is forced to take but where the idiot can use a cheaper route.

Since the idiot must also visit all cities, they will visit both of the cities with this expensive trip in between. Since they always pick the most expensive trip available from each city, either there must be an even more expensive trip from the first city (of the two) that they arrive in, or they must already have visited the other city.

But if there is an even more expensive trip available, they do not spend less than the genius. And they cannot have visited the other city before arriving in the first (or it would not be the first).

Therefore the idiot can not end up spending less than the genius.

Improve this answer
$\endgroup$
9
  • $\begingroup$ If I understood correctly, you're saying that for every pair A-B in the genius's path, there is an edge with higher cost leaving from the one that is visited first. This is not a bijection however; if the genius does A-B-C and the idiot visits B before A and C, then you're counting the B-x edge twice. $\endgroup$
    – ffao
    Commented Oct 17, 2016 at 15:11
  • $\begingroup$ @ffao I didn't say "for every pair", I said "there must exist at least one" (i.e., "for some pair"). For the genius to "lose", there must be some pair A-B where the genius pays more than the than the idiot to visit both. For the first one of A or B that idiot visits, the idiot must either have visited the other (but then it wouldn't be the first) or take a path even more expensive, else they must choose the same path as the genius, hence it cannot be the one where genius pays more. (Note, BTW, that the graph is complete, i.e., there cannot be any pair of cities without an edge between them.) $\endgroup$
    – Arkku
    Commented Oct 17, 2016 at 16:27
  • $\begingroup$ Suppose genius takes path A-B-C with costs 10 and 10, and idiot takes path B-A-C with costs 15 and 4. Idiot "pays more" to visit the pairs B-A and B-C, but pays less overall (of course, the case I described is actually impossible; but you didn't prove that.) $\endgroup$
    – ffao
    Commented Oct 17, 2016 at 17:11
  • $\begingroup$ (As for why I believe the pair A-B must exist if the genius were to pay more: both make the same number of trips so the genius cannot accumulate the additional cost by going over more edges, so there must be some edge that is responsible for the extra cost but where the idiot takes neither that edge nor a more expensive one.) $\endgroup$
    – Arkku
    Commented Oct 17, 2016 at 17:44
  • $\begingroup$ I already gave you a counterexample in which no pair A-B exists and the idiot pays less. Therefore, whatever your reasoning that guarantees the existence of such a pair is, it must be incorrect unless you address that point. $\endgroup$
    – ffao
    Commented Oct 17, 2016 at 19:17
4
$\begingroup$

Artur's proof is very nice. I did it a different way. First, note that it is sufficient to prove that for any C it is impossible for the genius to take more steps of cost at least C than the idiot. So we can just consider each pair of cities as being either expensive or cheap, and prove that the idiot takes at least as many expensive steps as the genius.

Now suppose the genius takes $r$ expensive steps and the idiot takes $s$ cheap steps. If $r=0$ or $s=0$ we are done, so suppose not. Consider the set of cities from which the genius takes an expensive step, together with the city his last expensive step gets him to. This is $r+1$ cities, and every pair of them must be connected by an expensive route (if there's a cheap pair in that set, then from whichever one he visited first he took an expensive route when there was a cheap route available). Similarly for the idiot we can find $s+1$ cities, each pair of which is connected by a cheap route. These two sets cannot have more than one city in common, so we must have $r+s+1\leq n$; rearranging this, the idiot took more expensive steps than the genius.

Improve this answer
$\endgroup$
0
1
$\begingroup$

Long live the idiot!

imagine all the cities are in a line.
A-2-B-1-C-1-D-1-E-1-F (letters are cities, numbers are distances(cost).)
if the start point is B, the smart guy will do 1+1+1+1, then go back 1+1+1+1+2 for a total of 10.
The idiot will do 2 then go back 2+1+1+1+1 for a total of 8

EDIT

Assuming it is forbidden to go to the same city two times, I think the genius would always win or tie.
The only way for the idiot to win, would be to trick the genius on a long segment that the idiot would not use. To go to every city, only 1 segment can be ignored and that has to be the long one for the idiot. And the only way to make sure the idiot would not use that long path would be to keep it for last, but since a path connects 2 cities, it is impossible to ignore it until the end.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Wouldn't the idiot go to F first? Unless you mean that such an action implies that he must travel through any cities in between, but such thinking is not intended. $\endgroup$
    – greenturtle3141
    Commented Oct 17, 2016 at 2:41
  • $\begingroup$ So we are assuming that the idiot is stupid to the point of taking a tremendous detour on purpose to avoid other cities? $\endgroup$
    – stack reader
    Commented Oct 17, 2016 at 2:48
  • $\begingroup$ No. We are assuming that the question has no lateral thinking. Yes, your answer could be correct. I could even say that part of the cost to travel to a city involves a pit stop in another city, meaning that you technically visit another city on the way. However, this avenue of thinking is non-intentional and is not part of the question. $\endgroup$
    – greenturtle3141
    Commented Oct 17, 2016 at 2:51
1
$\begingroup$

Yes the Idiot can travel less than the genius. For example in the following graph starting at A:

    A
   / \
  2   1
 /     \
B-9-C-4-D
 \     /
  8   3
   \ /
    E

The idiot travels A-B-C-D-E for a sum of 2+9+4+3=18.
The genius travels A-D-E-B-C for a sum of 1+3+8+9=21.

I have different travel costs just to make sure there is an unique smallest in each city.

Improve this answer
$\endgroup$
3
  • 5
    $\begingroup$ In your example there are missing paths between cities (for example you can't get from A to C). The question says "Between every pair of cities, there is a fixed travel cost to go from one city to the other." $\endgroup$
    – Meiffert
    Commented Oct 17, 2016 at 13:37
  • $\begingroup$ @Meiffert: I will look at it $\endgroup$
    – Etoplay
    Commented Oct 17, 2016 at 13:39
  • $\begingroup$ Wont work. Already tried it with all possible combinations $\endgroup$
    – Techidiot
    Commented Oct 17, 2016 at 14:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.