Maximum Winning Chance Choosing Three Horses!
Question:
Once the ancient city of Troy was under the threat of attackers from a foreign kingdom. King Priam gave the duty of preventing the attackers to his son Prince Hector. The prince decided to take three horses from the stable. But the horses were a bit naughty. The horses were stationed in a single line. As such, every horse had the chance to make friendship with the horse beside him. If three horses are chosen and at least two of the three doesn't have friendship with each other, then they don't get any inspiration to get into battle. But, if two of the horses are friends with the third horse, then they spend their time gossiping. If there are a total of
50
horses in the stable, then in how many ways can Hector choose his three horses where the probability of his winning the war is maximum?
My approach:
i thought any two can be friends.. so 25 pairs of friend.. that means if i choose any pair.. there will be 48 other horses to choose from .. ultimately which means 48C1 = 48..again 25 pairs to choose from .. 25C1= 25 so total ways to choose is 25 * 48 = 1200. But it's wrong
Note: I don't know combinatorics much. Just Started Learning. Can anyone help me with this problem?
Let's label the $50$ horses in the row by numbers $1,2,\ldots, 50$.
Standing in the row, they make $49$ pairs of horses next to each other (who have made friends with each other): $(1,2); (2,3);\ldots; (49,50)$. Note Prince Hector needs to pick one of those pairs, and then pick another horse who is not a friend of any of the two horses in the pair.
- If Prince Hector picks one of two pairs at the "ends", i.e. either horses $(1,2)$ or $(49,50)$, he cannot pick the horse immediately next to the pair (i.e. $3$ or $48$, respectively), but he can pick any of the other $47$ horses. Thus, there are $2\times 47$ ways to do it.
- If Prince Hector picks any other pair (say, $(25,26)$), then he cannot pick the horse preceding that pair (say, $24$) or following that pair (say $27$), but he can pick any of the remaining $46$ horses. There are $47$ such pairs, so the number of ways to do it is $47\times 46$.
Altogether, Prince Hector can make his choice in $2\times 47+47\times 46=2256$ ways.