Proof check about a particular partition of natural numbers

44 Views Asked by At

enter image description here

In this theorem we find the definizione of allowable partiton given a natural number n. I can't figure how the bound on u and v is found, precisely I don't understand how the replacement on u and v would find the desired bound. Also, seems to me that v equals d maybe there is a missed passage.

1

There are 1 best solutions below

0
On BEST ANSWER

Given $m\ge 2n(n+1)$, let $x=\lfloor \frac m{n+1}\rfloor$ and $d=m-x(n+1)$. Then $x\ge 2n$ and $0\le d\le n$. Let $$ A:=\{\,(u,v)\in \Bbb N^2\mid u\ge v\ge 0,\, m=u(n+1)+v(n+2)\,\}.$$ Then from $$m=x\cdot(n+1)+d = (x-d)\cdot(n+1)+d\cdot(n+2)$$ and $x-d\ge n\ge d\ge 0$, we see that $(x-d,d)\in A$, i.e., the set $A$ is non-empty. Hence there exists $(u_0,v_0)\in A$ that minimizes the map $f\colon A\to\Bbb N$, $(u,v)\mapsto u-v$. As $$(\underbrace{u_0-n-2}_{=:u'})(n+1)+(\underbrace{v+n+1}_{=:v'})(n+2)=m$$ and $u'-v'<u_0-v_0$, minimaltity of $(u_0,v_0)$ tells us that $u'\ge v'\ge 0$ is false, i.e., that $u'<v'$. Hence, $$ 0\le u_0-v_0=u'-v' +2n+3<2n+3. $$