# Tag Info

71

This is not impossible. Here is a possible solution:

57

You can't. Color them like a checkerboard - the top-left-front cell is black, and the ones adjacent to it are white, and the ones adjacent to those are black... Each prisoner in a white cell must move to a black cell, and each prisoner in a black cell must move to a white cell. But there are more of one color than the other, since there are an odd number ...

55

Explanation:

48

My most sincere apologies for this. Really.

45

Probably a bit simpler than what you were looking for. Looking at the other answers, I feel like there might be some details missing from your question.

44

It works when you use a really wide line:

36

It is impossible. Quite the same problem is "Seven Bridges of Königsberg", it was solved (proven) by Euler. Suppose you have drawn such a line and follow it from one room to another. Since you must use each door you must have a look at each room out of 5. What are these rooms? There will be 3 (at least) rooms you always go through - if you enter it you ...

36

This link explains why this puzzle is unsolvable: It also suggests a clever solution in "3 dimensions" (actually, a 2D solution transfomed into a 3D one).

34

Just for fun: Actually, there is solution, which formally satisfies all the rules. You just need to walk through a wall! Hard, but possible!

31

Option 1: Ask a mathematician to explain why the complete bipartite $K_{3,3}$ graph is non planar. Option 2: Put this drawing and a stack of cash in an envelope. Deliver the envelope to a competent engineer.

27

Yes! This is a classic graph theory problem. Anywhere where lines meet is called a vertex, and the degree of a vertex is the number of lines that meet there. Euler proved that as long as a graph has either 0 or 2 vertices of odd degree, and the graph is connected (consists of a single piece), then it can be drawn as you specified. Furthermore, if there are ...

26

Yes there is a solution with a very simple strategy: Start in (1,1). Always go the right most square that's unvisited I'll try to illustrate it. I checked it by hand on an 9x9 board and a very nice pattern emerges that makes it clear it works on any X by X board. \begin{array}{c|cccc} \ &1&2&3&4&5&6&7&8&9\\ \hline 1 &...

23

Similar to klm's solution, this one requires a little bit of lateral thinking but doesn't actually involve walking through a wall. Instead, you have to fold the corner of the piece of paper that the picture is drawn on, to form a bridge over a wall.

21

First of all, with some half-sibling incest, it's possible for a student to only have one grandpa. If that happens, then all 64 students have that grandpa as well. So, we can assume everyone has two grandpas. Let's say that a "grandpa triangle" is a set of three grandpas, where each pair have a common grandchild. If there is no grandpa triangle, then ...

21

Let $(x,y)$ be the square in row $x$, column $y$, so that a fantasy knight can move from $(x,y)$ to $(y,z)$. A closed tour is described by a cyclic sequence $$x_0,x_1,x_2,\ldots,x_{99^2-1},x_{99^2}=x_0,$$ where the knight moves from $(x_0,x_1)$ to $(x_1,x_2)$, then to $(x_2,x_3)$, and so on up to $(x_{99^2-1},x_0)$, then finally back to $(x_0,x_1)$. Each ...

20

I used integer linear programming, as follows. Let binary decision variable $x_{i,j,k}$ indicate whether cell $(i,j)$ contains value $k$. Let $N_{i,j}$ be the set of neighbors of cell $(i,j)$. The constraints are: \begin{align} \sum_{k=1}^{64} x_{i,j,k} &= 1\\ \sum_{i=1}^8 \sum_{j=1}^8 x_{i,j,k} &= 1\\ x_{i,j,k} &\le \sum_{(i',j')\in N_{i,j}} x_{...

19

You can draw a graph with six vertices, one for each room and one for the outside. Draw an edge to represent each door. The puzzle asks for an Eulerian path, which can be done if no more than two vertices have an odd number of edges coming in. In this graph the top two rooms, the middle bottom room, and the outside all have an odd number of edges coming ...

19

As atonement for my insolent lateral-thinking answer, I offer an optimality proof. If you keep repeating the correct code, the are six possible different orders: 1 abcdabcdabcd 2 abdcabdcabdc 3 acbdacbdacbd 4 acdbacdbacdb 5 adbcadbcadbc 6 adcbadcbadcb Each of the orders contains four possible codes. The orders are important, since after testing one code ...

18

Alternatively, going "through" a door need not necessarily be interpreted in the same way as one would in a house. This single, continuous line passes exactly once through each door, which is the constraint in the original question. Of course, it also conveniently side-steps making any other assumptions and takes certain liberties with the walls.

18

Here's one solution (not sure if it's unique): How I found it: by following the logic used to answer this similar question. How I found this specific solution:

16

Each of the four diagrams with letters but in each case These are, respectively, so this is a memorial to I expect it was constructed using graphs because

16

There are a few nodes that can be linked together immediately, giving us a good starting point: Most of those starting links are on the bottom half of the triangle, so that's where I started. Specifically, I was quickly able to fill in the bottom-right: Followed by the rest of the bottom: The next bit threw me briefly, but I managed to figure out the ...

15

Reiterate problem Bunny: a chess piece which moves like a bishop but only one square from its current position. It may also hop over another piece. Hop: a bunny hops when another piece is in a square touching the current square (no diagonals). In its turn it occupies the square 3 squares from its current square in the direction of the hopped piece. The ...

15

The state you have to end in will be Here's a possible trip you can take:

15

Number the nodes as follows: A valid solution is to check: To see that this works, first note that the fox can only go from a hole in an even-numbered level of the tree to a hole in an odd-numbered level of the tree and vice-versa. If the fox starts in an odd level, the sequence 4,2,5,2,1,3,6,3,7 guarantees the hunter will catch it. This works because the ...

15

First, I found all pairs that satisfy the criteria: Next, we can start making some deductions: That gives this new grid: Next, That resolves the rest of the path, but not the numbers: For the numbers, The final answer to the puzzle: And to double-check the result:

15

First it is easy to see that From here, there is only one "odd" square that as stated by @daw in comments, It looks to me like this The only remaining way to Continuing, we could turn left or right, but The upper route For the other route shown above, Thus, only one possibility remains for Looking to the next square number, Now turning our ...

14

This is impossible Assume 2 houses are fully connected to 3 wells. There must be an 'inner' well which is surrounded by the connections to the other 2 wells. For the third house to be connected to the inner well, it must be in one of the spaces between the inner well and one of the outer ones. But this means it is seperated from the other outer well. ...

14

An observation is.. Using this observation, one of many possible solutions is (left image is front of cube, right image is inside view):

Only top voted, non community-wiki answers of a minimum length are eligible