97

Ilmari's answer covers the logic of the answer perfectly, but in case anyone's still confused, here's a version of the diagram I find more intuitive (I made it myself while solving the puzzle). The Pink squares are rooms where the princess could be on the given day, the blue squares are where the prince knocks that day, and the black squares are rooms in ...


80

Maybe this diagram will help you visualize the solution: In this diagram, the vertical axis shows the room number (1–17) and the horizontal axis shows the day (1–30). The $\color{red}{\text{red}}$ dots show the rooms on whose door the prince knocks on each day, and the $\color{darkgreen}{\text{green}}$ dots and arrows show the possible ...


48

My most sincere apologies for this. Really.


28

Sure you can. There's finitely many possible mazes, so solve each one in sequence. To solve a maze, imagine you're in that maze. Figure out where you are in the maze by simulating starting on the start space and following the instructions corresponding to the sequence of steps you've taken so far. Then, make the moves that would take you from there to the ...


26

I found a solution that uses 16 moves. After exhaustively checking that there is no solution in 14 moves, I conclude that 16 moves is optimal, because after any odd number of moves the number of white and black squares occupied by knights cannot be equal.


26

Give these names to all the squares: 163 4 8 725 Each number can only be accessed by way of the numbers before and after it (where 8 wraps around to 1). That means they form a loop. Since they can never pass each other up on the loop, their relative ordering cannot change. Therefore it is impossible.


25

In the worst-case scenario, it requires to locate the radioactive rods. Several answers already describe strategies for locating the radioactive rods. I will give another. Testing strategy: Start by testing two rods. If neither of these rods is radioactive, use the five remaining tests on five of the six remaining rods, one at a time. If two of these rods ...


21

You need at least 16 Moves. Let's make the task visually more simple. The initial board is: a4 b4 c4 a3 b3 c3 a2 b2 c2 a1 b1 c1 We cut it into 12 cells and connect only those, which are separated exactly by one move of a knight. Easy to check that the result is the following: c4 - a3 - c2 - a1 | | | | b2 b1 b4 b3 ...


20

Ok, I think I got something. The answer should be : The ancient civilization The operation *|* is performed : Now, the real problem. In order to obtain the result for 2 numbers, we have to And now, all the values in the question : With, of course, the final answer :


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 ...


19

Perform tests of nine sheep on all but one sheep according to the illustrated patterns: The two important properties exhibited are The claim is that given a set of test results there is at most one possible group of five wolves. Suppose instead that some set of test results could have been produced by two different groups of five wolves A and B. Then both ...


18

This is a pretty common puzzle. Warm up Answer: Advanced Answer Explanation:


17

There are only 16 different possible state combinations of the four ancestor cells, and you can find them all in the image, so there is a unique answer. The rule is as follows:


17

The pattern is self-similar, and can be formed by repeatedly scaling and rotating copies of itself: An alternate dissection that fits in a diamond:


15

The solution assumes that she cannot ever stay in the the same room. Either on even days she is in even rooms or on even days she is in odd rooms. As he is going from room 2 to room 3 he is going from an odd day to an even day. She can go from room 3 to 2 if she is in even rooms on even days. She can never pass him if she is in odd rooms on even days as he ...


15

Treat each soldier as a binary digit, $1$ if facing east and $0$ if facing west, and order them from west to east (i.e. left to right). We start off with a random $n$-digit binary number, and the algorithm is: The process can only end when the number is a string of $0$'s followed by a string of $1$'s, i.e. it is one less than a power of two. Its digit sum ...


15

A series of variants of this puzzle came up in one of the trade magazines - possibly Communications of the ACM. When two soldiers face each other, they are required to turn around. Assuming the soldiers are considered to be interchangeable, this is equivalent to the soldiers marching 'through' each other (or swapping positions, if you prefer). In this ...


15

Edit: Now that @GOTO 0 got it in 16, I can at least prove that his solution is optimal. Proof: My best was:


