Competition - post a photo you've taken of nature >>

Natural number colouring problem11

I have been pondering over a maths problem that seems to have me stumped. I would like some hints on how to go about it as I have tried for over half an hour but to no avail. Any help is much appreciated.

Problem :
Let n be a natural number. We want to colour each natural number red or blue according to the following conditions:
1) There are infinitely many red numbers and infinitely many blue numbers.
2) The sum of every n distinct red numbers is red and the sum of every n distinct blue numbers is blue.

Is this possible when:
a) n = 2007
b) n = 2008.

Justify your answer.

Thank you for any help!

Reply 1

EmptyMathsBox

Note: I am more concerned about part b) rather than part a). a) is easy enough, all odd numbers are red, all even numbers are blue and it works.

Reply 2

Smaug123

Original post by EmptyMathsBox

Note: I am more concerned about part b) rather than part a). a) is easy enough, all odd numbers are red, all even numbers are blue and it works.

I don't know how to approach this problem, so I'll do some small cases and then some speculation on future directions.

For any odd

n

, your odd/even red/blue distinction works, since an odd sum of odd numbers is odd, while an even sum of even numbers is even.

For n=2, it is impossible: WLOG 1 is red. Then the next red number is m, say; we have

m+1, m+2, \dots

all are red by induction.

If we ever have n-1 consecutive reds, we've got all future numbers being red. Likewise if we ever have n consecutive blues, all future numbers are blue.

More generally, let the first n red numbers be

1=m_1, m_2, m_3, \dots, m_{n-1}, m_n

. Then

(m_2 + m_3 + \dots + m_n) + 1

is red,

(m_1+m_2 + m_3 + \dots + m_n) + m_1 + m_2 + \dots + m_{n-1}

is red, etc, so by induction, all future numbers in a multiple of

m_1 + \dots + m_{n-1}

are red.
Example: with n=3 using the red/blue odd/even colouring: 1,3,5 gives 9 red, then 9+1+3=14, then 14+1+3=18, …

We've found an arithmetic progression, all sufficiently large members of which are red:

\sum_{i=1}^n m_i + k \sum_{i=1}^{n-1} m_i

.

We can do something similar with blue, and even more interestingly, since every number is red or blue, we only need to go up to 2n^2 before we have n blue and n red (because we aren't allowed n consecutive reds or blues).

We therefore have some bounds on

\sum_{i=1}^{n-1} m_i

for red and blue respectively. It might be that we can ensure those numbers are relatively prime, so that the two sequences which are necessarily red and blue respectively must intersect (contradiction) unless n is odd.

(Of course, my postulate here is that it can be done iff n is odd.)

Reply 3

EmptyMathsBox

Thank you for your post but I fail to see why in there are n-1 consecutive reds/blues then all the numbers after that are a single colour. For n = 2 it works. But for other n such as n = 4 it does not. I.e. if 2,3,4 are all red then by your statement all of 5,6,7... should be red but I do not understand how this results in 5 (or even 6) being forced to be red.
Also why do all multiples of

have to be red. Clearly the

term does not have to be a multiple of

because it has an extra m_{n} term which does not need to be a multiple of that.

I also think that it can only be done if n is odd but am unable to show this. I shall keep trying and if you have any more hints, please do not hesitate to share.

P.S. How do I use Latex on TSR?

(edited 9 years ago)

Reply 4

rayquaza17

Original post by EmptyMathsBox

P.S. How do I use Latex on TSR?

Use this website: http://www.codecogs.com/latex/eqneditor.php Copy the code and put {tex} {/tex} around it (but use square brackets [] instead of {}).

Reply 5

Smaug123

Original post by EmptyMathsBox

have to be red. Clearly the

term does not have to be a multiple of

I assumed WLOG that 1 was red. Hence it's n-1 consecutive (non-1) reds that are required. Sorry, I should have said the non-1 bit. In fact, the blue bit is nonsense, isn't it. I need to remember not to try maths late at night.