Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



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 AB, > 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 > the quadratic > reciprocity law (in preparation). For a bibliography > of the other 221 > proofs, see > http://www.rzuser.uniheidelberg.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.



