You're on the quest for the pot of gold at the rainbow's end by rowing a boat along a big river. From a distant view, you're not sure where the pot of gold is, so when you meet a nearby fisherman, you ask him, "at which side of the river bank does the rainbow end?"
The fisherman will then point towards one of the two river banks, and you'll follow his guidance downstream with thanks. Then after rowing along the river bank, you take a rest at the nearby pier before asking a villager the same question, who will then point to one of the two river banks, and you'll row your boat as his guidance once again.
There are 3 piers on each river bank, facing as 3 pairs opposite each other with one villager at every pier as shown above, so after reaching either pier, you can't row towards the opposite due to the strong current and have to row towards the next one downstream only. Also, when traveling to the river's end, you'll either succeed or fail, for you can't row against the current should you desire to cross to the opposite side.
If 4 out of these 7 guiding men are "truth-tellers", who lead you to the right place, while the other are "liars", who mistakenly get you off track, what is the probability for you to accomplish your mission?
If this probability can be expressed as , where and are coprime positive integers, submit as your answer.
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.
For better visualization, we will rewrite the guide and pot positions as a graph as shown below:
As we can see, there are 7 available nodes for these people, and so there are ( 4 7 ) = 4 ! 3 ! 7 ! = 3 5 possible combinations.
Since there are less liars, it is easier to think of combinations to the wrong place.
First, let us suppose the far end piers both have liars (red nodes as liars; blue nodes as truth-tellers):
Clearly, with liars at both piers, the direction will be misled no matter what, and with 1 liar left, there is ( 1 5 ) = 5 possible combinations. (Note that if they are both truth-tellers, the mission will also be successful no matter what.)
Second, if the liar stands at the far end pier on the right bank while the truth-teller stands opposite to him, the people at the middle piers have to guide towards the right bank and should be truth tellers:
Again, with this setting, there will be 1 truth-teller left for the remaining 3 nodes: ( 1 3 ) = 3 combinations.
Finally, for the other ways, there are 7 possible outcomes as shown:
Therefore, there are 1 5 ways to go to the wrong way and 2 0 ways to find the pot of gold.
As a result, the probability to succeed = 3 5 2 0 = 7 4 .
a + b = 4 + 7 = 1 1 .