Let us index the trees from 1 to 6. The index of a sparrow is the index of the tree it is currently sitting on. A pair of sparrows flying can be modeled as an iterative step of a loop. When a sparrow at tree i flies to tree i + d, another sparrow at tree j flies to tree j – d. Thus, after each iterative step, the sum S of the indices of the sparrows remains invariant. Moreover, a loop invariant is true at the start and at the end of the loop.
At the start of the loop, the value of the invariant is
S = 1 + 2 + 3 + 4 + 5 + 6 = 21
When the loop ends, the loop invariant has the same value. However, when the loop ends, if all the sparrows were on the same tree, say k, then S = 6k.
S = 1 |
loop invariant at the start of the loop |
|
S = 6k, |
loop invariant at end of the loop |
|
6k = 21, |
loop loop invariant has the same value at the start and the end |
|
It is not possible – 21 is not a multiple of 6. The desired final values of the sparrow indices is not possible with the loop invariant. Therefore, all the sparrows cannot gather on one tree.