Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The goal is to move the pieces so as to gather them all in the same square - in the minimal number of moves. Chess pieces can move as normal. Additionally, whenever the king and one or more knights are placed in the same square, the player may choose to move the king and one of the knights together from that point on, as a single knight, up to the final gathering point. Moving the knight together with the king counts as a single move.

Given the following setup, what is the minimum number of moves to gather all the pieces together? Provide the path as well as the answer.

Chess board

Source: USACO training pages - I cannot figure out why my answer appears to be wrong and the site provides no reason for its answer. This is one of 20 cases.

share|improve this question
    
looks like 6... –  Karolis Juodelė Jan 4 '13 at 23:16
4  
I get Kc4, Kb3 (combining with the knight), and then all knights move to d2 for a total of 5 moves. Not posting as an answer because I'm not sure whether I understand the king/knight combining condition right. –  Lopsy Jan 4 '13 at 23:16
    
@Lopsy thank you a lot - that is the answer. Post it and I'll Upvote/accept it. –  Jakob Weisblat Jan 4 '13 at 23:38
1  
"Why can't it be done in 4 moves?" is a pretty important question to answer as well, by the way. At least in general, when solving problems. If they just want you to show how it can be done in 5, then fine. But now I'm not going to be able to sleep tonight because I can't disprove 4. –  Arthur Jan 4 '13 at 23:56
1  
@Arthur Consider just the three knights, without the king. They all have to meet at some point finally. If this point is not the same as any of the knights' initial positions, then each knight should move atleast once, hence they take atleast 3 moves. And if the final position is one of the knights' starting position, other knights take 2 steps each to reach there, a total of 4 steps. The square that can reached by all knights in 3 steps is only d2. And the king requires atleast 2 moves to reach there. Also, the knights cannot all reach the king's position in 4 moves, which covers all cases. –  polkjh Jan 5 '13 at 1:49

1 Answer 1

up vote 2 down vote accepted

It's possible in five moves: 1. Kc4, 2. Kb3 (combining with the knight), and then all three knights move to d2 for a total of five moves.

Here's an argument that it's not possible in four: if there were a four-move solution, then the meeting square must be d2, because it's the only square that all three knights can reach in less than four moves total.

If we only have four moves to get all four pieces to d2, then we can't waste a single step: every single move must either be a piece reaching d2, or a knight combining with a king. But examining the position of the king, this is impossible: no knight can reach the king in a single move, nor can the king reach any knight or d2 in one move. So four moves is impossible, and five is the best we can do.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.