wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Existence of some funcitons on fixed points
        
(Message started by: beibeibee on Oct 6^th, 2004, 11:11am)

Title: Existence of some funcitons on fixed points
Post by beibeibee on Oct 6^th, 2004, 11:11am

For any natural number n greater that 2, are there functions, say f_1, f_2, …, f_n, such that the class including all the sets {n in N: f_i (f_j(n))=n } for i, j > 0 but i not = j, is exactly a partition of the set of natural numbers?

When n = 2, the answer is Yes. This is easy. ;D Can u see it?

Then consider generally! It seems very hard. ::)

Title: Re: Existence of some funcitons on fixed points
Post by Aryabhatta on Oct 6^th, 2004, 2:26pm

The following seems to work (highlight to view)

[hide]
Given n > 1.

Let [bbn] be the set of natural numbers.
Split [bbn] into a disjoint union of m = n(n-1) sets C₁,...,C_m each set being infinite.

Let S = {(i,j) | i,j [in] {1,2,...,n} and i [ne] j}.
We have a bijection B:S [onetoone] {1,2,...,m}.

Also, for ordered pairs (i,j) and (j,i), we have bijections h_ij:C_i[onetoone]C_j and h_ji:C_j[onetoone]C_i such that
h_ij and h_ji are inverses of each other.

Define f_i as follows.
for each j [ne] i, on C_B(i,j), f_i coincides with h_ij
On any other set C_k, f_i is the identity.

The partitions which we get are C₁,...,C_m

[/hide]

Title: Re: Existence of some funcitons on fixed points
Post by beibeibee on Oct 7^th, 2004, 6:38am

Re:The following seems to work (highlight to view)

Aha, you are right precisely! It is actually an excise in a class of first order logic.

Thanks for your reply.