My family just had the pleasure of a visit from a friend I have known since first grade. Ever since we were kids, my friend and I would try to stump each other with math/logic problems we had heard about (or sometimes, invented ourselves). We went back and forth today, and these two were deemed the most fun — give them a shot if you haven’t heard them before. Answers after the jump.
His best to stump me:
Many numbers are the sum of consecutive digits, for example 29 is equal to 14+15 and 66 is equal to 21 + 22 + 23. Between 100 and 200, there is only one number that is NOT the sum of consecutive digits. What is it?
My best to stump him:
You are in the basement of a house and on the wall are three identical-looking light switches. Two of them are broken and one of them works, but the light that the working switch turns on is in the attic. If you could only make one trip to the attic, how would you determine which of the three switches is the one that works?
Answer to his best stumper:
The easiest way to figure this out is to try it with low numbers and work out which ones aren’t expressable as the sum of consecutive digits. You will see a pattern right away: 2, 4, 8, 16 etc. The only number following that pattern in the specified range is 128 (2 to the power of 7). My friend pointed out that there are many variants of the problem, one could just as easily make the range 200 to 400 (answer = 256), 500 to 1000 (answer = 512) etc.
Answer to my best stumper:
The trick here is to find another data point besides light to tell which switch turns on the bulb, and it’s warmth. Here’s how: Turn on switch number 1 for ten minutes and then turn it off, immediately turning on switch #2. Then go upstairs to the attic. If the bulb is warm but the light is off, switch #1 is the working one. If the light is on, switch #2 is the working one. And if the light is off and cold, switch #3 is the one that works.
I have not cheated (as I generally prefer to do) and peeked at the answers. The way to figure out the light switches is to go up to the attic and have your friend flip them. Works every time.
Or shout to your neighbor mowing his lawn, "hey, is my attic light on?". Or do it at night, and peek out your cellar window to see if there's any illumination on in the yard.
My method is superior to yours because it does not presuppose a light in the attic. So there! As for the rest of you, "blah, blah, number, blah, blah number."
Well played, Maestro. Except that when your friend flips the switches, how will you tell which one works, unless there's a light in the attic?
Ohhhhh, I shouldn't get snarky when I'm tired. I meant a window, D'ho. Props to you.
The first problem assumes that negative numbers are not allowed. Otherwise, you have -127 + -126 + -125 + … + 125 + 127 + 127 + 128 = 128.
A better phrasing would be "Many numbers are the sum of consecutive positive integers" or "Many numbers are the sum of consecutive counting numbers". I'd even go for "Most numbers", but that's a matter of taste.
You were really testing to see if anyone would notice that your broken switch method probably fails if the light is a normal LED, rather than an old-fashioned incandescent. What is my prize?
Here is a more rigorous solution to the first problem.
The minimum sum of A consecutive digits is
1 + 2 + … + A
This sum can be calculated as follows: A * (A+1) / 2
If we add the value B to each digit, the resulting sum is: A * (A+1) / 2 + B * A
So a more formal definition of the condition "N is the sum of consecutive digits" is:
There exists a solution the integer equation
N = A * (A+1) / 2 + B * A
such that A >= 2 and B >= 0.
Note that if A is odd, then (A+1) will be even, allowing us to calculate (A+1)/2 using integer arithmetic, and we can rewrite the above condition as:
N = ((A+1)/2 + B) * A
So if A is odd, then N must be a multiple of A.
Similarly, if A is even, then A/2 is an integer and we can rewrite as:
N = (A/2 + B) * A + A/2
So if A is even, then N must be a multiple of A/2, and not a multiple of A.
If N is a power of 2, then there is no solution for A and B. First, there can be no solution where A is odd, because A must be >= 2 and no multiple of an odd number greater than 2 is a power of 2.
Second, there can be no solution where A is even. The only possible A such than N is a multiple of A/2 but not a multiple of A is A = N*2. Setting A = N*2 and solving for B gives
B = -N
which is not a valid solution because we require B >= 0.
Now consider the case where N is positive and not a power of 2.
Let P be the product of all odd prime factors of N.
Let Q = N/P * 2
Then we can express N as:
N = P * Q/2
If P < Q, let A = P.
We know that P is odd because it was constructed by multiplying one or more odd prime numbers together. Solving for B gives:
B = Q/2 - (P+1)/2
Since Q > P, Q >= (P+1) and B >= 0
Q is even, so Q/2 is an integer.
P is odd, so (P+1)/2 is an integer.
That means that B is an integer.
Therefore A = P and B = Q/2 - (P+1)/2 is a valid solution.
Alternatively, if Q < P, let A = Q. Solving for B gives:
B = (P - (Q + 1))/2
Since P > Q, P >= (Q+1) and B >= 0
P and (Q + 1) are both odd, so the difference is even and B is an integer.
Therefore A = Q and B = (P-(Q+1))/2 is a valid solution.
We can rule out the final alternative, Q = P, because Q is even and P is odd.
In summary, for positive N, there is a solution if and only if N is not a power of 2.
MOST impressive!
Quick clarification: "Let P be the product of all odd prime factors of N." What I really mean here is: start with N and repeatedly divide by 2 until you get an odd number. Set P to the result.
I think there's a faster solution if you take the sums "around the middle" (though google says there's lots out there). An odd number of terms around x gives
(x-n) + (x-n+1) + … + (x-1) + x + (x+1) + … + (x+n) = (2n+1)x,
because there are 2n+1 terms and everything else cancels. For an even number of terms, we subtract the first term, x-n:
(x-n+1) + … + (x+n) = 2n x + n = n(2x+1).
As you observed, we need to assume we have more than one term (n > 0) and all terms are strictly positive (in the former case, n < x, and in the latter case, n-1 < x). In either case, x > 0.
We already see having an odd factor is necessary to be a sum of consecutive integers; it's sufficient because if N = (2p+1)q we can just use the former (odd # of terms) if p < q and the latter if q-1 < p.
So N is not expressible as the sum of consecutive positive integers iff N has no odd factors iff N = 2^k.
I'm sure I'm not the first to note this, and again Google turns up much deeper stuff. Cheers.
Got the second one.
First one I did by brute force … it is easy to get all the consecutive sums into a spreadsheet … start with (1+2), then increment each by 1, and it is obvious all odd numbers will be the sum of consecutive digits. Continue for 1 2 3, 1 2 3 4 etc until you have all the numbers up to 200 … it took 19 columns and 100 rows. Eliminate numbers less that 100 and greater than 200, and you are left with ~240 numbers with a lot of duplicates … after that a visual search or something more fancy will turn up candidate numbers.
It works but an error in my spreadsheet prevented me getting the right answer! Sad 🙁 Thanks for the challenge!
One could write a program that could take any number and (a) say if it was the sum of consecutive numbers, and (b) if it was, give them all.