Hello guys: I have been thinking half hr or so on this problem, so pls forgive me for anything wrong but I think I have an idea that might help:
-Assuming: 1) Giving the nature of the number of colors I supposed that both the inner and outer disks are divided into an even number of pieces (n) 2) Each section is painted with one and only one color. 3) Given that it is mentioned that the sections of the inner circle are painted randomly, then I assume that the sections on the outer circle are painted following a given order. 4) The sections are of the same size - Obs's: The easiest case is when the sections on the outer circle of the same color are toghether except for the border's. In that case you rotate the inner circle so the most reds are in the reds' section and we finish. Then we have to "spread out" the colors in the outer circle. The proof will be by induction on the numbers of white sections in the outer circle between two red sections without red section between them. What I mean is: if we have a section i painted red, then we have m white sections and then the section i+m+1 would be red. The idea here is that I want to push the problem to the limit when all the sections of the same color are toghether. -"proof" The only way possible for 2 red sections on the outter circle to be spread is that we have m=1 so we begin our induction there. This is only a sketch... 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 5) Given that the sections in the inner circle are painted randomly at least 2 reds "are" spread for at least 2 whites or 2 whites spread for two reds. We call this kind of sections (wrrw or rwwr) 6) Without lost of generality (WLG) it doesnt matter where wrrw are in the inner circle, we always have 2 matches with the outer circle. 7) So, if we have k sections of the form wrrw and rwwr we have k/2 colors that match with the colors of the outer sections. 8) Moreover if we move the inner circle we still have 2k sections that match 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. 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) j+1 is even 11) thanks to 4) we have the worst scenario no one in that wrw section matches with the RWR section. So we move the inner circle so they can match 12) now we have 3 more matches. And so happens when we have other wrw or rwr sections that didn't match. 13) (need to be proved) All wrw and rwr matches when we move the inner circle in 12) 14) thanks to 13) we have now 3*(k+1) more matches 15) Thanks to 10) we have 3*(k+1) + 4k = n and we have 3*(k+1) + 2k matches that is > n/2 That would conclude the proof for the basis. Maybe the case for m=2 its easier cause we are gonna have sections of the same color in the outer circle that would be next to each other. The idea came up with just one example of a circle divided in 24 sections, as I said I havent work in this a lot and all could be coincidence I hope this helps Alfredo Cruz P.D An interesting extension would be sections of arbitrary size and more than 2 colors or just one of them P.D1 Excuse my terrible english --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
