This is a puzzler that I got from someone a couple of weeks ago. It was quite interesting to solve it. Thought I will share the puzzler with you. If no one solves it, I will post the solution coming Tuesday...
Assume that there are 3 pairs of King/Queens in a shore. They have to cross this river with a boat which can accomodate a maximum of 2 people at a time. Following is the only rule that needs to be followed at either end of a shore: No Queen should be left alone (without her King) with another King (even if the other King's Queen is around)...
Friday, June 23, 2006
King/Queen Puzzler
Posted by Suresh Sankaralingam at 6:51 PM
Subscribe to:
Post Comments (Atom)
Posts
14 comments:
Come on folks... did any of you try it? If you think it is rudimentary, it is wrong. If you think it is a prank, you are wrong again. The solution to this problem is based on pure logic...
I tried and I assumed, any queen can travel alone and also travel with any other king in the boat.
Heres the solution
----------------------------------
side A [side B]
k1q1, k2q2, k3q3 [__NONE__]
(k1q1) -> leaves q1
<- k1 goes back
----------------------------------
k2q2,k3q3,(k1)
(k1q2) -> k1q1 (stays)
<- q2 goes back
----------------------------------
k2q2,k3q3 [k1q1]
(k2q2) -> k2 (stays)
<- q2 goes back
----------------------------------
q2,k3q3 [k1q1][k2]
(k3q2) -> k3 (stays)
<- q2 goes back
----------------------------------
q2,q3 [k1q1][k2][k3]
(q2,q3) -> Both stays
----------------------------------
__None__ -> all pairs here
----------------------------------
persons within [] are on sideB
persons within () are travelling
persons with no bracket on sideA
Here is some notation.
Lets call them K1, K2, K3 and Q1, Q2, Q3 respectively. K1 is king 1 and his wife is Q1. Similar association for the others. Lets call the two shores Shore A and Shore B.
Trip 1: K1 and Q1 move from Shore A to Shore B. Q1 is left behind on Shore B and K1 comes back to Shore A.
Trip 2: K1 jumps off the boat on Shore A. Q2 and Q3 jump aboard and travel to shore B. Q2 is left behind on shore B and Q3 comes back on the boat to shore A. At this point. We have two queens on Shore B. Three kings on Shore A and one queen in the boat. Hence the condition is met.
Trip 3: Q3 jumps ashore on Shore A. K1 and K2 board the boat and travel towards shore B. K2 disembarks and K1 and Q1 come back to travel back to shore A. Hence at this point we have K2 and Q2 on shore B. K3 and Q3 on shore A and K1 and Q1 in transit. Hence the condition is again met.
Trip 4: Both K1 and Q1 disemabark at shore A. Now K1 and K3 board the boat and moves toward shore B. Both K1 and K3 diembark on shore B and Q2 boards the boat to move to shore A. At this point we have all kings on shore B, two queens on shore A and one queen in transit.
Trip 5: Q2 disemabrks on shore A. Q1 and Q2 move back to shore B. Q1 and Q2 disembark. K3 boards the boat to move to shore A. At this point we have K1, K2, Q1 and Q2 on shore B. Q3 on shore A and K3 in transit.
Trip 6: K3 and Q3 move to the other side.
Hence we have achieved the objective keeping the constraint in mind. Do lemme know if this solution is ok
Shankar: In step2, you violate the condition that you cannot have 2 kings and 1 queen on one shore.
Anup: U r right ! Good job!!
I have a solution that can do it in 9 steps instead of 11. If you have more time, you can try it out...:)
@ Mindframes: thanks...whoa 9 steps..will look into that..
at either end of a shore: No Queen should be left alone (without her King) with another King
dude, the queen is still on the boat.. (Tell the king, its dangerous to attack (!?) the queen on boat!).
In step 2, k1 & q1 (who are a pair are in the shore, and q2 goes back in boat, leaving k2 in the shore B) Also, it has to be "k2q2,k3q3,[q1]", instead of "k2q2,k3q3,(k1)
Still, I beleive, mine is right.
sdpal: One thing that is incorrect in your assumption is this.
"No Queen should be left alone (without her King) with another King (**even if the other King's Queen is around**)
Following is my interpretation of your steps.
[k1q1,k2q2,k3q3] [NONE]
Step 1: k1q1 leave shore A
[k2q2,k3q3] == [k1q1]
Step 2: k1 goes back from shore B
[k2q2, k3q3] =k1= [q1]
Step 3:
You show (k1q2) taking the trip. If you do that, the people in shore A are
(k2, k3q3) while (k1q2) are in flight. The (k2, k3q3) combination is invalid. Am I missing something?
sdpal:: sorry about that... the rule is that you can't have a queen with 2 kings around even if she has her king... My bad.. I wasnt clear on that...
You are right based on what you assumed. But the real problem doesnt allow you to have more kings than queens on any side.
K1Q1K2Q2K3Q3 --K1Q1-> K1Q1
K2Q2K3Q3 <--K1-- Q1
K1K2K3 --Q2Q3-> Q1Q2Q3
K1K2K3 <--Q3-- Q1Q2
K3Q3 ---K1K2-> K1Q1K2Q2
K3Q3 <--K2Q2- K1Q1
Q2Q3 --K2K3-> K1Q1
Q2Q3 <--Q1-- K1K2K3
Q2 --Q1Q3-> K1Q1K3Q3
K2Q2 <--K2-- K1Q1K3Q3
--K2Q2-> K1Q1K2Q2K3Q3
Cool dude !! You nailed it !!!
See if you can do it in 9 steps... If you look at your steps based on what you wanted to achieve to get to the result, you can reduce the number of steps...
I found the 9 step solution in the morning, but could not reproduce it now.
(I promise, I didnt look at the answer)
k1q1 k2q2 k3q3 ---k1q1--> NONE
k2q2 k3q3 <--k1----- q1
k1 k2 k3 ---q2q3--> q1
k1 k2 k3 <---q3--- q1q2
k3q3 ---k1k2--> q1q2
k3q3 <--k1q1--- k2q2
q1 q3 ---k1k3--> k2q2
q1 q3 <--q2----- k1k2k3
q1 ---q2q3--> k1k2k3
q1 <--k1----- k2q2k3q3
---k1q1--> k2q2k3q3
Cool SDPal !! Great job folks...
Well, the 9 step solution is as follows:
If you observe all your solutions, the key is to have the boat in shore A with K1,K2,K3 in shore A and Q1,Q2,Q3 in shore B (or vice versa). In step 3, we got it the other way around (the boat stays in Shore B) with K1,K2,K3 in shore A and Q1,Q2,Q3 in shore B. So, the reversal is the key.
K1Q1,K2Q2,K3Q3 == NONE (Initial State)
K1Q1 K2Q2 ==K3Q3==> (Step1)
K1Q1 K2Q2<==K3== Q3 (Step2)
K1K2K3 ==Q1Q2==>Q3 (Step3)
K1K2K3 <==Q1== Q2Q3 (Step4)
K2K3 ==K1Q1==>Q2Q3 (Step5)
K2K3 <==K1== Q1Q2Q3 (Step6)
K3 ==K1K2==>Q1Q2Q3 (Step7)
K3 <==Q3== K1Q1K2Q2(Step 8)
NONE ==K3Q3==> K1Q1K2Q2K3Q3 (Step 9)
The reversal is done by just bringing a king in a dummy trip and returning it back.
I used the traditional method of proving LHS=RHS by doing something from RHS and something from LHS and mangle around to solve it..:)
Post a Comment