The Math Forum

Search All of the Math Forum:

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

Math Forum » Discussions » Math Topics » alt.math.recreational

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Ara M Jamboulian

Posts: 71
Registered: 12/6/04
Re: Wee combinatorics puzzle
Posted: Feb 15, 2006 11:34 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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

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.

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.