We color numbers $1,2,3,...,20$ in two colors, blue and yellow, such that both colors are used (not all numbers are colored in one color). Determine number of ways we can color those numbers, such that product of all blue numbers and product of all yellow numbers have greatest common divisor $1$.
Problem
Source: Bosnia and Herzegovina Junior Balkan Mathematical Olympiad TST 2016
Tags: Coloring, greatest common divisor, combinatorics
NikoIsLife
16.09.2018 15:51
Without loss of generality, suppose that $6$ is blue. (Don't forget to multiply the answer by two at the end!)
Then this means, all the even numbers and all the multiples of $3$ should be yellow. Also, since the numbers $10$ and $14$ are colored yellow, then this means $5$ and $7$ should be colored blue.
The only numbers left uncolored are $1,11,13,17,19$. We are free to color these numbers in any way we want, as they don't affect the GCD in any way. This gives us $2^5=32$ ways to color these five remaining numbers.
Therefore, the answer is $2\times32=\boxed{64}$
Nymoldin
01.10.2020 18:20
NikoIsLife wrote:
Without loss of generality, suppose that $6$ is blue. (Don't forget to multiply the answer by two at the end!)
Then this means, all the even numbers and all the multiples of $3$ should be yellow. Also, since the numbers $10$ and $14$ are colored yellow, then this means $5$ and $7$ should be colored blue.
The only numbers left uncolored are $1,11,13,17,19$. We are free to color these numbers in any way we want, as they don't affect the GCD in any way. This gives us $2^5=32$ ways to color these five remaining numbers.
Therefore, the answer is $2\times32=\boxed{64}$
But you are forgot one case which is all colours are not colored 1 colour.You must subtract all Blue colouring and all Yellow colouring from your answer. Answer is 64-2=62
huashiliao2020
05.04.2023 19:08
Nymoldin wrote: NikoIsLife wrote:
Without loss of generality, suppose that $6$ is blue. (Don't forget to multiply the answer by two at the end!)
Then this means, all the even numbers and all the multiples of $3$ should be yellow. Also, since the numbers $10$ and $14$ are colored yellow, then this means $5$ and $7$ should be colored blue.
The only numbers left uncolored are $1,11,13,17,19$. We are free to color these numbers in any way we want, as they don't affect the GCD in any way. This gives us $2^5=32$ ways to color these five remaining numbers.
Therefore, the answer is $2\times32=\boxed{64}$
But you are forgot one case which is all colours are not colored 1 colour.You must subtract all Blue colouring and all Yellow colouring from your answer. Answer is 64-2=62 There are already blue or yellow because the 6 is one color and multiples of 2, 3 are another. There is no overcount. @2above nice sol!