The Volokh Conspiracy - 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.

	[Eugene Volokh, August 12, 2005 at 11:36am] Trackbacks 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.