A Math Puzzle:

Sometimes, in idle moments, I notice patterns in numbers I see, for instance phone numbers. For some reason, they especially relate to sums and differences and multiples of 9. (Is it just me, or do others do this, too?)

So, if I see a number that starts with 357, I might observe that 7+5-3 = 9. If it starts with 263, I notice that 6+3 = 9 (though I have to throw out the 2). If it starts with 442, that's obvious: 4-4 = 0. But for some 3-digit prefixes, you can't do that — UCLA's 825, for instance, can't yield a multiple of 9 no matter how you add or subtract any (nonempty) subset of the digits.

(1) What about the 4-digit suffixes? Is it the case that for any 4-digit suffix, you can find some nonempty subset (either 1, 2, 3, or 4 of the digits) such that, when the proper +s or -s are inserted, you can get a multiple of 9? My office suffix, 3926, is too easy, since 9 alone is a multiple of 9, as of course is 3+6. What about others?

(2) More generally, say that you're looking for multiples of some number N (or, if you want to make it less general, use N=29). What is the lowest number X such that for any X positive integers, it is guaranteed that some nonempty subset of those X integers will, with the proper +s and -s added, yield a multiple of N? Thus, can you be sure that for any 4 integers, some subset will with the right +s and -s yield a multiple of 29? What about for any 5 integers? For any 6 integers?

REMINDERS: (A) Only addition and subtraction will qualify. Don't tell me how you can get the result using square roots or multiplication or what have you.

(B) As one of the examples illustrates, it's OK to get to a multiple of N by getting to 0, and subtracting two equal digits if necessary.

(C) Remember that the problem isn't asking for specific sets of positive integers that can be used to get to a multiple of N. It's asking for the lowest number X such thar any set of X integers will be guaranteed to yield a multiple of N (i.e., if you take some nonempty subset of the integers, and throw in +s and -s in the right places, the result will be a multiple of N).

I've deleted the comments posted before this clarification was added.

John Armstrong (mail):
Dick and Kevan-

Your (implicit or explicit) assumptions that zero as a sum/difference is out, and that all the numbers must be used are belied by the very examples in the OP.

442 -> 4-4 = 0

Not only does this sum to zero, the 2 is dropped.
8.12.2005 1:33pm
For #2, I belive the lowest x that guarantees a result will satisfy:

N = 2^x - 1
8.12.2005 2:15pm
Tax Lawyer (mail):
Short answer: with 4 digits, you can always get it to work. My proof is very inelegant, so I will email it to Eugene, who can decide to post it if he likes. (In other words, I have an excellent proof, but it is too large to fit in these comments!)
8.12.2005 2:38pm
There is no way to generate an odd number by adding and subtracting even numbers.
8.12.2005 2:45pm
Noah Snyder (mail):
x > log_2(N) will work.

During the proof we will be using "modular arithmetic" which means that we don't care about the numbers themselves, but only their remainders modulo N. Rephrasing your question in this language: You have x numbers modulo N and you want to show that there is a subset whose sum/difference is 0 modulo N.

Consider a subset S and let sum(S) be the sum of the elements of S. There are 2^x different subsets. Thus, since 2^x > N we know that for two different sets S_1 and S_2 we have that sum(S_1) = sum(S_2) (this argument is called the "pidgeon hole principle"). Now we take the *difference of S_1 and S_2.* To be more exact, if an element is in S_1 but not S_2 it gets a + sign, if it is in both we ignore it, and if it is in just S_2 we get a minus sign. Clearly this difference is sum(S_1)-sum(S_2) = 0.
8.12.2005 3:07pm
Noah Snyder (mail):
Incidentally that means that for N=29 we have that X=5 works and that for N=9 we have that X=4 works. X=4 would also work up to N=15 if you're ever bored with 9 and want to start using 15.
8.12.2005 3:12pm
Eugene Volokh (www):
Noah is essentially right. To make the proof complete, you also need to prove that for X <= log_2(N), one can always come up with a set of numbers for which no nonempty subset yields a multiple of N.

