Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Wee combinatorics puzzle
Replies: 2   Last Post: Feb 15, 2006 11:34 PM

 Messages: [ Previous | Next ]
 Ara M Jamboulian Posts: 71 Registered: 12/6/04
Re: Wee combinatorics puzzle
Posted: Feb 15, 2006 11:34 PM

> Partition the set T={1,2,3,...,n} into 2 sets A and
> B. Define a function f
> on T by
> -- if x is in A, then f(x) is the number of elements
> y of B such that y<x
> -- if x is in B, then f(x) is the number of elements
> y of A such that y<x.
> Show that the sum of all the values of f is |A||B|,
> where |S| denotes the
> number of elements of a finite set S.
> There are at least two fairly quick proofs.
> This little thing is a feature of proof number 222 of
> reciprocity law (in preparation). For a bibliography
> of the other 221
> proofs, see
> http://www.rzuser.uni-heidelberg.de/~hb3/fchrono.html
> :)
>
>

Arrange the numbers in increasing order in each of A and B.
Then we see that f(a) = a - k where k is the position of a in the set A. Example: A = { 1,5,7,8 } then f(5) = 5 - 2 = 3 since 5 is in position 2 in A. Now add all the f(a) and f(b), a in A, b in B.

Date Subject Author
2/11/06 Larry Hammick
2/12/06 Rino Raj
2/15/06 Ara M Jamboulian