The Stack Overflow podcast is back! Listen to an interview with our new CEO.

# Tag Info

## Hot answers tagged reachability

35

One possible algorithm has just three state data: Integers $k$ and $n$, and a Boolean $f$. Start in any room, with $k = 0$, $n=0$, and $f$ true. (The meaning of $f$ is "I am currently moving in the 'forward' direction". The meaning of $k$ will be a forward room number.) Turn on the light in that first room. Then: If $f$ is false and $k=0$ and the light ...

30

Professor Halfbrain's theorem is Proof

28

Answer: Argument: ============ ============ ============

27

First choose $2014$ and $2016$. Average = $2015$. Now take the $2015$s. Their average is $2015$. Now choose $2015$ and $2013$. Average = $2014$. Choose $2014$ and $2012$. Average = $2013$. Note that we can keep on continuing this approach and end up with a situation like $1$, $2$ and $4$ in the end. From here, choose $2$ and $4$. Average = $3$. ...

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

Four is cosmic because: And it should probably go: 18 --> 8 --> 5 --> 4 (from Doge's comment)

23

Professor Erasmus If the leftmost six numbers are $110\,010$, then the first step removes $110$ from the left and adds $11$ on the right, and the next step removes $010$ from the left and adds $0010$ on the right. The result is that after two steps, $110\,010$ has been removed from the left and added on the right. Similarly, if the leftmost twelve numbers ...

22

I will give you a hint rather than an answer (because I think you will enjoy this more by solving it yourself): I would encourage others not to post an outright solution, at least for a few days; aside from anything else, this will give idknuttin the satisfaction of answering his own question when he figures it out :-).

20

Parity If you remove any two even numbers, their difference will also be an even number. The total number of odd numbers will remain the same. If you remove any two odd numbers, their difference will be an even number. The total number of odd numbers will decrease by two. If you remove an even and an odd number, their difference will be an odd number. ...

19

It is Consider the remainder of the number when divided by $13$. Initially we start with remainder $3$ ($81\equiv 3 \mod 13$), we have to get remainder $4$ ($82\equiv 4 \mod 13$). Applying step 1, assuming that $m\equiv 3\mod 13$, we get: \begin{align} m &\to m^k \\ 3 &\to 3^1, 3^2, 3^3, \ldots \mod 13 \\ 3 &\to 3, 9, 1, 3, \ldots \mod 13 \... 19 The answer is I imagine the line of reasoning the author wants is as follows: 18 Spoiler: Let's choose a set of sticks to prove this: 18 Building on @2012rcampion's answer, here's a simple constructive proof that any even number is reachable. Take the (even) number that you want to reach (say n) and put it aside. Then take the difference between all the pairs (500,499), (498,497),\ldots,(n+2,n+1), and (n-1,n-2),(n-3,n-4),\ldots,(3,2). That will give you an odd number of 1's. You'... 18 Edit: A lot of credit is due to @ffao for devising a better way to deal with the case where there is just one room and reducing the solution by one. (Subsequently, @Lawrence has managed to do even better in their answer). I now think it can be done with Strategy If we are allowed to assume that there is more than one room, then it can be done with ... 17 This answer is entirely due to Henning Makholm. If we draw a grid in such a way that the four fleas are at positions (0,0), (0,1),(1,0) and (1,1), then the fleas will forever be at integer points on the grid. Color the lattice points red, blue, green and purple by repeating the pattern The key observation is that a flea will always hop to the same ... 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 ... 15 N=5 This builds on @ffao's on-on pattern and is a slight optimisation over @hexomino's 7-step 6-step solution. I'm assuming that in a 1-room scenario, stepping out of that room will lead to the corridor, and walking around the corridor in either direction consistently will lead back to the same room. Here's a summary of the strategy: You have no ... 15 Task 1 was answered. Task 2: 14 2048 Proof Each move changes the number of black numbers remaining by 0 or 2, and thus cannot change the parity. Thus initial states with an even number of black numbers can never be brought to the desired state. Now we claim that every initial state with an odd number of black numbers can be brought to the required state. By repeatedly using the moves RBR ... 14 Here's one answer that I think would be shortest: 14 N = 2 By referencing the wall colors, you should be able to deduce which direction you were going (CW/CCW or R/L) when entering your current room. I used that assumption to come up with a state machine that should be able to accomplish the task with just two states. Looking at the other answers, my solution does use the "double sentinel" method, although I ... 13 The GCD of 300 and 132 is 12. So the quantity you can take out is always a multiple of 12. In theory we can take out at most 83\cdot 12=996, leaving four in the bank. Every day make sure you deposit exactly nine times and withdraw exactly 4 times. This is possible as long as you have 16 or more dollars in the bank. After this we end up having ... 13 Answer The (maybe) interesting details The ugly details 13 Label the tiles like chessboard notation, so that the bottom left is a1 and the top right is j10. Moves will be denoted by referring to a pair of opposite corners in the square being flipped. This guarantees that it is always possible to get down to black squares. To prove that it is not always possible to reduce the number of black squares further: 12 Answer: Explanation: 12 Obviously we're never going to get an irrational number. So any number we get can be expressed as \frac{p}{q}, where p and q are relatively prime integers (q can be 1, if the number is an integer). When we have \frac{p}{q}, we can write \frac{2p+q}{q} and \frac{p}{p+2q}. If p and q are both odd, 2p+q and p+2q are also odd, so any ... 12 Reasoning: After this we... ...going all the way back to... 11 Professor Halfbrain For integer a, b\geq 0, let T_{a,b} denote the right triangle with side lengths \frac{3^{a+1} 4^b}{5^{a+b-1}},\;\;\;\frac{3^a 4^{b+1}}{5^{a+b-1}}\;\;\;\frac{3^a 4^b}{5^{a+b-2}}.  Cutting triangle $T_{a,b}$ results in the triangles $T_{a+1,b}$ and $T_{a,b+1}$. The initial triangles are two copies each of $T_{1,0}$, $T_{0,1}$, ...

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