Proving the 'All Blonde Girls Have Blue Eyes' Fallacy Theorem

  • Thread starter Thread starter courtrigrad
  • Start date Start date
courtrigrad
Messages
1,236
Reaction score
2
Theorem Given any collection of $ n$ blonde girls. If at least one of the girls has blue eyes, then all $ n$ of them have blue eyes.

Proof. The statement is obviously true for n = 1. The step from k to k+1 can be illustrated by going from n = 3 to n = 4. Assume, therefore, that the statement is true for n = 3 and let G_1,G_2,G_3,G_4 be four blonde girls, at least one of which, say G_1, has blue eyes. Taking G_1,G_2, and G_3 together and using the fact that the statement is true when n = 3, we find that G_2 and G_3 also have blue eyes. Repeating the process with G_1,G_2 and G_4, we find that G_4 has blue eyes. Thus all four have blue eyes. A similar argument allows us to make the step from k to k+1 in general.


Corollary. All blonde girls have blue eyes.

Proof. Since there exists at least one blonde girl with blue eyes, we can apply the foregoing result to the collection consisting of all blonde girls.

Does it have to do with how we arrived at k+1?

Thanks
 
Physics news on Phys.org
Won't work for n=2: Let G_1 and G_2 be blonde girls and le't assume the theorem is true for n=1. If, for example G_1 is blonde, we can't take G_2 to the collection with her (that would be n=2), so we can't prove that G_2 is also blonde.

Hence the induction stops at n=1 and you'll never reach the step 3->4.

If you were guaranteed that the theorem is true for all pairs of blonde girls and I told you that my sister is blonde and has blue eyes then, yes, all blonde girls would have blue eyes.
 
Repeating the process with G_1,G_2 and G_4, we find that G_4 has blue eyes.

That is a non sequitur.
 
Thread 'Use greedy vertex coloring algorithm to prove the upper bound of χ'
Hi! I am struggling with the exercise I mentioned under "Homework statement". The exercise is about a specific "greedy vertex coloring algorithm". One definition (which matches what my book uses) can be found here: https://people.cs.uchicago.edu/~laci/HANDOUTS/greedycoloring.pdf Here is also a screenshot of the relevant parts of the linked PDF, i.e. the def. of the algorithm: Sadly I don't have much to show as far as a solution attempt goes, as I am stuck on how to proceed. I thought...
Back
Top