# The Magic Stick

Here's a relatively easy puzzle that's actually entirely my own creation.

An old guru in an Asian monastery is showing his beloved student his gallery of items that he has either collected or kept from previous generations.

One item that he is particularly fond of is an odd-looking walking stick. He shows it to his student, waving his hands over the evenly spaced notches in the stick. His student understands without talking that the stick served two purposes – as a walking stick and as a measuring device.

He then proceeds to pop the handle off the stick. The student almost gasps but utters no sound. The guru continues to break the stick into pieces, while the student watches in silent horror at how inconsiderate the guru is being of an old relic.

The student regains his calm, though, after noticing that the guru has not destroyed the stick after all, but is snapping pieces of the stick back together again, rearranging them into two smaller sticks. He then lines the two sticks on the ground, and the student sees that one piece is one notch longer than the other.

He then proceeds to break the sticks into pieces again. The student watches curiously as he then rearranges the pieces into three sticks, each of them one notch longer than the next. The guru continues to do this for five sticks and seven sticks, and in each of the arrangements, each stick is one notch longer than the next.

Finally, the guru snaps off all the pieces that he had been using to make the smaller sticks, and lines them up individually. The student knows what to expect. Each individual piece, ten of them in total, is one notch longer than the next.

How long is this stick, in notches?

• Please confirm but I think from your insistance that there is only one solution that there are only 9 breaks in the magic stick. So far at least 3 people including myself thought that the stick was made up of many more than 9 breaks. – kaine May 30 '14 at 17:47
• I see it in the question already: "Each individual piece, ten of them in total" (emphasis added) – Xynariz May 30 '14 at 17:57
• Yes, there are only nine breaks in the stick, that make up a total of ten pieces. – Joe Z. May 30 '14 at 18:11
• Not every notch is a break. – Joe Z. May 30 '14 at 18:22
• @JoeZ. Aha. That makes sense now, though I didn't find it obvious upon the first few readings of the puzzle. You might consider an edit to clarify (or maybe I'm just slow ;)) – WendiKidd May 31 '14 at 0:10

### Part 1

Xynariz's answer seems to be correct. We can note all the infinite solutions if the stick has more than 10 breaks as follows: $$5(2j+9)=3*5*7*k \quad \text{for some integers $$j$$ and $$k$$}$$

If $j = 21x+6$ and $k=2x+1$ for any integer $x$, then these equations are true.

This means the number of sticks is

$210x+105$ for any integer $x$. This number is odd and divisible by 3,5, and 7. Also if you subtract 45, the answer is divisible by 10.

### Part 2

If there are only 9 breaks, each stick is $L+s$ long where $s$ is the stick number $0,1,2,3...$ while L is $21x+6$.

If we try to make 3 sticks out of the 10 parts, the minimum length of the stick that contains 4 parts (as 10 is not divisible by 3) is $(21x+6)*4+0+1+2+3=84x+30$. The largest stick that can be made out of 3 small sticks is $(21x+6)*3+9+8+7 = 63x+42$. The smalles difference between the 4 and 3 stick lengths is $21x-12$ while the guru's game requires at least one combination that differ in length by no more than $1$. As the 4-stick is more than $1$ greater than the 3-stick for any $x>0$, the only solution is $x=0$. This means that the only solution is

$105$.

• You can prove that any other multiple of $105$ won't work, however. – Joe Z. May 30 '14 at 16:47
• Which quality won't let it work? – kaine May 30 '14 at 16:48
• That's for you to figure out. :) – Joe Z. May 30 '14 at 16:48
• @JoeZ Do you mean that there are only 10 breaks in the entire stick? I did not understand that. – kaine May 30 '14 at 17:02
• Took me about 5 tries through to understand your logic, but I finally did. I do believe you've proved conclusively that there is only one answer. – Xynariz May 30 '14 at 18:01

Here's my answer for the smallest possible solution, in number of notches:

$105$.

Here's my logic (slightly mathematical, mostly intuitive).

The first case (splitting into $2$ sticks) is easy - any odd number satisfies that: $n + (n+1) = 2n+1$, which will always be odd.
The second, third, and fourth cases (splitting into $3$, $5$, and $7$ sticks) are more interesting. Consider the case of $3$ sticks. You have sticks of length $n$, $n+1$, and $n+2$. If you took one off of the $n+2$ stick, and put it on the $n$ stick, you have $3 \times (n+1)$, which means the final number has to be a multiple of $3$. By similar logic, you can conclude that the number is also a multiple of $5$ and $7$.
The final case was a bit more difficult, until I realized that $n + (n+1) + (n+2) + \dots + (n+9) = 5 * (2n+9)$. I took the simplest case possible for the first for clues ($3 \times 5 \times 7 = 105$), and did some simple algebra to reduce to $n = 6$.

Here is a breakdown of the length (in notches) of each stick, and how they can be combined as needed:

First case: $52 = 15+14+13+10$ and $53 = 12+11+9+8+7+6$.
Second case: $34 = 15+13+6$, $35 = 14+12+9$, and $36 = 11+10+8+7$.
Third case: $19 = 13+6$, $20 = 12+8$, $21 = 11+10$, $22 = 15+7$, and $23 = 14+9$.
Fourth case: $12,13,14,15$, $16=10+6$, $17=8+9$, $18=7+11$
Fifth case (trivially): $6,7,8,9,10,11,12,13,14,15$

Kaine's answer does prove that this is indeed the only solution.

• There is a proof that your answer is the only solution (although not the only way to assemble the smaller pieces). If nobody gets it in a few days, I'll put that up myself. – Joe Z. May 30 '14 at 16:35
• You also haven't done the seven-stick case yet. – Joe Z. May 30 '14 at 18:11

Well we can easily rephrase the question as follows (the subtractor being $k + (k - 1) / 2$ obviously for $\bmod k$): \begin{align} (n - 1) \equiv 0 & \mod 2 \\ (n - 3) \equiv 0 & \mod 3 \\ (n - 10) \equiv 0 & \mod 5 \\ (n - 21) \equiv 0 & \mod 7 \\ (n - 45) \equiv 0 & \mod 10 \\ \end{align}

Using congruence math we can prettify this:

\begin{align} n \equiv 1 & \mod 2 \\ n \equiv 0 & \mod 3 \\ n \equiv 0 & \mod 5 \\ n \equiv 0 & \mod 7 \\ n \equiv 5 & \mod 10 \\ \end{align}

So the number has to be divisible by $3$, $5$, $7$ which gives us as the minimum

$105$, which also fulfills the other two requirements.

So is there really only one solution as claimed? Easy to disprove: $n \equiv 1 \mod 2$ is guaranteed if $n \equiv 5 \mod 10$ is fulfilled (I'm sure that's obvious although we could prove it with the CRT). So we just have to check when $105 n \equiv 5 \mod 10$ or rather $5n \equiv 5 \mod 10$ is true. Which is for all odd values of $n$.

Hence the correct solution is

$\forall k \in \mathbb{N}, 105 (2k+1)$, i.e. $105, 315, 525, \dots$

• I thought the same thing but the point of the question is that there are only 10 smaller sticks out of which to make the 2,3,5,7, and 10 cases. – kaine May 30 '14 at 17:43
• The key phrase is "lines them up individually" – Bobson May 30 '14 at 17:45
• Either that, or "Each individual piece, ten of them in total" – Xynariz May 30 '14 at 18:04
• Ah I see missed that part, yep that may change things. – Voo May 30 '14 at 18:27