0
$\begingroup$

Is it possible to determine the number of non-negative integer solutions to $2x + y = N$ where $N$ is a non-negative integer? I was solving a problem when a particular equation of this kind came up and the book simply counted every case (which was rather tedious, given the large amount of cases). Later, I noticed a different problem which appeared to require the same number of solutions of $2x + y = N$ but it was not possible to count the cases because $N$ was not given.

I found another solution and it turned out not be necessary to solve for the number of solutions of the equation, however I'm still wondering if it is possible to find this number in terms of factorials and whatnot. I was not able to do it with the bars/stars method or whatever it's called. So, is it possible?

$\endgroup$
  • $\begingroup$ Since $y=N-2x$, the number of integer solutions is actually $\left\lfloor\frac{N}{2}\right\rfloor+1$. If you draw the function $y=N-2x$ in the first quadrant and work on the boundary conditions, you will easily get the answer. Also, I don't think that this is a combinatorics question... $\endgroup$ – Yourong Zang Nov 14 '19 at 0:28
  • $\begingroup$ This is the number of partitions of $N$ into at most $2$ parts or where no part exceeds $2$. The pattern continues: for example the number of solutions to $6u+5v+4w+3x+2y+z=1$ is the number of partitions of $N$ into at most $6$ parts or where no part exceeds $6$, though the formula gets more complicated $\endgroup$ – Henry Nov 14 '19 at 0:56
2
$\begingroup$

Case 1: $N$ is odd. We have $$ N=1: \quad 1 \mbox{ solution } \ (x,y)=(0,1) $$ $$ N=3: \quad 2 \mbox{ solutions } \ (0,3), \ (1,1) $$ $$ N=5: \quad 3 \mbox{ solutions } \ (0,5), \ (1,3), \ (2,1) $$ The pattern suggests that we have $\lceil N/2 \rceil$ solutions for odd $N$.

Case 2: $N$ is even. We have $$ N=0: \quad 1 \mbox{ solution } \ (x,y)=(0,0) $$ $$ N=2: \quad 2 \mbox{ solutions } \ (0,2), \ (1,0) $$ $$ N=4: \quad 3 \mbox{ solutions } \ (0,4), \ (1,2), \ (2,0) $$ This pattern suggests that we have $N/2+1$ solutions for even $N$.

In both cases, the number of solutions can be written as $\lfloor N/2 \rfloor +1$.

It remains to prove that the above guess is correct. (We can do this without much difficulty.)

$\endgroup$
1
$\begingroup$

A Proof of Alex's "guess" to show that why Alex says

We can do this without much difficulty

Since $y=N−2x$, the number of integer solutions is actually $\left\lfloor\frac{N}{2}\right\rfloor+1$. If you draw the function y=N−2x in the first quadrant, you will easily get two solutions (not necessarily integers) at the boundaries: $(x,y)=(0, N)$ and $(x,y)=(N/2,0)$. Since $N$ may not be an even number, we could say the largest possible integer solution of $x$ is $\lfloor N/2\rfloor$. Now, since an integer $(N)$ minus another integer $(2x)$ is still an integer $(y)$, we only need to see how many integer solutions of $x$ are in the first quadrant. You can get this by counting from $0$ to $\lfloor N/2\rfloor$, which is $$\#=\left\lfloor \frac{N}{2}\right\rfloor+1$$

$\endgroup$

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.