Jealous Neighbors

Aug 09, 2014

RAY: This week's Puzzler was sent to me from Bruce Robinson, a professor of civil and environmental engineering at the University of Tennessee. It goes like this: There are 25 jealous people who live in the squares of a five-by-five grid. We're gonna number the squares, starting in the upper left-hand corner, 1 through 25.

TOM: So the first row starts with 1, the second row starts with 6, the third row starts with 11, and so forth.

RAY: Right. Remember, each person is jealous of his adjacent neighbor. Not his diagonal neighbor, but the person up or down or left or right of him. Each aspires to move into the apartment of his adjacent neighbor.
The question is very simple: What is the fewest number of total moves that can accomplish this?

Answer: 
RAY: So, if you draw this grid, the square in the upper left-hand corner we could say is one, and the one next to it is two, three, four, five, and then the line below that is six, seven, eight, nine, 10, 11, 12, right? All the way to 25. Got it?

TOM: I got it.

RAY: Now, each person who lives on the floor aspires to move into the apartment of one of the adjacent neighbors. So number one can move to square number two, or number six, for example.

TOM: But not diagonally.

RAY: Not diagonally.  So, here's the question. Why would anyone live in such a stupid building? No, the question is, what is the fewest number of total moves that will allow every person to move to an adjacent square?

TOM: Well, unencumbered by the thought process, I concluded right away when you gave this problem that the answer was either going to be 26 or millions.

RAY: Well, millions is close. Let's letter the first one A, the next one B, the next one A, the next one B, et cetera, et cetera. Then, everyone who's on an A square must, by definition, move to what?

TOM: A B square.

RAY: Right. And everyone who's on a B square must move to an A square. It's pretty obvious if you draw it out. Now, if you add them up, by some stroke of bad luck, you got 13 A squares and only 12 B squares.

TOM: Someone's got to move out of the building.

RAY: There is no fewest number of moves. It is impossible for this to happen. I know, it was a little sneaky.

TOM: No, no. Impossible is a good answer!

RAY: Impossible is a good number of moves. So, who's our winner, anyway?

TOM: Ah, the winner is Winston Teitler from Albany, California. Congratulations!

Get the Car Talk Newsletter