Another approach:
On the state [image: F=\{H_f,P_f\}], where each person holds exactly
one of [image:
H=\{25,25,24,24,\cdots,14,14,13\}], and keep passing on the rest 25
cards [image:
P=\{1,1,2,2,\cdots,12,12,13\}] to the left. Denote this as final state. In
this state, in every 25 rounds, the one holding 13 will get the other 13
once, thus having equal number on both cards.
On some state [image: S_i=\{H_i, P_i\} \ne F], there must be some [image: x
\in H_i], [image: y \in P_i] that [image: x<y]. Suppose person [image: i]
holds card x, and card y is passed on to the [image: k_{th}] person(0<k<25)
to the right of person i.
Consider the next k-1 rounds: a) person i swaps card x for larger one to
hold; b) card x is hold by some one, no longer passing on; c) neither a nor
b happens, then person i holds card x and gets card y in [image: k_{th}]
round, thus passing on card x in the next round.
In all cases, someone swaps his holding card for larger one, and state [image:
\{H_i,P_i\}] changes with [image: \sum H_i] strictly increasing. Thus we
show that in any state other than final state F, state change must happen
within next 24 rounds.
On the other hand, the total increase in all rounds cannot exceed
[image: ((25+25+24+24+\ldots+14+14+13)-(1+1+2+2+\ldots+12+12+13)) = 312].
So there are no more than 312 state changes, each happening in at most 24
rounds after the previous change, ending with final state F, after which in
every 25 rounds one of the person gets 2 cards with number 13.
*tl;dr. After at most 312*24 rounds, the final state F is reached, when
each person holds one of [image: \{25,25,24,24,\cdots,14,14,13\}]. Then
with at most 25 extra rounds, one person get 2 cards with number 13.**
2015-08-19 19:43 GMT+08:00 tec <technic....@gmail.com>:
> 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.
