\((a,b,k)\quad (k<0)\)-additive partition of positive integers (Q1364947)

Let \(a,b,k\) be integers with \(a,b>0, k<0, a+k \geq 0\), and \(b+k \geq 0\). Define the sequence \(U=\{u_m\}_{m=1}^{\infty}\) by \(u_1=a,u_2=b\), and \(u_m=u_{m-1}+u_{m-2}+k\) for \(m \geq 3\). Suppose that \(B\) is a set of positive integers. An \((a,b,k)\)-partition of \(B\) consists of two subsets \(B_1,B_2\) such that \(B=B_1 \cup B_2\), \(B_1 \cap B_2= \emptyset\), and \(b_i+b_i'\notin U\) for all \(b_i,b_i'\in B_i, i=1,2\). The authors give necessary and sufficient conditions on \(a,b\), and \(k\) for the existence of an \((a,b,k)\)-partition when \(B\) is the set of positive integers, and derive a formula for the number of \((a,b,k)\)-partitions. Consider a graph \(G\) whose vertices are the positive integers, and where an edge exists between two vertices \(a\) and \(b\) if and only if \(a+b \in U\). There is a 1-1 correspondence between \((a,b,k)\)-partitions of the positive integers and 2-colorings of \(G\). The authors show that \(G\) has odd cycles, and hence no 2-coloring, under certain conditions. In the absence of these conditions, the authors reduce the problem of finding \((a,b,k)\)-partitions of the positive integers to that of finding 2-colorings of the subgraph \(G'\) of \(G\) whose vertices are the positive integers less than \(a+b+k\), and where an edge exists between \(x\) and \(y\) if and only if \(x+y \in \{a,b,a+b+k\}\). They describe the connected components of \(G'\) in terms of congruence classes \(\bmod \gcd(a+k,b+k)\). This gives a formula for the number of 2-colorings of \(G'\), and hence for the number of \((a,b,k)\)-partitions of the positive integers.