302 6 Combinatorics and Probability
877.The distinct positive integersa 1 ,a 2 ,...,an,b 1 ,b 2 ,...,bn, withn≥2, have the
property that the
(n
2)
sumsai+ajare the same as the(n
2)
sumsbi+bj(in some
order). Prove thatnis a power of 2.878.LetA 1 ,A 2 ,...,An,...andB 1 ,B 2 ,...,Bn,...be sequences of sets defined by
A 1 =∅,B 1 ={ 0 },An+ 1 ={x+ 1 |x ∈Bn},Bn+ 1 =(An∪Bn)(An∩Bn).
Determine all positive integersnfor whichBn={ 0 }.
6.2.3 Counting Strategies
We illustrate how some identities can be proved by counting the number of elements of a
set in two different ways. For example, we give a counting argument to the well-known
reciprocity law, which we have already encountered in Section 5.1.3, of the greatest
integer function.
Example.Givenpandqcoprime positive integers, prove that
⌊
p
q
⌋
+
⌊
2 p
q⌋
+···+
⌊
(q− 1 )p
q⌋
=
⌊
q
p⌋
+
⌊
2 q
p⌋
+···+
⌊
(p− 1 )q
p⌋
.
Solution.Let us look at the points of integer coordinates that lie inside the rectangle with
verticesO( 0 , 0 ),A(q, 0 ),B(q, p),C( 0 ,p)(see Figure 41). There are(p− 1 )(q− 1 )
such points. None of them lies on the diagonalOBbecausepandqare coprime. Half
of them lie above the diagonal and half below.
O(0, ) ( , )( ,0)qC p pqABFigure 41Now let us count by a different method the points underneath the lineOB. The
equation of this line isy=pqx. For each 0<k<qon the vertical segmentx=kthere
arekp/qpoints belowOB. Summing up, we obtain
⌊
p
q
⌋
+
⌊
2 p
q⌋
+···+
⌊
(q− 1 )p
q⌋
=
(p− 1 )(q− 1 )
2.
The expression on the right remains unchanged if we switchpandq, which proves the
identity.