8
$\begingroup$

Each of the positive integers from 1 to n is colored either black or white. You can repeatedly choose a number m and recolor m together with those numbers, which are not coprime to m. At the beginning all numbers are white.

For which n is it possible to accomplish that all numbers are colored black?

$\endgroup$
7
  • $\begingroup$ Answer is probably "all positive integers", but I don't see how to prove it. $\endgroup$
    – WhatsUp
    May 18 at 20:17
  • $\begingroup$ Isn't that I just choose largest prime I could as "m"? $\endgroup$
    – Jan Ivan
    May 19 at 8:20
  • $\begingroup$ @JanIvan It says you colour the numbers that are NOT coprime, so choosing the largest prime would only change that single number, since all other numbers are coprime to it. $\endgroup$ May 19 at 8:33
  • $\begingroup$ I don't see how you can change the color of number 1. (PS: oops, just choose m = 1) $\endgroup$
    – Florian F
    May 19 at 11:14
  • 1
    $\begingroup$ I assume with "recolor a number", it is meant to "invert the color of the number", and not "color them to the same color as m" ? $\endgroup$
    – fishinear
    May 19 at 17:26
15
$\begingroup$

Since "non-coprimeness" (or more commonly, sharing a factor) is symmetric, (if A toggles B, then B will toggle A), and sharing more than one factor only counts once, we can draw a graph of "which number toggles which", and then the name of the game will be

Lights Out on an undirected simple graph, with all lights initially on.

An interesting property of this "toggle everything" variant is that

it is always solvable, no matter what is adjacent to what (as long as the adjacency matrix is symmetrical, i.e. there are no one-directional graph edges),

so we should be safe in claiming that it's possible to get all digits black

no matter what n is.

$\endgroup$
6
$\begingroup$

While Bass's solution is correct, I'll give a more constructive proof that

all n work.

Proof:

By induction/construction. The base case of $n=1$ is solved just by picking $1$.
Suppose that you have a set S containing a selection of numbers which will solve the problem of colouring $1$ to $n-1$ black. Then you can extend this to work for $n$ as well depending on the nature of $n$.

1. If $n$ is divisible by $p^2$, then $n$ and $n/p$ are affected by exactly the same elements of S, so $n$ will already be coloured black.
2. If $n$ is a prime, then just choose $n$ to colour it black without affecting any smaller numbers. (Actually this is a special case of the next one)
3. If $n$ is a product of distinct primes, then you can change its colour by choosing as your moves the set of divisors of $n$, including $n$ itself but excluding $1$. These moves will toggle $n$'s colour without affecting any smaller numbers (proof below). You can then combine these with the moves in S, throwing out any duplicate moves, to get the set of moves that colour the numbers from $1$ to $n$.

In this way you can build up a solution to any $n$. For example:
$\{1,5,6\}$ is a solution for $n=6$. $7$ is prime so just add it to get
$\{1,5,6,7\}$ as a solution for $n=7$. $8$ and $9$ are divisible by squares, so
$\{1,5,6,7\}$ is also a solution for $n=9$. $10$ is a product of distinct primes, so add $\{2,5,10\}$ to get
$\{1,2,6,7,10\}$ as a solution for $n=10$. The two $5$ moves cancel each other.

Now for proof that if $n$ is a product of distinct primes, then the set T of divisors excluding $1$ when used as colouring moves will toggle only $n$.
Let $k<n$. Let $p$ be any prime that divides $n$ but does not divide $k$, which must exist since $n$ uses each prime only once and $k$ cannot include all of them.
The moves from $T$ that affect the colour of $k$ can be gathered in pairs that differ only by a factor of $p$. Therefore $k$ is affected by an even number of moves, and will have no net colour change. For example, if $n=30$ we have $T=\{2,3,5,6,10,15,30\}$, and then for any odd number $k$ we can ignore the move $\{2\}$ as it won't affect $k$ and pair the other moves as $\{3,6\},\{5,10\},\{15,30\}$ where each pair will have no net effect on $k$.
The number $n$ itself is affected by all the moves in $T$, and since there are an odd number of them (if $n$ is the product of $m$ primes, then $|T|=2^m-1$ since $1$ is excluded) the number will change colour.

$\endgroup$
2
  • $\begingroup$ This is a very interesting algorithm! (reminiscent of rot13[vapyhfvba–rkpyhfvba]) Explicity, one can toggle the following integers exactly once each to succeed, as long as $n$ is rot13[nal vagrtre terngre guna bar: gbttyr $q=1$, nybat jvgu nyy vagrtref $q$ fhpu gung gurer ner na bqq ahzore bs fdhnerrserr zhygvcyrf bs $q$ hc gb $a$ (pbhagvat $q$ vgfrys)]. $\endgroup$ May 19 at 17:19
  • $\begingroup$ nice solution, I wish I can give more than +1 $\endgroup$
    – ThomasL
    May 19 at 18:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.