But here one can just point to one such set -- the powers of 2 from 1 to 2^X(-1): 1, 2, 4 would work for 9, 1, 2, 4, 8 for 29, and so on. No nonempty subset of these would simply add to a multiple of N, since such sums would range from 1 to 2^X-1 (all of them added together).

Nor can you get to 0 by adding some of the powers of 2 and subtracting other powers. If you could add to 0 by, say, something like 0 = the sum of some different powers of 2 - the sum of other different powers of 2, then that means that two sums of different powers of 2 would yield the same number. And that's impossible, since each integer has only one binary representation.
8.12.2005 3:15pm
Tax Lawyer (mail):
Sweet proof, Noah Snyder. Now I feel not only like a nerd for thinking about it as long as I did, but also an incompentent nerd, for the hideous mess that is the "proof" I came up with for n=9, x=4!
8.12.2005 3:15pm
Noah Snyder (mail):
That example is quite cute. I was trying to come up with an example to show that the bound was tight, but hadn't had the binary numbers "aha!" yet. I was on 1,2,4, when I refereshed.

To be fair, Tax Lawyer, mathematics is my fulltime job. I'd hate to see my attempt at a answering a tax law question.
8.12.2005 3:21pm
Daryl Herbert (www):
relevant to QUESTIONS 2 &1:

If you are looking for multiples of X:

there are 3^N - 1 possibile (though not necessarily unique) sums for a number of N digits according to your rules (because every digit can be positive, negative, or zero, but we must exclude the one possibility where all digits are zero).

It is possible for a computer to iterate through all of them, in some order, and get the sum. Then the computer would check if (sum % X == 0), and if so, it's a match.

So a computer could iterate through enough of them until you could be reasonably sure that every number above Y would always yield some combination of digits such that the sum would be equal to a multiple of X.

That's not the same as a proof, of course :-)

For further clarification: would the number 206 be considered valid? (1)*0 + (0)*2 + (0)*6 would yield zero, which is a multiple of 9. In that case, all numbers with 0 as a digit would always satisfy your requirements.

To take your requirements a step further, instead of demanding the sums match the formula (sum % X == 0) you could invent any formula. For instance, you could look for all digits that could be summed as a multiple of nine plus two, in which case you could use the formula (sum % X) == 2, or even use more complicated formulae.


The fact that you allow zero to count as a multiple of X makes it much easier to prove that all numbers with Y digits will always contain a multiple:

If a number contains a single zero or 2 of the same digit, then it can evaluate to zero (which is a multiple).

