Could you help me with this problem on natural numbers?

68 Views Asked by At

Pick two natural numbers $q,n \in \mathbb{N}$ such that $1<q<n$ and for $0 \leq j\leq q-1$ define $a(j) = \lfloor \frac{n-j}{q}\rfloor$.
The claim is that the elements of the set

$\{rq+j \mid 0\leq r\leq a(j)-1,\ 0\leq j \leq q-1\}$

are all distinct and no greater than $n-q$.

The second part is clear since for each $0 \leq j \leq q-1$ it holds that $(a(j)-1)q \leq \left(\frac{n-j}{q}-1\right)q = n-q$, however I can't see how this and the definition would imply that the elements of the sets are distinct. Maybe it's trivial, but I really can't see the answer.

1

There are 1 best solutions below

1
On

Being picky, a set only has distinct elements by definition.

However, I think the following addresses your concern. The set $\{rq+j \mid 0\leq r\leq a(j)-1,\ 0\leq j \leq q-1\}$ is the disjoint union of sets of form $A_r:=\{rq+j\mid 0\leq j\leq q-1\}$, where $0\leq r\leq a(j)-1$. It is clear that $A_r$ does not have repeated elements. We now observe that the minimum element in $A_r$ is $rq$ and the maximum element $rq+q-1$ which is less than $(r+1)q$. Hence, if $p>r$, then $\min (A_p)>\max(A_r)$, from which it follows all sets are disjoint.