Proving the Divisibility of Sum of Digits in Consecutive Natural Numbers by 11

[Ebn_Alnafees]

Problem 1
Prove that among any 39 consecutive natural numbers
it is always possible to find one whose sum of digits
is divisible by 11.

Problem 2
Sets of 4 positive numbers are made out of each other according
to the following rule: (a, b, c, d) (ab, bc, cd, da).
Prove that in this (infinite) sequence (a, b, c, d) will
never appear again, except when a = b = c = d = 1.

Problem 3
Take a series of the numbers 1 and (-1) with a length
of 2k (k is natural). The next set is made by multiplying
each number by the next one; the last is multiplied by the
first. Prove that eventually the set will contain only ones.


Problem 4
What is the largest x for which
427 + 41000 + 4x
equals the square of a whole number?

Problem 5
Prove that for any prime number p > 2 the numerator m of the fraction
http://
is divisible by p.

 

[arildno]

What have you done so far?

 

[AKG]

1. Take the first number whose unit digit is 0. This number will be anywhere from your first number to your tenth. So you'll have at least 29 numbers above it to work with. Let's call this number x, and say [the sum of its digits] is congruent to a (mod 11). If a is zero, then you're done, otherwise note that x + 20 - a is in your set of numbers and the [sum of its digits] is divisible by 11.

[Actually, this doesn't always work. It works when adding 20 - a to x does not change the hundreds or thousands, etc. digit, e.g. if you have 40, then add 20 - a = 20 - 4 = 16, and you get 56 and 5 + 6 = 11. On the other hand, if you have 90, then adding 11 gives 101, and 1 + 0 + 1 = 2. However, you can build off of this idea to show that what you need is true in general.]

2. Have you even tried this?

3. Suppose x is some string of 1's and -1's. Define p(x) to be the "push-up" of x, all of the elements of x pushed up one spot (the first one being pushed to the end). If we define the mulitplication of two strings, x and y, to simply be their pointwise product, then if x occurs in our sequence, the next term will be p(x)x. Next would be [p(p(x)x)][p(x)x] = [p²(x)p(x)][p(x)x] = p²(x)[p(x)]²x, etc (note that p is multiplicative, i.e. p(xy) = p(x)p(y). Suppose there is some x which appears twice in our sequence. First, if there is no such x, then this sequence must eventually go through all 2^2k possible strings, and so it must eventually hit (1,1,1,1,...,1). Otherwise, if there is some x that repeats, then we will have that for some n:

pⁿ(x)[p^n-1(x)]²[p^n-2(x)]²...[p²(x)]²[p¹(x)]²x = x, which gives:

pⁿ(x)[p^n-1(x)]²[p^n-2(x)]²...[p²(x)]²[p¹(x)]² = (1,1,1,...,1)

But the square of any string is clearly (1,1,1,1,...,1), so we simply get:

pⁿ(x) = (1,1,1,...,1)

Well this just means that x = (1,1,1,1,...,1) so our identity element does indeed occur in any sequence.

 

[AKG]

Is question 4 a trick question?

What is the largest x for which
427 + 41000 + 4x
equals the square of a whole number?

Observe that (assuming x is an integer):

427 + 41000 + 4x = 427 (mod 4) = 27 (mod 4) = 3 (mod 4)

No square is congruent to 3 (mod 4). Any square can be expressed in the form (4k + a)² where a is in {0, 1, 2, 3}. Note that 0² = 0 (mod 4), 1² = 1 (mod 4), 2² = 4 = 0 (mod 4), and 3² = 9 = 1 (mod 4). So x is not an integer. The question doesn't state specifically that x must be one, but these type of questions normally ask for integer solutions. On the other hand, if non-integer solutions are permitted, then the question still has no answer. Let N be arbitrarily large. Then:

(N² - 41427)/4 = x

is clearly a real number (not an integer), so there is no maximum value for x that satisfies the given condition. I suspect you posted the problem incorrectly.

 

[Muzza]

1. Take the first number whose unit digit is 0. This number will be anywhere from your first number to your tenth. So you'll have at least 29 numbers above it to work with. Let's call this number x, and say it is congruent to a (mod 11). If a is zero, then you're done, otherwise note that x + 20 - a is in your set of numbers and is divisible by 11.

I don't get it. Just because a number is divisible by 11 doesn't mean that the sum of its digits is divisible by 11 (counterexample: 11).

Problem 5 can be done by considering n(p - 1)!(1 + 1/2 + ... + 1/(p - 1)) modulo p.

 

[AKG]

Sorry, I meant "say the sum of its digits is congruent to a (mod 11)." Edited.

 

[Hurkyl]

Have you guys just done all of his homework for him?

 

[AKG]

Actually, this way works better:

Any consecutive 39 numbers must contain at least 20 in the same hundred, i.e. they would all be the same except the last two digits. You are further guaranteed that within a given hundred, you will be able to find 20 consecutive numbers that have last digits going from x0 to (x+1)9 for some x in {0, 1, ..., 8}. So you know that you have last two digits of the following forms:

x 0
x 1
.
.
.
x 9
(x+1) 9

whose sums are:

x, x+1, ..., x + 9, x + 10.

That's eleven unique sums, so no matter what the remaining digits sum to, you know that you can pick one of {x, ..., x + 10} such that the total sum is divisible by 11.