The Coin Collector
Mario has to meet the Princess at the opposite node of the network, as shown above. The digit on each node indicates the number of coins he collects upon arriving at the node. He can visit each node only once.
For example, if Mario follows the red arrow trail illustrated below, he will obtain 1 + 6 + 3 + 4 = 1 4 coins before reaching the Princess.
To prove his love, the Princess demands that Mario collect exactly 17 coins (as that is her favorite number). Can Mario accomplish this task?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
2 solutions
Moderator note:
This solution has some very nice, careful casework. While it is longer in length, the images make the elimination of all the cases immediately clear, so it's a much faster and easier read.
Such a materialistic princess! If I were Mario I won't even bother to meet her... Otherwise, clear solution!
Log in to reply
Maybe Her highness is just too smart. Lol...
Log in to reply
So she already knows it is impossible? What a smart way to reject people!
Log in to reply
@Christopher Boo – Maybe she's testing Mario's mathematical skills just like some rich ladies did. :)
Log in to reply
@Worranat Pakornrat – I thumbed up this question because I love Mario and Princess. What an awesome childhood video game nostalgia!
I wish that I can ask such Nintendo controller console questions that involves games, like Starfox! XD
Log in to reply
@Michael Huang – Well, thanks. I'll have to try Starfox first then. Lol...
Poor Mario....
Log in to reply
Maybe the Princess was just testing his wit. If he claimed "Oh, dear Princess, it's impossible.", she might be lenient enough to choose other number. (Just a thought...) :)
Superb solution
We can also try finding the sum of every path from Mario to Princess and check if any of the sums is 17, but this method would be inefficient because there are so many possible paths. This leads me to think how many paths exist starting from Mario and ending at the Princess? How can we calculate this quantity?
Log in to reply
Not sure if you still want an answer, after more than a year and a half, but here goes.
For this specific graph, you can enumerate all the paths and count them, and it would be tedious, but once you had done it, you would have done it...
Questions of efficiency, of course, are more interesting when you want to solve the problem for a generic graph, so let me try to address that.
If the edges on the graph had arrows so they could only be traversed one way, and furthermore, there was no way to go around a cycle (what is called a Directed Acyclic Graph, or DAG for short) then you can topologically sort it (i.e give a numbering of the vertices such that all paths are increasing) and then solve the problem by Dynamic Programming.
On a generic graph, specified by its adjacency matrix A, the (i,j)th entrie of the matrix of the matrix A^k gives the number of walks of length k between i and j. (Here, a 'walk' means we remove the restriction that we cannot revisit vertices).
If you really want to count actual paths (cannot revisit vertices) then this is a very hard problem. To be more precise, the problem is NP-hard, because if you could count paths efficiently (in polynomial time) then you could also determine whether there was a Hamiltonian path, which is a well-known NP-complete problem.
So, I don't know whether there is a solution that is better than enumerating all possibilities, but whatever the best solution is, it is not going to be efficient (unless P=NP).
Wow, you told the explanation like a pro
Is this not a possible solution ? 1 > 6 > 3 > 6 > 7 As the 6 coins are already taken the second time when he comes back, he gets nothing and the total shall be 17. I think, the question did not demand the direction or repetition of the path.
After all he has to make the princess happy :) Please consider.
Log in to reply
It stated that you may only visit each node once.
5, 1 , 6, 2, 7
There are only seven ways to write 17 as the sum of three or more different numbers from 1 through 7. 1 7 = 7 + 6 + 4 1 7 = 7 + 6 + 3 + 1 = 7 + 5 + 3 + 2 = 7 + 5 + 4 + 1 = 6 + 5 + 4 + 2 1 7 = 7 + 4 + 3 + 2 + 1 = 6 + 5 + 3 + 2 + 1 It is easy to check that none of these corresponds to a route from Mario to the princess. (The closest is 1, 6, 3, (6), 7, which would work if Mario was allowed to revisit a node.)
A quick way to generate these sums is as follows.
-
With three numbers we can get at most 1 8 = 7 + 6 + 5 ; there is only one way to lower this by one without running into doubles.
-
With four numbers not including 7, we can get at most 1 8 = 6 + 5 + 4 + 3 . The only we to subtract one is by lowering 3 to 2. All other possibilities must include 7. For the remaining three numbers, we need a total of 10. This can be done as 1 0 = 6 + 3 + 1 = 5 + 3 + 2 = 5 + 4 + 1 .
-
With five numbers, the minimum is 1 5 = 1 + 2 + 3 + 4 + 5 . To add two, we can only increase either 4 or 5 by two. (Or add one to each of them, but that gives us nothing new.)
Your solutions appears to be rather "brute force" and it's certainly easy to list out all the possible cases when the sum (of 17) is very small. Is there a more systematic way to solve this? Especially if the number "17" is replaced with something much much larger?
I was thinking of something along the lines of generating functions or partition of an integer but that doesn't get me anywhere. Thoughts?
Log in to reply
For bigger networks I would exploit the geometry of the situation instead, and make this a computer science exercise about graphs.
Log in to reply
In this case, an alternative would be:
-
In the first column, Mario can take { 1 , 5 , 6 } coins.
-
In the last column, Mario can take { 4 , 7 , 1 1 } coins.
-
Together, first and last column add up to { 5 , 8 , 9 , 1 0 , 1 2 , 1 3 , 1 6 , 1 7 } .
-
Therefore the second column must produce { 0 , 1 , 4 , 5 , 7 , 8 , 9 , 1 2 } .
-
But the possible totals in the second column are { 2 , 3 , 5 , 6 , 8 , 9 , 1 1 } .
-
The overlap is 5 , 8 , 9 . Mario must visit exactly two of the nodes in the middle column.
-
It is now easy to consider these three possibilities and rule them out because of connectivity.
Log in to reply
@Arjen Vreugdenhil – That's what I thought too. Thanks for showing the working!!
@Arjen Vreugdenhil – Would you please explain how you got the third part of your answer? {5,8,9,10,12,13,16,17}
Log in to reply
@Brenda Gaines Hunter – I simply made all possible sums based on the first and last column: 1 + 4 = 5 5 + 4 = 9 6 + 4 = 1 0 1 + 7 = 8 5 + 7 = 1 2 6 + 7 = 1 3 1 + 1 1 = 1 2 5 + 1 1 = 1 6 6 + 1 1 = 1 7 .
Basically Dijkstra's algorithm
Technical solution is discussed to death, I'm more concern about the rant, what a shame. He cannot prove his LOVE?
The total amount of coins in the network = 1 + 2 + 3 + 4 + 5 + 6 + 7 = 2 8 coins. Therefore, if there is such a route to collect 1 7 coins before reaching the Princess, there will be 1 1 coins left untouched in the network. It will be easier to investigate the partitions of 1 1 coins as red nodes with blue nodes being the intended route:
Case #1: 1 1 = 7 + 4
We can see that by visiting all blue nodes, 1 7 coins can be obtained, but the route to the Princess' node can not be traveled without passing the red node. Thus, case #1 is not applicable.
Case #2: 1 1 = 7 + 3 + 1
In this case, we can not visit all blue nodes without repeating the same route or passing the red node. Thus, case #2 is also not applicable.
Case #3: 1 1 = 6 + 5
By revolving around the blue nodes, we will end up at the 3-node, but from there, it's not connected to the Princess' node. Thus, case #3 is also not applicable.
Case #4: 1 1 = 6 + 4 + 1
The red nodes separate the blue nodes apart, so it's impossible to visit all the blue nodes without passing the red ones. Thus, case #4 is also not applicable.
Case #5: 1 1 = 6 + 3 + 2
Similar to case #4, the red nodes separate the blue nodes apart, so it's impossible to visit all the blue nodes without passing the red ones. Thus, case #5 is also not applicable.
Case #6: 1 1 = 5 + 4 + 2
Similar to case #2, we can not visit all blue nodes without repeating the same route or passing the red node. Thus, case #6 is also not applicable.
Case #7: 1 1 = 5 + 3 + 2 + 1
Finally, all the blue nodes are not connected to Mario, so the last case is also not applicable.
As a result, it will be impossible for Mario to collect 1 7 coins before reaching the Princess.