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.

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.

N = 2^x - 1

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.

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

addto 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.

To be fair, Tax Lawyer, mathematics is my fulltime job. I'd hate to see my attempt at a answering a tax law question.

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.

Cheers,

Daryl

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)

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)

2348

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)

2458

24589 (fails because 4+5-9=0)

2459 (fails because 4+5-9=0)

2478

2489

2569 (fails because 2-5-6+9=0)

2589

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.

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)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:

457

458

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

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

568

569

467

4679

679

478

578

489

4689

689

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 :-)

I'm obviously not an expert at this sort of thing.

ama mathematician.825 when "spelled out" on a telephone keyboard is UCL(A)

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:

4568456956794

6784

7895

789All 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.

* 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.