In my parallel computing class, I have this proof in one of my HW problems:
Suppose we have chosen a block agglomeration of $\mathrm n$ elements (labeled $\mathrm 0, 1, ... , n - 1$) to $\mathrm p $ processes (labeled $\mathrm 0, 1, ... , p - 1$) in which process $\mathrm i $ is responsible for elements $\mathrm\lfloor in/p \rfloor$ through $\mathrm\lfloor (i+1)n/p \rfloor - 1$. Prove that the last process is responsible for $\mathrm\lceil n/p \rceil$ elements.
This is what I have so far, but in my result I keep getting $\mathrm\lceil n/p \rceil - 1$ instead of $\mathrm\lceil n/p \rceil$ elements.
I was wondering if I could have a hint as to what I may be doing wrong? Thanks a lot.
Let process $\mathrm i $ be equal to $\mathrm p - 1$ to represent the last process.
Then process $\mathrm p $ is responsible for elements $\mathrm\lfloor{(p-1)n\over p}\rfloor$ through $\mathrm\lfloor{((p-1)+1)n\over p}\rfloor - 1$
= $\mathrm\lfloor{pn-n\over p}\rfloor$ through $\mathrm\lfloor {pn\over p}\rfloor - 1$
= $\mathrm\lfloor n - {n\over p}\rfloor$ through $\mathrm\lfloor {n}\rfloor - 1$
So the process is responsible for = $\mathrm\lfloor n \rfloor -1 - \lfloor n - {n\over p}\rfloor$ elements
Simplify:
= $\mathrm\lfloor n\rfloor-1+\lceil -n+{n\over p}\rceil$ elements
= $\mathrm\lfloor n \rfloor -1 + \lceil {n\over p}\rceil-n$ elements
= $\mathrm\lceil n/p \rceil -1$ elements
For integers $a$ and $b$, with $a<b$, the number of integers from $a$ to $b$ (inclusive) is $b-a+1$, not $b-a$.