So no matter what, no number of length greater than nine digits can ever fail your test (and it's actually smaller than that, because it can't contain any triples of the form (a, b, a+b) like (1, 2, 3) because those are easy to evaluate to zero. So there is definitely an upper bound.


Solution to QUESTION 1:

With the number 9, it's even easier to pigeonhole:
the number cannot contain a 9 (just like it can't contain zeroes) which means you are limited to 8 digits. Also, there are four pairs of numbers that cause each other to fail:
1 and 8, 2 and 7, 3 and 6, 4 and 5. So you can only have 1 of each pair. Which means you can have 4 digits max.


We can take this a step further:

All 4-digit numbers that could satisfy your test must contain either 1 or 8. 8 is actually _equivalent_ to 1 in that +1 has the same effect as -8 (N+1%9)==(N-8%9)

A similar effect occurs for all other pairs because (N+a%9)==(N-(9-a)%9)

If you include values from the 2nd and 3rd pairs (four ways to do this, (23,26,37,67), that is the equivalent of adding 2 and 3 (because a 6 has the same effect as a 3 and a 7 has the same effect as a 2).

But you can't have 123, because 1 + 2 - 3 evaluates to zero.

I mean that 876 is equivalent to 123 because -8 -7 + 6 evalutes to -9 (you switch the +s to -s and the -s to +s)

Therefore there are NO combinations of four digits such that a multiple of nine cannot be reached.

8.12.2005 3:29pm
Daryl Herbert (www):
Now that I've solved Question 1, back to Question 2:

I think the easiest trick is to continue to focus on how to get to zero.

First, we establish that the number cannot contain a zero. Then we establish that it can't contain a duplicate of the same value (because a-a == 0 which is a multiple of anything)

So we are left with a number of up to 9 digits max, all digits unique (and order doesn't matter).

Therefore we can represent these numbers as a binary string of length 9 (where a 1 signifies the presence of that digit and a 0 signifies that it is missing).

So we know already that there are fewer than 2^9 possible combinations of digits that can NEVER evaluate to zero.

We've only limited it so far by removing sets of length 1 that evaluate to zero (i.e.: "0" as a digit) and sets of length 2 that evaluate to zero (i.e.: duplicate digits, because a-a=0)

So now we have to remove combinations of digits that contain sets of 3 digits that together can evaluate to zero, sets of 4 digits, sets of 5, etc.

No number can contain a combination of digits that evaluates equal to some other combination of digits (because one subtracting the other yields zero).

this means if it contains a 1, no other digits can have a distance of 1 from each other, which brings you down to 5 digits max (12468 or 13579), except that both of those 5-digit combinations can evaluate to zero (2-4-6+8 and 3-5-7+9), so you are left with 4-digit combos, at best, if you include a 1.

We can safely ignore all numbers that include 1 as a digit (because those can never reach more than 4 digits, which means at most a ceiling of 9751, which is low enough to be boring)
8.12.2005 3:53pm
Daryl Herbert (www):
If it doesn't contain a 1, then it has 8 digits max (because there are only 8 unique digits left to choose from, 23456789). So we've already proven that all 9-digit combinations yield a sum of zero.

Now we can look at whether or not to include 2 as a digit: if 2 is included, no other numbers can have a distance of 2 (because then you'd have 2,a,a+2 and 2+a-(a+2)=0)

This means that 9 blocks 7, 8 blocks 6, 7 blocks 59, 6 blocks 48, 5 blocks 37, 4 blocks 6, and 3 blocks 5.

Here is an iteration of all possibilities of length 4 or greater: (done in my head, not by computer; I left out the small ones of length < 3 because )

2347 (fails because 3+4-7=0
23478 (fails because 3+4-7=0)
23489 (fails because 2-3-8+9=0)
2349 (fails because 2+3+4-9=0)
2367 (fails because 2-3-6+7=0)
2369 (fails because 3+6-9=0)
2378 (fails because 2-3-7+8=0)
2389 (fails because 2-3-8+9=0)
24589 (fails because 4+5-9=0)
2459 (fails because 4+5-9=0)
2569 (fails because 2-5-6+9=0)

successful combinations:
2348, 2458, 2478, 2489, and 2589
The largest of these is the number 9852, which will serve as the ceiling for numbers containing the digit "2". Again, these can never reach five digits successfully, so that is our ceiling.
8.12.2005 4:08pm
Daryl Herbert (www):
If it doesn't contain a 0, 1 or 2, and no duplicate digits, then we're left with some subset of 3456789

If it contains a 3:

Then it can't contain any pair of digits that has a distance of 3:
4 excludes 7, 5 excludes 8, 6 excludes 9, 7 excludes 4, 8 excludes 5, and 9 excludes 6.
We can pair them up as follows (47, 58, 69)
We know that we can only contain 1 number from each pair (because 3 and that pair can be summed to zero)

This means that, at most, a number containing 3 (but not 1 or 2) can only have 4 digits max, or it will capable of summing to zero.

The largest of these is 9873, which does not sum to zero, so that will be our ceiling for numbers containing 3 but not 2 or 1. (I should have said in my last comment that it's scope was for numbers containing 2 but not 1)
8.12.2005 4:17pm
Daryl Herbert (www):
Thus far, I've shown that any number of 5 digits or more containing 0, 1, 2, 3, or a duplicate digit can evaluate to zero.

We are left with 456789 as possible digits to choose from.

We can't have two pairs that are both 1 apart (45, 56, 67, 78, and 89). We could represent these two pairs as (a,a+1,b,b+1) and they can be made equal to zero with a-(a+1)-b+b+1.

We can have zero or _one_ such pair, but not two. If we have zero pairs, that leaves us with 468, 469, or 579. Those are very low, so we don't care about them. The only way to get a high ceiling will be to include exactly one pair of consecutive numbers.

That pair can be: 45, 56, 67, 78, or 89

The following is an iteration of all possible values of three or more digits meeting those criteria:

459 (fails because 4+5-9=0)
4579 (fails because 4+5-9=0)





The highest of those is 9864.


Thus there is no combination of 5 or more digits that can't be turned into a zero using your formula (thus all combinations of 5 digits can be divisible by X, by way of zero)

Cheers again

Sorry if these proofs are very long, but I'm not a mathematician. I figure that you started a thread asking for proofs, so you get what you ask for :-)
8.12.2005 4:39pm
Daryl Herbert (www):
Also: I apologize for misusing the term "sums to" to mean "using Eugene's special formula, evaluates to"

I'm obviously not an expert at this sort of thing.
8.12.2005 4:41pm
John Armstrong (mail):
Noah's got it on the nose. IANAL, but I am a mathematician.
8.12.2005 5:53pm
Fred K:

825 when "spelled out" on a telephone keyboard is UCL(A)
8.12.2005 5:56pm
Daryl Herbert (www):
It's my computer programming background that makes my solution so ugly compared to the mathematicians'...

Also, I think I found a mistake in my last proof post.

While a number cannot have 2 separate consecutive pairs, one could have 3 consecutive numbers (789, for instance).

So I have to include those as a possibility:

All are 4 digits in length, so my conclusion stands (that the highest possible number that can evaluate to zero is 4 digits), but the highest possible ceiling value is 9875, not 9864. Sorry.
8.12.2005 6:29pm
Tim Converse (mail) (www):
Here's an interesting related problem.
8.13.2005 4:38pm
Victor Davis (mail) (www):
Let Z be a 5 digit number that satisfies Eugene's addition/subtraction requirements (hereafter referred to as the "Eugene property"). I will here prove that there exists a subset of those 5 digits that can always add to zero (which is trivially a multiple of any number).

* All digits must be unique. We must eliminate *exactly* 4 of the first 9 integers to form Z.

Proof by contradiction. Assume Z exists.

a) Assume Z contains the digit "1". None of the remaining 4 digits can be consecutive. => (1,3,5,7,9) is the only remaining possibility. This violates the "Eugene property". Therefore, Z does not use the digit "1".

b) Assume Z contains the digit "2". Any omitted digit must be either paired with a consecutive omitted digit or located at the end. I.e., if you eliminate 4, you must also eliminate 3 or 5 or else the remaining digits can be added to the digit 2 to obtain a zero. Because we also know the number cannot contain the digit 1, we are left with an impossibility. (2,3,6,7) is the closest we can come, and that's ony a 4-digit number, and even those numbers don't fulfill the "eugene property").

c) Assume Z contains the digit "3". Because we have eliminated "1" and "2" already, we must eliminate exactly 2 additional digits, choosing between (4,5,6,7,8,9). Notice, however, that there are three pairs of digits separated by exactly "3". We must eliminate one of the digits in each of those pairs, but we only have two additional digits available to eliminate! Therefore, "3" cannot be a digit in Z.

d) Assume Z contains the digit "4". We must eliminate ONE of (5,6,7,8,9). Notice that we must eliminate 5 or 9, since the difference between those digits is 4. If we eliminate 5, the remaining digits (4,6,7,8,9) violate the Eugene property (4+6+7=8+9). If we eliminate 9, the remaining digits (4,5,6,7,8) also violate the Eugene property for basically the same reason: the first three digits equal the sum of the last two.

e) We know we must eliminate the digits 1-4. Therefore, we have found Z. It must be composed of (5,6,7,8,9). However, notice that this number violates the Eugene property as well! (5+8=7+6 or 5+9=8+6, etc.)

Therefore, Z cannot exist, because any construction of Z is impossible. Therefore, any 5 digit number must have a subset of numbers that can be added or subtracted together to equal zero. QED.

Notice also that Eugene has solved X=4: (1,2,4,8) is a combo that doesn't equal zero.

I desperately have to go, and hope I didn't misunderstand anything. Neat problem, and if I have erred in any way, I do apologize. I know this message is long and the proof is still not entirely elegant.
8.14.2005 2:07pm
8.16.2005 3:01pm