Colours on my mind
- What on earth are you doing?
- Where else?
- ?!
- I am colouring numbers.
- But how is that possible? I thought they were just abstractions, not anything touchable.
- I colour them in my mind.
- And how does it go? I see you use only red and blue.
- I also try to make numbers that differ by 7 or 11 the same colour.
- Isn’t that difficult?
- You tell me! If you can see the colours I am thinking of you shouldn’t have any problems finding that out.
Problem source: Mathcamp 2009.
February 8th, 2010 at 5:19 am
This turns out to be the same as (or at least very closely related to) a postage stamp problem, I think. What numbers can’t you make using only 7-cent and 11-cent stamps?
February 8th, 2010 at 5:54 am
You seem to understand it, mathmom. Please could you explain it in simpler terms? I couldn’t understand at all what the problem asks us to do.
February 8th, 2010 at 6:08 am
Put the numbers 1, 2, 3, … in two sets such that numbers that differ by 7 or 11 are in the same set. If you can’t do it for all natural numbers do it for 1, 2, 3, …, n where n is as big as possible.
February 8th, 2010 at 12:02 pm
If you have two coprime numbers, such as 7 and 11, there will be a largest number N that you can’t make up from a sum of multiples of 7 and multiples of 11 (and after that point you can make every number). So, if you tried to do all the natural numbers, all the numbers would end up being the same color. (I’m going to start from 0, because it’s clearer, but you could start from 1 and add a bunch of +1’s in my argument). If you color 0 red, you also have to color all multiples of 7 and all multiples of 11 red, and also all the numbers that can be made up of multiples of 7 and 11, including all numbers >N. And then you can count back from those new numbers made up of 7’s and 11’s by 7 and/or 11 and eventually you will color every number. That is for any x N for some y which is red, so x must be red too.
So… if you can find N, that’s an upper bound on how high we could go and still have 2 separate colors. But it may be a red herring — I’m not sure!
February 8th, 2010 at 12:38 pm
In practice, I can only go up to 12, but I can’t yet explain why.
February 8th, 2010 at 12:56 pm
How do you colour to get to 12?
February 8th, 2010 at 4:33 pm
Oh, I see, Jan. Right. I didn’t understand your “try”.
We can put all numbers which differ by multiples of 77 into the same set, no problem. By the same set I mean that I have determined that all numbers in the same set will be coloured with the same colour, but have not yet decided which colour. So we now have 77 sets, namely the residue classes modulo 77. So the question reduces to how best to colour these.
Arrange them in a rectangle like so, where each number n stands for that residue class modulo 77 which includes n.
00 07 14 21 28 35 42 49 56 63 70
11 18 25 32 39 46 53 60 67 74 04
22 29…
33…
44…
55…
66…
Then regard each number in the bottom row as “next to” the number in the top row in the same column, and each number in the right-hand column as “next to” the number in the left-hand column in the same row. Then numbers m, n are next to each other if and only if they stand for sets M, N where members of M differ from members in N by 7 or 11. For example 74 and 4 stand for {74, 151,…} and {4, 81, 158,…}, and 74 and 81 differ by 7. So in every place where two numbers next to each other get different colours we break the condition. It’s clear that in order to avoid breaking the condition at all, we must colour all the numbers the same colour, which breaks the other condition that we must use two colours.
OK, I can do {1,…,16}:
Red: 7, 14, 3, 10
Blue: 6, 13, 2, 9, 16, 5, 12, 1, 8, 15, 4, 11
Each number differs by 7 or 11 from the numbers I’ve listed it next to (that’s why I listed the numbers that way). This proves that the above partition of {1, …, 16} is the only possible one.
{1, …, 16} is best, and the following theorem is the last link in the chain:
Theorem: Where n is greater than 16, {1, …, n} cannot be two-coloured.
Proof:
n=17: 17 differs by 7 from red 10 and by 11 from blue 6, so {1,…, 17} cannot be two-coloured.
n greater than 17: {1,…,n-1} cannot be two-coloured, so the only possible two-colouring of {1,…,n} would be if {1,…,n-1} were one colour and n was the other. However, this makes n a different colour from n-7 and n-11, and this is not allowed. Thus {1,…,n} cannot be two-coloured.