Improving pizzas one pizza at the time
- Last night the new neighbour divided us over.
- Isn’t that nice. I wish I had neighbours like that!
- We played a game he had invented.
- A creative guy from what I hear.
- We started with the number one and added to it any of its divisors.
- How many does it have.
- Only one, 1 itself.
- Does he believe his game has commercial possibilities?
- When we got to 2 we repeated the process by adding any of 2′s divisors to it.
- I have read somewhere that 1 and 2 are the only divisors of 2.
- Reading can be useful at times.
- What happened then? Was that the end of it?
- No. We continued to add numbers till he asked us if all numbers below or equal to 16 can be reached in eight or less steps.
- What did you answer?
- That we had to get up early the next morning and that we really had enjoyed meeting him.
- Vuaw!
- When we got home we actually found the answer to his question. What’s more, we proved that any number not greater than 2^(n+1) can be reached in 2^n or less steps.
- Sounds like real useful stuff. I will try to add it to my pizza recipe.
Problem source: MathCamp 2009.
December 3rd, 2009 at 3:19 am
Note that you can get from:
1) 2^n to 2^(n+1) by adding 2^n
2) 2^n to 3*2^(n-1) by adding 2^(n-1)
3) k to k+1 by adding 1
Therefore, by starting with 1 and applying method 1) n times, you can reach 2^n in n steps. Further, by applying method 2), you can reach 3*2^(n-1) in n+1 steps.
Suppose 2^n <= k < 3*2^(n-1). Then k – 2^n < 2^(n-1). Start with 1, and apply method 1) n times. This reaches 2^n. Now apply method 3) k – 2^n times. This reaches k in k – 2^n + n steps. The k needing most steps in this case is 3*2^(n-1)-1, which needs 2^(n-1) + n – 1 steps.
Suppose 3*2^(n-1) <= k < 2^(n+1). Then k – 3*2^(n-1) = 1, 2^(n-1) + n <= 2^n, so this method will do.
December 3rd, 2009 at 3:32 am
Theorem: Any number less than 2^n can be reached in no more than 2n-2 steps.
Proof: Induce on n.
For n=1, this means that 1 can be reached in 0 steps, which is true: 1 is where we start.
Suppose this theorem is true for n-1, and let k be a number at least 2^(n-1) and less than 2^n.
If k is even, k=2j for some integer j<2^(n-1) which can be reached in no more than 2n-4 steps. After j, add j to get k. Thus k can be reached in no more than 2n-3 steps.
If k is odd, k=2j+1 for some integer j<2^(n-1) which can be reached in no more than 2n-4 steps. After j, add j to get 2j, then add 1, to get k. Thus k can be reached in no more than 2n-2 steps.
Thus all numbers less than 2^n can be reached in no more than 2n-2 steps, as required.
December 3rd, 2009 at 4:27 am
If I’ve calculated correctly, the smallest numbers to require 0,… steps are 1, 2, 3, 5, 7, 11, 19, 23, ….
December 3rd, 2009 at 10:31 am
I reached the same method as Richard. Without knowing how to express it in more formal terms, so my instinct was to illustrate by example.
Suppose you want to get to 13 = 1101. Build it as follows:
1 — start
10 — double
11 — add one
110 — double
1100 — no need to add one, so double again
1101 — add one, and done.
With this method, creating a number requires one step every time you add a binary digit, and one step every time you add one.
December 3rd, 2009 at 10:33 am
Though, it would be quicker if we could start from 0 instead of starting from 1.