Posts

Showing posts with the label knights

Truth Tellers and Liars in Circle

On a certain island there live only knights, who always tell the truth, and knaves, who always lie.

One day you find 10 island natives standing in a circle. Each one states: "Both people next to me are knaves!"

Of the 10 in the circle, what is the minimum possible number of knights?


Truth Tellers and Liars in Circle


Do you think there can be 5?

Identifying Number of Truth Tellers in Circle


What was the task given?

Recalling the given situation. 

On a certain island there live only knights, who always tell the truth, and knaves, who always lie.

One day you find 10 island natives standing in a circle. Each one states: "Both people next to me are knaves!"

 
Every Knight must be surrounded by 2 Knaves and every Knave has to be surrounded by at least one knight to satisfy the given condition. So there must be Knave-Knight-Knave groups must be standing in circle. 

Now if Knave of previous group is counted for the next group, then there will be 5 knights in the circle as shown below.

Identifying Number of Truth Tellers in Circle


But the question asks minimum possible number of Knights in the circle.

So after forming 3 groups of Knave-Knight-Knave separately (total 9 in circle), the last person will be obviously surrounded by 2 knaves. Hence, he must be Knight. See below.

Identifying Number of Truth Tellers in Circle


This way there can be only 4 knights standing in the circle without violating the given condition.
 

Arrange Positions Around The Round-Table

King Arthur and his eleven honorable knights must sit on a round-table. In how many ways can you arrange the group, if no honorable knight can sit between two older honorable knights?

Arrange Positions Around The Round-Table




Here are the possible combinations!

Source 

Possible Positions Around The Round Table


What was the challenge?

If king K is sitting at the center then the youngest knight must sit to right or left of the king i.e. 2 possible positions for him.

The second youngest knight now can sit either left or right of the group of 2 made above.

The third youngest knight now can sit either left or right of the group of 3 made above.

And so on.

That is every knight has 2 possible positions except the oldest knight who will have only 1 position left.

This will be make sure each of the knight (except youngest one) has at least 1 younger neighbor (youngest one has king as one neighbor).

So after putting youngest in 2 possible ways the next youngest can be put another 2 possible ways. That is 4 possible combinations for 2.

Similarly, for arranging 3 knights' positions there can be 2^3 = 8 possible combinations.

Possible Positions Around The Round Table

This way for 10 knights (excluding the oldest which will have only 1 seat available at the end) there are 2^10 = 1024 possible combinations.

Follow me on Blogarama