5

Question from Engel's book problem solving strategies.

Let $p$ and $q$ be fixed integers. The set of integers are to be partitioned into three subsets $A,B,C$ such that for any $n \in \mathbb{Z}$, the three integers $n, n+p$ and $n+q$ belong to different subsets. What conditions must $p$ and $q$ satisfy?

I have hardly any idea how to do this question.

Maybe can see it as a graph, and each vertex is a number, and from vertex $n$, there is an edge going to vertices $n-p, n-q, n+p, n+q$, and we are looking for a 3-coloring?

A easy case is if the pattern is somehow regular, like $p=2,q=4$, then we can partition as $\{0,1,6,7 \dots\}, \{2,3,8,9,\dots\},\{4,5,10,11\dots\}$

Parcly Taxel
  • 103,344
eatfood
  • 2,414
  • Oops I made a mistake, it should be $p=2,q=4$, I have made the correction – eatfood Jul 03 '19 at 05:32
  • 1
    One basic example that works is if $p = 1$ and $q = 2$, with the $3$ sets being one for multiples of $3$, one for those with a remainder of $1$ when divided by $3$ and one for with a remainder of $2$ when divided by $3$. More generally, $p$ and $q$ can be any $2$ integers where one is congruent to $1$ modulo $3$ and the other is congruent to $2$ modulo $3$. Your example of $p = 2$ and $q = 4$ fits this. However, I don't offhand if there are any other sort of general conditions that can work (I don't think there are) and, if not, how to prove what I just wrote are the most general conditions. – John Omielan Jul 03 '19 at 05:36
  • I believe I have a basic proof, but it's somewhat long & messy, plus it's quite late here (just before midnight), so I'll outline it for you. Start with $n=n_0$ for any $n_0$ integer. Let $n_0$ be in set $1$, $n_0+p$ in set $2$ & $n_0+q$ in set $3$. Next, $n=n_0+p$ is in set $2$, so $n_0+2p$ & $n_0+p+q$ are in sets $1$ & $3$ in some order. Next, $n=n_0+q$ is in set $3$, so $n_0+p+q$ & $n_0+2q$ are in sets $1$ & $2$ in some order. As $n_0+p+q$ is common to both, it can't be set $2$ or $3$, so it's set $1$. Thus, $n_0+2p$ is set $3$ & $n_0+2q$ is set $2$. You can continue this process to ... – John Omielan Jul 03 '19 at 06:57
  • (cont.) show (e.g, by induction) that the set which $n_0+jp+kq$ belongs to depends on what $j+2k$ is modulo $3$. Next, if $p$ & $q$ don't have different non-zero values modulo $3$, you can show a contradiction where an element of one set has the same value as an element of another set. I hope this makes some sense &, ideally, you can finish the proof (ideally in a somewhat simpler manner than I'm outlining here), or maybe somebody else will do it instead. – John Omielan Jul 03 '19 at 07:04
  • @JohnOmielan See my proof. – Parcly Taxel Jul 03 '19 at 07:35
  • @JohnOmielan I think I get what you mean, so $j+2k \mod 3$ determines which set $n+jp+kq$ is in. Then since $n_0+jp+kq = n_0 + (j+tq)p + (k-tp)q$ for any $t$, we must have $(j+tq)+2(k-tp) \equiv j+2k$, which is $q\equiv 2p $, and since $p,q$ coprime, they are not both equal $0 \mod 3$, which means $p,q$ are different modulo $3$. – eatfood Jul 03 '19 at 09:06
  • @ParclyTaxel I'm not very familiar with graph theory, but it looks like an interesting & valid method to solve the problem. – John Omielan Jul 03 '19 at 16:47
  • @eatfood You have the right idea. However, as you showed yourself, with $p=2$ and $q=4$, they are not co-prime. Instead, you need to do something like show that if it works for $p$ and $q$ which are coprime, so they are not then both equal to $0$ mod $3$, then it will also work for $dp$ and $dq$ for any non-zero integer $d$. You can actually do that with your argument above by replacing $tq$ and $tp$ with $tq/d$ and $tp/d$ where $d = \gcd(q,p)$. – John Omielan Jul 03 '19 at 16:54

1 Answers1

2

We approach this from the perspective of colouring the graph $Z$ where each vertex represents an integer, the colours correspond to the desired partitions and $n,n+p,n+q$ are given different colours.

If $\gcd(p,q)=d>1$, $Z$ is the disjoint union of $d$ copies of itself. Hence we may assume $\gcd(p,q)=1$, in which case $Z$ is a triangular lattice as shown below. There is only one way to 3-colour this lattice up to colours, which assigns the same colour to all points $n+mp+nq$ with $m\equiv n\bmod3$.

Some numbers are repeated in this lattice, however. To obtain a line of integers we must project the lattice onto a line, i.e. define some relation $ap+bq=0$ with $\gcd(a,b)=1$. This projection must not conflict with the 3-colouring, which implies that $a,b$ satisfy the same relation as $m,n$ above: $a\equiv b\bmod3$. Taking $ap+bq=0$ modulo $3$ we then see that $a(p+q)\equiv0\bmod3$ where $a\not\equiv0\bmod3$ (otherwise $\gcd(a,b)$ would not be $1$), implying $p+q\equiv0\bmod3$.

Combining this last relation with $\gcd(p,q)=1$, we see in the general case that for the pair $(p,q)$ to define an admissible partition, it must be of the form $(dp',dq')$, where $\gcd(p,q)=d$, one of $p'$ and $q'$ is $1\bmod3$ and the other is $2\bmod3$.

Parcly Taxel
  • 103,344
  • What does it mean by $Z$ forms a triangular lattice before substituting the numerical values of $p$ and $q$? – eatfood Jul 03 '19 at 08:10
  • @eatfood I added a picture. – Parcly Taxel Jul 03 '19 at 08:20
  • Could you elaborate why defining the relation $ap+bq=0$ will project the lattice onto the line? – eatfood Jul 03 '19 at 09:08
  • @eatfood Since $\gcd(p,q)=1$ by assumption, every number $n$ may be written as $kp+lq$ for integer $k,l$. We now draw a line from $(0,0)$ in the picture above to $(a,b)$, as well as parallels passing through every point in the lattice. Now we look down the length of these lines. All the infinity of points that lie on the line passing through $(k,l)$ are deemed equal to $kp+lq$, and thus collapse into a definite number. – Parcly Taxel Jul 03 '19 at 09:16