[algogeeks] Re: Pigeon Hole Principle
Yes...the proof is correct and this is what stone had suggested in his earlier post. Consider one red sector in the inner disk in each of the 200 different positions, it will match against exactly 100 sectors in the outer disk since there are 100 of the red sectors in the outer disk. Similarly for a white disk also, therefore there are a total of 200*100matching events and hence by PHP it is true that atleast one rotation must have 100 events. --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Pigeon Hole Principle
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 -~--~~~~--~~--~--~---
[algogeeks] Re: Pigeon Hole Principle
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 -~--~~~~--~~--~--~---
[algogeeks] Re: Pigeon Hole Principle
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 -~--~~~~--~~--~--~---
[algogeeks] Re: Pigeon Hole Principle
On 3/25/07, Rajiv Mathews [EMAIL PROTECTED] wrote: On 3/25/07, Prunthaban Kanthakumar [EMAIL PROTECTED] wrote: If you see carefully his proof does not assume anything about sections colored continuously. His proof assumes only one thing Half of them are red and half of them are white Half does not mean it should be continuous. So the proof still works correct unmodified even if the halves are not continuous. Could you elaborate please. His proof contains, Quote: If r = R-r, match half1 with Red half of outer disk. Total matching = r + 100 - R + r = 100 - R + 2*r How do you justify this if the sections aren't contiguous? I think the proof elaborated by _stone_ is correct and apt. There is an equivalence It is simple.Just consider, Half1 = All the sections in the outer disc painted red (This is not continuous. But nothing prevents you from assuming a non-continuous 100 red sections as a logical half) Half2 = All the sections in the outer disc painted white Now with this interpretation, read his proof. Just remember that when you say 'half' of inner disc it means the sections corresponding to the half in the outer disc as defined above. This is the key to establish equivalence). Regards, Prunthaban -- Regards, Rajiv Mathews --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Pigeon Hole Principle
Ouch I got the question completely wrong assuming the inner disc is continuous.Sorry for the confusion. On 3/25/07, Prunthaban Kanthakumar [EMAIL PROTECTED] wrote: On 3/25/07, Rajiv Mathews [EMAIL PROTECTED] wrote: On 3/25/07, Prunthaban Kanthakumar [EMAIL PROTECTED] wrote: If you see carefully his proof does not assume anything about sections colored continuously. His proof assumes only one thing Half of them are red and half of them are white Half does not mean it should be continuous. So the proof still works correct unmodified even if the halves are not continuous. Could you elaborate please. His proof contains, Quote: If r = R-r, match half1 with Red half of outer disk. Total matching = r + 100 - R + r = 100 - R + 2*r How do you justify this if the sections aren't contiguous? I think the proof elaborated by _stone_ is correct and apt. There is an equivalence It is simple.Just consider, Half1 = All the sections in the outer disc painted red (This is not continuous. But nothing prevents you from assuming a non-continuous 100 red sections as a logical half) Half2 = All the sections in the outer disc painted white Now with this interpretation, read his proof. Just remember that when you say 'half' of inner disc it means the sections corresponding to the half in the outer disc as defined above. This is the key to establish equivalence). Regards, Prunthaban -- Regards, Rajiv Mathews --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Pigeon Hole Principle
I did assume that the outer disk is painted half (contiguous) red and half white. However the 'equivalence' should do the trick and the same proof applies. As far as Stone's proof goes, I did not understand - For each inner section,no matter white or black ,there is 100 color-matching events. Can somebody explain? ~Vishal On 3/25/07, Prunthaban Kanthakumar [EMAIL PROTECTED] wrote: Ouch I got the question completely wrong assuming the inner disc is continuous.Sorry for the confusion. On 3/25/07, Prunthaban Kanthakumar [EMAIL PROTECTED] wrote: On 3/25/07, Rajiv Mathews [EMAIL PROTECTED] wrote: On 3/25/07, Prunthaban Kanthakumar [EMAIL PROTECTED] wrote: If you see carefully his proof does not assume anything about sections colored continuously. His proof assumes only one thing Half of them are red and half of them are white Half does not mean it should be continuous. So the proof still works correct unmodified even if the halves are not continuous. Could you elaborate please. His proof contains, Quote: If r = R-r, match half1 with Red half of outer disk. Total matching = r + 100 - R + r = 100 - R + 2*r How do you justify this if the sections aren't contiguous? I think the proof elaborated by _stone_ is correct and apt. There is an equivalence It is simple.Just consider, Half1 = All the sections in the outer disc painted red (This is not continuous. But nothing prevents you from assuming a non-continuous 100 red sections as a logical half) Half2 = All the sections in the outer disc painted white Now with this interpretation, read his proof. Just remember that when you say 'half' of inner disc it means the sections corresponding to the half in the outer disc as defined above. This is the key to establish equivalence). Regards, Prunthaban -- Regards, Rajiv Mathews --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Pigeon Hole Principle
@Vishal When you rotate the inner section through it's 200 configurations, each of the inner section happens to come in tune with each of the outer sections, so there will 100 'matchings' and 100 mismatches. On 3/25/07, Vishal [EMAIL PROTECTED] wrote: I did assume that the outer disk is painted half (contiguous) red and half white. However the 'equivalence' should do the trick and the same proof applies. As far as Stone's proof goes, I did not understand - For each inner section,no matter white or black ,there is 100 color-matching events. Can somebody explain? ~Vishal On 3/25/07, Prunthaban Kanthakumar [EMAIL PROTECTED] wrote: Ouch I got the question completely wrong assuming the inner disc is continuous.Sorry for the confusion. On 3/25/07, Prunthaban Kanthakumar [EMAIL PROTECTED] wrote: On 3/25/07, Rajiv Mathews [EMAIL PROTECTED] wrote: On 3/25/07, Prunthaban Kanthakumar [EMAIL PROTECTED] wrote: If you see carefully his proof does not assume anything about sections colored continuously. His proof assumes only one thing Half of them are red and half of them are white Half does not mean it should be continuous. So the proof still works correct unmodified even if the halves are not continuous. Could you elaborate please. His proof contains, Quote: If r = R-r, match half1 with Red half of outer disk. Total matching = r + 100 - R + r = 100 - R + 2*r How do you justify this if the sections aren't contiguous? I think the proof elaborated by _stone_ is correct and apt. There is an equivalence It is simple.Just consider, Half1 = All the sections in the outer disc painted red (This is not continuous. But nothing prevents you from assuming a non-continuous 100 red sections as a logical half) Half2 = All the sections in the outer disc painted white Now with this interpretation, read his proof. Just remember that when you say 'half' of inner disc it means the sections corresponding to the half in the outer disc as defined above. This is the key to establish equivalence). Regards, Prunthaban -- Regards, Rajiv Mathews -- Santhosh S ME05B045 Dept. of Mechanical Engineering, IIT Madras, Chennai-600036 --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Pigeon Hole Principle
When both disks are not painted continuous 'equivalence' does not work. Because in your proof when one half does not give the answer, you just take take the other half and align it. But for arbitrary configuration, when one configuration does not work, you cannot align the other half. It will not fit unless the sections are painted symmetrically. On 3/25/07, Vishal [EMAIL PROTECTED] wrote: I did assume that the outer disk is painted half (contiguous) red and half white. However the 'equivalence' should do the trick and the same proof applies. As far as Stone's proof goes, I did not understand - For each inner section,no matter white or black ,there is 100 color-matching events. Can somebody explain? ~Vishal On 3/25/07, Prunthaban Kanthakumar [EMAIL PROTECTED] wrote: Ouch I got the question completely wrong assuming the inner disc is continuous.Sorry for the confusion. On 3/25/07, Prunthaban Kanthakumar [EMAIL PROTECTED] wrote: On 3/25/07, Rajiv Mathews [EMAIL PROTECTED] wrote: On 3/25/07, Prunthaban Kanthakumar [EMAIL PROTECTED] wrote: If you see carefully his proof does not assume anything about sections colored continuously. His proof assumes only one thing Half of them are red and half of them are white Half does not mean it should be continuous. So the proof still works correct unmodified even if the halves are not continuous. Could you elaborate please. His proof contains, Quote: If r = R-r, match half1 with Red half of outer disk. Total matching = r + 100 - R + r = 100 - R + 2*r How do you justify this if the sections aren't contiguous? I think the proof elaborated by _stone_ is correct and apt. There is an equivalence It is simple.Just consider, Half1 = All the sections in the outer disc painted red (This is not continuous. But nothing prevents you from assuming a non-continuous 100 red sections as a logical half) Half2 = All the sections in the outer disc painted white Now with this interpretation, read his proof. Just remember that when you say 'half' of inner disc it means the sections corresponding to the half in the outer disc as defined above. This is the key to establish equivalence). Regards, Prunthaban -- Regards, Rajiv Mathews --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Pigeon Hole Principle
@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 RRRR in the outer circle If the inner circle is WRRRW (we have two matches here) The solution would be RRWWR (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 -~--~~~~--~~--~--~---
[algogeeks] Re: Pigeon Hole Principle
@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 RRRR 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 m1 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 RRRR in the outer circle If the inner circle is WRRRW (we have two matches here) The solution would be RRWWR (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 -~--~~~~--~~--~--~---
[algogeeks] Re: Pigeon Hole Principle
Got it. Stone's solution seems to be right. On 3/25/07, Prunthaban Kanthakumar [EMAIL PROTECTED] wrote: When both disks are not painted continuous 'equivalence' does not work. Because in your proof when one half does not give the answer, you just take take the other half and align it. But for arbitrary configuration, when one configuration does not work, you cannot align the other half. It will not fit unless the sections are painted symmetrically. On 3/25/07, Vishal [EMAIL PROTECTED] wrote: I did assume that the outer disk is painted half (contiguous) red and half white. However the 'equivalence' should do the trick and the same proof applies. As far as Stone's proof goes, I did not understand - For each inner section,no matter white or black ,there is 100 color-matching events. Can somebody explain? ~Vishal On 3/25/07, Prunthaban Kanthakumar [EMAIL PROTECTED] wrote: Ouch I got the question completely wrong assuming the inner disc is continuous.Sorry for the confusion. On 3/25/07, Prunthaban Kanthakumar [EMAIL PROTECTED] wrote: On 3/25/07, Rajiv Mathews [EMAIL PROTECTED] wrote: On 3/25/07, Prunthaban Kanthakumar [EMAIL PROTECTED] wrote: If you see carefully his proof does not assume anything about sections colored continuously. His proof assumes only one thing Half of them are red and half of them are white Half does not mean it should be continuous. So the proof still works correct unmodified even if the halves are not continuous. Could you elaborate please. His proof contains, Quote: If r = R-r, match half1 with Red half of outer disk. Total matching = r + 100 - R + r = 100 - R + 2*r How do you justify this if the sections aren't contiguous? I think the proof elaborated by _stone_ is correct and apt. There is an equivalence It is simple.Just consider, Half1 = All the sections in the outer disc painted red (This is not continuous. But nothing prevents you from assuming a non-continuous 100 red sections as a logical half) Half2 = All the sections in the outer disc painted white Now with this interpretation, read his proof. Just remember that when you say 'half' of inner disc it means the sections corresponding to the half in the outer disc as defined above. This is the key to establish equivalence). Regards, Prunthaban -- Regards, Rajiv Mathews --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Pigeon Hole Principle
Let R be the total reds on inner disk. Consider a half with 'r' reds. Half1 = r reds and 100-r whites Half2 = R-r reds and 100-R+r whites. If r = R-r, match half1 with Red half of outer disk. Total matching = r + 100 - R + r = 100 - R + 2*r Now r = R - r = 2*r - R = 0 Total matching = 100 - R + 2*r = 100 If r R - r, match half1 with white half of outer disk. Rest calculations are similar. On 3/18/07, Santhosh Suresh [EMAIL PROTECTED] wrote: This problem has been troubling me from quite a long time. The circumference of two concentric disks is divided into 200 sections each. For the outer disk, 100 of the sections are painted red and 100 of the sections are painted white. For the inner disk the sections are painted red or white in an arbitrary manner. Show that it is possible to align the two disks so that 100 or more of the sections on the inner disk have their colors matched with the corresponding sections on the outer disk. Please send in solutions. It seems to be trivial application of PHP. Thanks, --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Pigeon Hole Principle
The problem statement particularly mentions that inner disk has red and white sections painted **arbitrarily**. It doesn't say any such thing about outer disk. On 3/24/07, Rajiv Mathews [EMAIL PROTECTED] wrote: On 3/24/07, Vishal [EMAIL PROTECTED] wrote: If r = R-r, match half1 with Red half of outer disk. I think you've made an assumption that is not explicitly stated in the problem statement. You've assumed here that the outer disk has 100 red sections followed by 100 white sections. The question doesn't state a particular ordering only states that there are 100 white and red sections each on the outer disk. Please clarify. -- Regards, Rajiv Mathews --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Pigeon Hole Principle
yes...but that does not mean that you can assume that the 100 reds and 100 whites are contiguous blocks.It just says that the outer disk has a sum of the 100 reds and 100 whites and does not say that they are contiguous. --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Pigeon Hole Principle
Yes, I don't think we can assume that the reds and whites are contiguous. They might be arbitrarily distributed. The only information is that there are 100 reds and 100 whites. On 3/25/07, Karthik Singaram L [EMAIL PROTECTED] wrote: yes...but that does not mean that you can assume that the 100 reds and 100 whites are contiguous blocks.It just says that the outer disk has a sum of the 100 reds and 100 whites and does not say that they are contiguous. -- Santhosh S ME05B045 Dept. of Mechanical Engineering, IIT Madras, Chennai-600036 --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Pigeon Hole Principle
We rotate the inner disk at 200 different positions. Now we count the total number of color-matching events. For each inner section,no matter white or black ,there is 100 color- matching events. So total number of color-matching events is 100*200 The summation of color-matching events of 200 different positions are 200*100, so there must be a inner position which have =100 color-matching events. On Mar 18, 11:17 pm, Santhosh Suresh [EMAIL PROTECTED] wrote: This problem has been troubling me from quite a long time. The circumference of two concentric disks is divided into 200 sections each. For the outer disk, 100 of the sections are painted red and 100 of the sections are painted white. For the inner disk the sections are painted red or white in an arbitrary manner. Show that it is possible to align the two disks so that 100 or more of the sections on the inner disk have their colors matched with the corresponding sections on the outer disk. Please send in solutions. It seems to be trivial application of PHP. Thanks, --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Pigeon Hole Principle
Hi, The proof given by Vishal is correct irrespective of the arrangement (which he himself did not realize). If you see carefully his proof does not assume anything about sections colored continuously. His proof assumes only one thing Half of them are red and half of them are white Half does not mean it should be continuous. So the proof still works correct unmodified even if the halves are not continuous. Regards, Prunthaban On 3/25/07, Karthik Singaram L [EMAIL PROTECTED] wrote: yes...but that does not mean that you can assume that the 100 reds and 100 whites are contiguous blocks.It just says that the outer disk has a sum of the 100 reds and 100 whites and does not say that they are contiguous. --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Pigeon Hole Principle
On 3/25/07, Prunthaban Kanthakumar [EMAIL PROTECTED] wrote: If you see carefully his proof does not assume anything about sections colored continuously. His proof assumes only one thing Half of them are red and half of them are white Half does not mean it should be continuous. So the proof still works correct unmodified even if the halves are not continuous. Could you elaborate please. His proof contains, Quote: If r = R-r, match half1 with Red half of outer disk. Total matching = r + 100 - R + r = 100 - R + 2*r How do you justify this if the sections aren't contiguous? I think the proof elaborated by _stone_ is correct and apt. -- Regards, Rajiv Mathews --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
