# Number of pairs satisfying $2\alpha + 3 \beta =k$

How can I prove the following:

Let $\mathbb{W}$ denote the set of non-negative integers. Then what is the cardinality of the set $$\bigl\{ (\alpha,\beta) \in \mathbb{W} \times \mathbb{W} \ | \ 2\alpha + 3\beta =k \bigr\}$$ I think it’s $\left\lfloor\frac{k}{6}\right\rfloor$ if $k \equiv 1 \ (\text{mod} \: 6)$ and $\left\lfloor\frac{k}{6}\right\rfloor + 1$ if $k \not\equiv 1 \ (\text{mod} \ 6)$.

But I am having trouble doing this. Can anyone provide me an answer, or thoughts on how to go about a solution.

-
What about proving your formulas for "small" k, then lifting the count to k+6? –  hardmath Apr 29 '12 at 22:56
If $2\alpha + 3\beta = k$, then $2(\alpha+3) + 3(\beta-2)= ?$ Or do you mean positive integers when you say "whole numbers"? –  Arturo Magidin Apr 29 '12 at 23:02
@TMM Downvoting due to choice of terminology seems a bit extreme, esp. for new members. –  Bill Dubuque Apr 29 '12 at 23:23
@Bill: Especially when the terminology is not uncommon in U.S. primary and secondary schools. –  Brian M. Scott Apr 29 '12 at 23:44
@Bill: Alright, I'll remove the downvote. I had the same thoughts as Arturo above and Douglas here, that the only natural definition of "whole numbers" is integers (aren't negative numbers whole numbers too?). But apparently this bad terminology is often used in the US. –  TMM Apr 30 '12 at 11:29

If $k=6n$, $\beta$ can be $0,2,4,\dots,2n$.

If $k=6n+1$, $\beta$ can be $1,3,5,\dots,2n-1$.

If $k=6n+2$, $\beta$ can be $0,2,4,\dots,2n$.

And so on.

-

Here’s a straightforward (if slightly ugly) approach.

Suppose that $k=6n$; then $\langle\alpha,\beta\rangle=\langle 0,2n\rangle$ is a solution, and it’s clearly the solution with minimum $\alpha$. Suppose that $\langle a,b\rangle$ is a solution with the smallest possible positive $a$. Then $2a+3b=6n$, so $2a=6n-3b=3(2n-b)$, and $3\mid 2a$. Since $2$ and $3$ are relatively prime, $3\mid a$, and we must have $a\ge 3$. But in fact $2\cdot 3+3(2n-2)=6n=k$, so $\langle 3,2n-2\rangle$ is a solution. By arguing along similar lines you should be able to show that the solutions are precisely the pairs $\langle 3m,2(n-m)\rangle$ such that $0\le m\le n$, so there are $n+1$ of them. And in this case $\left\lfloor\frac{k}6\right\rfloor+1=n+1$, as you conjectured.

Next consider the case $k=6n+1$. Then $k$ is odd, so if $2\alpha+3\beta=k$, $\beta$ must be greater than $0$. Can we find a solution with $\beta=1$? That would require that $2\alpha=6n+1-3=6n-2=2(3n-1)$, which is fine: $\langle\alpha,\beta\rangle=\langle 3n-1,1\rangle$ is a solution with minimal $\beta$. In the first case I got the remaining solutions by changing $\alpha$ by $3$ and $\beta$ by $2$, but in opposite directions. Suppose that in this case I try increasing $\beta$ from $1$ to $d+1$; if $\langle a,d+1\rangle$ is a solution, it must satisfy $2a+3(d+1)=6n+1$, or $3d=6n-2-2a=2(n-1-a)$. As before, this implies that $2\mid d$, so $d\ge 2$. And again we find that the smallest possible value works: $\langle 3(n-1)-1,3\rangle$ is a solution, and you can show without too much trouble that the solutions are the pairs $\langle 3(n-m)-1,2m+1\rangle$ such that $0\le m<n$. There are $n=\left\lfloor\frac{k}6\right\rfloor$ of them, precisely as you conjectured.

The other cases can all be handled similarly.

-

Just for notation purposes, let $S = \{(\alpha, \beta) \in \mathbb{W} \times \mathbb{W} \ | \ 2\alpha + 3\beta = k\}$.

Case 1: $\mathbb{W} = \mathbb{Z}$

In this case we can inductively define $S$ by:

1. $(-k, k) \in S$
2. $(\alpha, \beta) \in S \ \Longrightarrow \ (\alpha + 3, \beta - 2) \in S$
3. $(\alpha, \beta) \in S \ \Longrightarrow \ (\alpha - 3, \beta + 2) \in S$

Since we can start with the pair from 1. and apply either 2. or 3. indefinitely to generate new pairs, we get $\color{blue}{|S| = \infty}$.

Case 2: $\mathbb{W} = \mathbb{N}$

Starting with the pair from 1. above we need to apply rule 2. exactly $\lceil k/3\rceil$ times to get $\alpha > 0$, i.e. to get a pair $(\alpha, \beta) \in S$. We can then repeatedly apply 2. to get good pairs, up until we applied it $\lfloor k/2 \rfloor$ times. Applying it one more time will lead to $\beta < 0$. So in total we get $\color{blue}{|S| = \lfloor k/2 \rfloor - \lceil k/3 \rceil + 1}$, or equivalently, $\color{blue}{|S| = \lfloor k/6 \rfloor}$ for $\color{red}{k \not\equiv 1 \bmod 6}$ and $\color{blue}{|S| = \lfloor k/6 \rfloor - 1}$ for $\color{red}{k \equiv 1 \bmod 6}$.

-
If $k$ is even, then $\beta$ must be even.
Thus $\beta=2\gamma$, with $0 \leq \gamma \leq \frac{k}{6}$. Each such $\gamma$ leads to an unique solution $\alpha=\frac{k-6\gamma}{2} \,;\, \beta =2\gamma$.
If $k$ is odd, then $\beta$ must be odd.
Thus $\beta=2\gamma+1$, with $0 \leq \gamma \leq \frac{k-3}{6}$. Each such $\gamma$ leads to an unique solution $\alpha=\frac{k-6\gamma-3}{2} \,;\, \beta =2\gamma+1$.