Consider each person holding 1 card (the larger) and passing 1 card around
(the smaller, passing to his left).
There are 25 cards on hold and 25 cards passing around at a time.
When a person get a number smaller than his card on hold, he keeps the new
card and passes on the original hold card (denoting this as a swap). In
this case, the number on the card he holds strictly increases.
Since the sum of the numbers on all 25 cards holding by someone cannot
larger than 2*(25+24+...+14)+13 = 481, the number of swaps is finite in all
possible scenario.
Now prove by contradiction:
Suppose at any point of time, no person will have same number on both his
cards. then the passing on can continue infinitely.
There must be a time point t, that no swaps occur after this point.
Now we examine consequent 25 turns after t, the card hoding by each person,
and the set of cards passing around, do not change in this period.
Denoting the card hoding by i'th person as hi, and the card passing on from
i'th person to the left at time t is pi.
For each person i, he receives and passes on cards pi, pi+1, ..., p25, p1,
..., pi-1 in those turns, without swaping the card he holds.
So hi >= pj for all i,j in 1..25, i!=j. And the equality can not holds due
to the assumption.
ie. min{h1,h2,...,h25} > max{p1,p2,...p25}.
But no such partition for set {1,1,2,2,...,25,25} exists. (the only
partition that meets min{h1,h2,...,h25} > max{p1,p2,...p25} is
{1,1,2,2,...,12,12,13} and {13,14,14,...,25,25})
That contradicts our assumption, thus proved the original claim.
2015-07-22 14:20 GMT+08:00 bujji jajala <jajalabu...@gmail.com>:
> 25 persons are seated in a round table. There are two sets of cards, each
> set having 25 cards numbered 1,2,3,, 25. Each one of them is given two
> cards from these set of cards.
>
> Each one will pass on card having smaller number to the one on his left.
> This happens synchronously.( All persons transfer cards at same instant ).
> Prove that at some point of time,
> some person will have same number on both his cards.
>
> -Thanks
> Bujji
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
>
--
__________________________________________________
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
