Necklace puzzle - yet another solution

Hi all,

I am posting here another solution to "Necklace Puzzle". The solution is by my friend Vaibhav Gupta

-------

Let A and B are the 2 necklaces with N gemstones. A and B has three types of
gemstones which are equal in number.

A = A[1] A[2] ... A[N]
B = B[1] B[2] ... B[N]

Where A[i] is the ith gemstone in Necklace A.
B[i] is the ith gemstone in Necklace B.

Let Color(A[i]) represents the type of the gemstone A[i].

We construct a bipartite graph G = (X,Y,E), with the following condition:

For each gemstone A[j] in A we create a node X_j in X. So |X| = N
Foe each gemstone B[j] in B we create a node Y_j in Y. So |Y| = N
E is the edges set from node in X to node in Y.

E = { (u,v) | u \in X and v \in Y and Color(u) = Color(v)}

|E| = (N^2) / 3 since each node has exactly N/3 edges.

We define weight to each edge in E:
Weight(e) = orientation of the string.
OR Mathematically
Weight((X_i,Y_j)) = i - j if i>=j
= N+i-j otherwise

0 <= Weight((X_i,Y_j)) <= N-1 since 1<=i<=N, 1<=j<=N So there are N possible values of weight.

Now we just need to prove that there are atleast N/3 edges of same weight.
This can be proved by pigon hole principle. There are (N^2) / 3 edges and
each edge has N possible values of weight so there must exist a set of
ceil(|E|/N) edges of same weight

|E| / N >= N/3

Hence proved.

For general case :

For 3 gemstone types
( a^2 + b^2 + c^2 ) / (a + b + c)

Where a is the number of gemstone of type 1.
b is the number of gemstone of type 2.
c is the number of gemstone of type 3.

For m gemstone types:
(N_1^2 + N_2^2 + N_3^2 ... + N_m^2) / (N_1+N_2+N_3 ..+N_m)

where N_i is the number of gemstone of type i.

---------