@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 -~----------~----~----~----~------~----~------~--~---