15

Here is a revised solution, for... ...which  (again) seems like the maximum to me.  has been verified by Molhan as being maximal.   Trivial steps have been condensed. These steps may be reversed, exchanging the roles of pegs 1 and 6, to complete moving the whole tower from peg 1 to peg 6. This approach was derived by ...


14

Your link to Diophantine equations shows that you already have an idea of the answer. The only actions available are filling a jug completely from the tub, emptying a jug completely, or pouring one jug into another. If we fill empty jug $k$ from the tub, then the amount of water we have is increased by $v_k$. Similarly, if we empty jug $k$ when it is full, ...


14

Not exactly answering this question, but given 9 infections still on an 8x8 board, it is actually possible to delay the inevitable until 40 days. Pretty counter-intuitive huh? Locations are A1, A5, A8, B3, B7, D1, E8, G1, H8 Also, I believe that this is the maximum for an 8x8 board with any number of initial infections. As for the edges argument I made ...


13

The standard solution is that all clones signal their first passage using some state of the bulbs to an elected clone, the "counter", who counts how many there are. You need to address 3 things. 1. How to transmit the information of one's passage reliably, 2. How to deal with the initial state, 3. How to elect a counter. Note that the lights don't ...


13

I have a solution with a success rate of 93.5%, according to my simulations. The reason this solution works so well is Here's my code that I used to verify my solution:


13

Thinking out loud, not a solution yet, but spoilery enough that I didn't want to put it in a comment: However, Still-not-an-answer UPDATE: However, I also notice that the situation is not symmetrical: we may know a way to find $k$ wolves among $n$ sheep using $t$ tests, but that won't help us at all to find $n-k$ wolves among $n$ sheep. (Under the ...


12

Here is a permutation that works upto n=12: 1 6 11 4 5 10 15 8 9 14 19 12 13 18 23 16 17 22 27 20 21 26 31 24 25 30 35 28 29 34 39 32 33 38 43 36 37 42 47 40 41 46 51 44 45 50 3 48 49 2 7 52 Essentially, keep the first and fourth cards with same rank in its place. And permute the second cards of all ranks cyclically, and the third cards of all ranks ...


12

There are $5!=120$ possible orderings of the fencers, so we need $\log_2(120)\approx 6.9069$ bits of information. Each duel provides at most $1$ bit of information, so at least $7$ duels will be necessary. Here is a way to determine the ordering in $7$ duels. Call the fencers $A$, $B$, $C$, $D$, and $E$. First $A$ and $B$ duel, by symmetry we assume $A$ ...


12

Consider the set of binary strings that are lexicographically earlier than their reverses. For example, 011, 1011, and 11010111 are all members of this set, because 011 is earlier than 110, 1011 is earlier than 1101, and 11010111 is earlier than 11101011. We can order this set by length, followed by lexicographical order. Let the first member (01) be $c_1$, ...


11

The princess moves 1 room (never 0, never 2) each day. So does the prince. To meet, they have to be at distance 2, and move toward each other. Therefore, their distance either stays constant, increases by 2, or decreases by 2, but the oddity is unchanged, except once on day 16. If the initial distance is even (first case discussed in the solution), it will ...


11

EDITED - thanks to @Meelo for pointing out my mistake. We can do it in We place the C.Coli's at a4, a8, b2, c1, e2, g1, h3, h6. Now we prove that this is optimal. Every day there are either 1 new infected cell or 2+ new infected cells. Let us have k days with single infections and l days with 2+ infections. Then k+2l<=56 and therefore k+l<=28+k/2. ...


11

Let's get a baseline answer: Split the rods into groups of 2, test them (4). If only one group is hot, you're good. Otherwise, you have 2 groups of 2, 1 each which is radioactive. Test one of each. (2) If hot, found; otherwise the other one is hot. Edit: For a more generalized answer, I think the worst case is $2 * \log_2{N}$ Split the group in half, ...


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