[algogeeks] Re: Pigeon Hole Principle

2007-03-27 Thread Karthik Singaram L
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

[algogeeks] Re: Pigeon Hole Principle

2007-03-25 Thread Alfredo Cruz
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)

[algogeeks] Re: Pigeon Hole Principle

2007-03-25 Thread Alfredo Cruz
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)

[algogeeks] Re: Pigeon Hole Principle

2007-03-25 Thread Alfredo Cruz
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)

[algogeeks] Re: Pigeon Hole Principle

2007-03-25 Thread Prunthaban Kanthakumar
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

[algogeeks] Re: Pigeon Hole Principle

2007-03-25 Thread Prunthaban Kanthakumar
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

[algogeeks] Re: Pigeon Hole Principle

2007-03-25 Thread Vishal
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

[algogeeks] Re: Pigeon Hole Principle

2007-03-25 Thread Santhosh Suresh
@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

[algogeeks] Re: Pigeon Hole Principle

2007-03-25 Thread Prunthaban Kanthakumar
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

[algogeeks] Re: Pigeon Hole Principle

2007-03-25 Thread Karthik Singaram L
@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

[algogeeks] Re: Pigeon Hole Principle

2007-03-25 Thread Alfredo Cruz
@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

[algogeeks] Re: Pigeon Hole Principle

2007-03-25 Thread Vishal
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

[algogeeks] Re: Pigeon Hole Principle

2007-03-24 Thread Vishal
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 +

[algogeeks] Re: Pigeon Hole Principle

2007-03-24 Thread Vishal
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

[algogeeks] Re: Pigeon Hole Principle

2007-03-24 Thread Karthik Singaram L
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

[algogeeks] Re: Pigeon Hole Principle

2007-03-24 Thread Santhosh Suresh
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

[algogeeks] Re: Pigeon Hole Principle

2007-03-24 Thread stone
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

[algogeeks] Re: Pigeon Hole Principle

2007-03-24 Thread Prunthaban Kanthakumar
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

[algogeeks] Re: Pigeon Hole Principle

2007-03-24 Thread Rajiv Mathews
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