0

Suppose that I have 2 positive integers $N$ and $K$ $(K \ge 3)$, I want to write

$N = 1*x + 2*y + K*z$.

All $x, y,z$ are non-negative integers. $z$ should be $\lfloor\frac{N}{K}\rfloor$ or $\lfloor\frac{N}{K}\rfloor - 1$.

Are there any ways to verify that $N$ can be written in that form, so that $x + y + z$ is an odd number?

Trường Giang Vũ
  • 3

1 Answers1

0

If we fix $z$, we have $x + 2y = N-Kz$. If $N-Kz > 1$, we can always choose the parity of $x+y$ by choosing between $y=0$ and $y=1$. If $N-Kz \le 1$ we are forced to have $x = N-Kz$, $y=0$.

Therefore the only cases which fail for the choice $z = \left\lfloor\frac NK\right\rfloor$ are (a) $z$ is odd, $N - Kz = 1$; (b) $z$ is even, $N - Kz = 0$.

If we can choose $z = \left\lfloor\frac NK\right\rfloor - 1$, similar constraints apply. Of course, we can't do that validly if that would give $z < 0$.

So the cases where this is impossible are:

  1. $\left\lfloor\frac NK\right\rfloor = 0$, $N - K\left\lfloor\frac NK\right\rfloor = 0$. That comes down to $N = 0$. I'm not sure whether you consider $0$ positive or not, but I presume not since you also use the term non-negative in the question.
  2. $\left\lfloor\frac NK\right\rfloor$ is odd, $N - K \left\lfloor\frac NK\right\rfloor = 1$, $N - K \left(\left\lfloor\frac NK\right\rfloor - 1\right) = 0$. But then $K = -1$, so this is not a valid solution.
  3. $\left\lfloor\frac NK\right\rfloor$ is even, $N - K \left\lfloor\frac NK\right\rfloor = 0$, $N - K \left(\left\lfloor\frac NK\right\rfloor - 1\right) = 1$. But then $K = 1$, so this is not a valid solution.

Conclusion: for all $N > 0$ and $K > 1$ it is possible.

Peter Taylor
  • 13,425