If $f = ax - by + 0c$, with non-negative $x$, $y$, $c$, and $x+y+c=n$, all integers, then how many distinct values does $f$ take?

Question

Given a function $f = ax - by + 0c$, with constraints $y\geq 0$, $x\geq 0$, $c\geq 0$, and $x+y+c=n$, where all are integers. I am interested to find the count of all unique values of $f$.

I know that total number of different arrangements of $a$, $b$, $c$ are $(n+1)(n+2)/2$. But how do I know how many these arrangements have same value of $f$?

Empy2 · Accepted Answer · 2018-11-04T11:51:54.430

1

If $a$ and $b$ have a common factor then so does every $f$. So divide $a$ and $b$ by the common factor. From now on, $a$ and $b$ are coprime.
$(x,y)$ lies within a triangle. Note $f=ax-by+0c=a(x-b)-b(y-a)+0c$ so only count $(x,y)$ if $(x-b,y-a)$ lies outside the triangle, otherwise the same $f$ is counted twice.

Suppose $n=5$, $a=2$ and $b=3$. The triangle has vertices $(0,0), (0,5)$ and $(5,0)$. The bottom three rows should all be counted because $x-3\lt0$ which is outside the triangle. For the other rows, only the first two columns should be counted.

edited Nov 04 '18 at 11:51

answered Nov 04 '18 at 11:41

Empy2

50,853

Can you please elaborate with an example that triangle part? – Resorcinol Nov 04 '18 at 11:47
Still didn't understand what you are saying. – Resorcinol Nov 04 '18 at 12:00
The triangle bounded by $x\ge0,y\ge0, x+y\le n$ has vertices at $(0,0),(0,n)$ and $(n,0)$. – Empy2 Nov 04 '18 at 12:06
For your cited example, I have 21 combinations and of which 2 will give 0 as the value of f, so the answer becomes 20. Can you show this using your answer? – Resorcinol Nov 04 '18 at 12:56
The bottom three rows contain 6+5+4 points = 15. The other three rows have 3+2+1 points, but only count the first two of each, which is 2+2+1=5. Total = 15+5 = 20. – Empy2 Nov 04 '18 at 13:00
I'm really sorry but I am not able to get what you are saying. – Resorcinol Nov 04 '18 at 13:03
Can you explain for n=70, a=4 and b=8. – Resorcinol Nov 04 '18 at 13:26
Now, I understood, thanks a lot. – Resorcinol Nov 04 '18 at 13:53

If $f = ax - by + 0c$, with non-negative $x$, $y$, $c$, and $x+y+c=n$, all integers, then how many distinct values does $f$ take?

1 Answers1