That's a whole bunch of balls

A collection of 2015 balls are numbered from 1 to 2015. Each ball may be coloured green or red according to the following rules:

(i) If balls $a$ and $b$ are two different red balls with $a+b \leq 2015$ , the ball $a+b$ is also red.

(ii) If ball $a$ is red and another ball $b$ is green with $a+b \leq 2015$ , then $a+b$ is green.

Find, with proof, the number of different possible ways of colouring the 2015 balls.

Bonus: Generalise this for $n$ balls.

#Combinatorics #Sharky

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

Suppose there are $N$ balls.

All green is one possible coloring. Otherwise, there exists a red ball; let $m$ be the smallest red ball. We claim that all balls with number not a multiple of $m$ are green. Suppose there exists another red ball with number not divisible by $m$ ; let the smallest of such numbers be $n$ . Since $m$ is the smallest red ball, $n > m$ ; also, since $n$ is not divisible by $m$ , $n-m \neq m$ . Thus $n-m$ is green. But $m$ is red, so $n = (n-m)+m$ should be green, contradiction.

A single red ball is also a possible coloring. Otherwise, there exists a second red ball. As shown above, this red ball must be a multiple of $m$ ; call the smallest one to be $km$ . If $k \ge 3$ , we can use the same argument as above to reach a contradiction, so $k = 2$ . Now we claim that all multiples of $m$ are red. Suppose there exists a green ball that is a multiple of $m$ ; call the smallest one to be $km$ . Since $m, 2m$ are red by assumption above, $k \ge 3$ , so $k-1 \ge 2$ . So $m, (k-1)m$ are different balls, and since $km$ is the smallest green ball, $(k-1)m$ is red. But then $km = m + (k-1)m$ should be green, contradiction.

We have determined all the possible colorings above:

All green: $1$ coloring
One red ball: $N$ colorings
Many red balls: $N$ colorings, minus $\lceil N/2 \rceil$ where there is only one red ball (only one multiple)

In total, there are $2N + 1 - \lceil \frac{N}{2} \rceil$ colorings. For $N = 2015$ , this gives $3023$ .

Ivan Koswara - 5 years, 7 months ago

If ball a is green and ball b is green then ball a+b<2015 then A+B IS GREEN

Amrit Nimiyar - 5 years, 7 months ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$