This problem I think can be solved using strong induction! My proof: The total number of positions we can align the inner circle with the outer circle is 200. Let's try to calculate the total number of matches over all 200 alignments.
For each sector of the inner circle, it would match 100 of them of the outer circle since there are 100 reds and whites on the outer circle. Therefore total number of matches is 200*100 . Therefore the average number of matches is 200*100/100 = 100. Therefore there exists one alignment where atleast 100 of them match. Let me know if anyone has trouble understanding the solution ( i feel I didnt make it clear) . But I am sure it's right :) regards, Pradeep On 3/25/07, Alfredo Cruz <[EMAIL PROTECTED]> wrote: > > > @Karthik > > I think the confusion arises from my lack of explanation in the nature > of the "pseudo-induction" > Lets take 2 sections in the outer circle that are painted red (S1, > S2). My variable "m" "messures" the number of whites between S1 and S2 > with no red sections. > What I wrote is the basis of the pseudo-induction (m=1). If we have > m=1 then the outer circle will be painted only in this way ...R(S1) W > R(S2) W R W... As we increase m we will eventually stop when all reds > are toghether and all whites are toghether in the outer circle. For > example, for m=2 we are gonna have ...R(S1) W W R(S2) W (R)..., for > m=3 ...R(S1) W W W R(S2)... > > In your example if we take RRWWWWRR in the outer circle we can make R > R(S1) W W W W R(S2) R that would correspond to m=4. Its important that > once we choose S1 and S2, we dont change them, so the pseudo-induction > works. > > The general idea is this: > 1) The problem is that the we "can not" give an order to the sections > in the inner circle. > 2) I divided the inner circle's sections so we can give them an order. > If u see I divided the inner circle's sections in 2 classes. One class > is the 3-set sections (wrw and rwr) that could not match at all at the > begining. The other class is the 4-set sections (wrrw and rwwr) that > it doenst matter how we move the circle, if we have m=1 then 2 colors > will always match. > 3) That its the key (for me). For m>1 we partition the inner circle in > classes so we have at least one class that we can predict how many > sections will match at least so we can play with the other class > (classes) by moving the inner cicle. I dont really know if we can > always dived the inner sections in 2 classes or as m grows we have > more classes. > 4) At the end we are gonna stop when we have the case that it seems > Vishal has already solved. > > What I wrote was only the basis of my pseudo-induction > > Notes: > The statement I made at 8) should say: > 8) Moreover if we move the inner circle we still have k/2 sections > that > match > ------- > The statment I made at 9) is wrong but that doesnt change anything I > though it was nice. > 9) (need to be proved) if we consider wrw, rwr, wrrw, rwwr sections > then we always have a red next to a white on the borders of the > sections. i.e. wrw-rwr or wrw-rwwr or rwr-wrw, etc. > ------- > The statement I made at 10) should say (wrong variable j insted of k): > 10) (need to be proved) if we have k wrrw and rwwr sections. Then we > have k+1 wrw and rwr sections. (not so sure) k+1 is even > > > I hope this helps > > Alfredo Cruz > On Mar 25, 9:43 am, "Karthik Singaram L" <[EMAIL PROTECTED]> > wrote: > > @alfredo: > > > > I dint get this part: > > > > 1) Lets say that we have the outer circle painted in the following > > manner: 1 red(C1), 1 white(C2), 1 red(C3), etc. We call this sections > > (RWR) > > 2) Then if we have that the inner circle is painted in the same way we > > finish. > > 3) if not then lets say that we have a least one section in the inner > > circle that is painted 1 white(c1) 1 red(c2) 1 white(c3) or 1 red, 1 > > white, 1 red. We call this sections (wrw or rwr) > > 4) we rotate the inner circle so C1 = c1 > > > > Say we have RRWWWWRR in the outer circle > > If the inner circle is WRRRRRRRW (we have two matches here) > > The solution would be RRWWRRRRR (with 6>=4 matches) > > > > Plz clarify if i am misinterpreting your solution > > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
