CS 2104 OOC 1 Summer 2014 ------------------------------------------------------------------------------- 1. Partition the cube into sub-cubes with sides .1 foot long; that yields 1000 sub-cubes. Since there are 2001 flies, by the Pigeonhole Principle there must be at least one sub-cube containing more than 2 flies. Now, a cube with a side of .l feet will have a diagonal of length sqrt(.1^2 +.1^2 +.1^2) = .1 * sqrt(3) = .1732 feet. Since 2/11 feet (the diameter of the sphere in question) equals about .182 inches, we see that each sub-cube will fit within such a sphere. Therefore, there must be a group of 3 or more flies that are all within a sphere of radius 1/11 feet. 2. Suppose that it is possible to cover an equilateral triangle with two smaller equilateral triangles. Let S be the length of a side of the large equilateral triangle, so each of the smaller ones will have sides with length less than S. Now, the large equilateral triangle has three corners, and by the Pigeonhole Principle, one of the smaller equilateral triangles must contain at least two of those corners. Let T be the length of a side of the smaller equilateral triangle (so T < S). But the distance between the corners of the large equilateral triangles is exactly S, and there cannot be two points in or on the smaller equilateral triangle that are further apart than T. And T < S. Therefore, it's not possible to cover the large equilateral triangsle with two smaller ones. 3. Now, Jones does not know immediately whether any of the statements are true or false. He does know that the first two natives cannot both be truth- tellers, since they contradict each other. But the third native's statement is still informative. If the third native is a truth-teller, then his statement confirms that so is the first native, and therefore: Native 1: truthful Native 2: cannot be liar since his last statement was true; cannot be a truth-teller since his first statement was false Therefore, the third native cannot be a truth-teller, and so he must be a liar. Then the third native's statement confirms that the first native is NOT a liar (and hence is a truth-teller). And so: Native 1: truthful Native 2: liar Native 3: liar Island: Isle of Baloney So, it's possible for Jones to determine everything. 4. Let's consider what the statements of the first four natives tell us... Could there be no Truthfuls? No, since then the fourth native would have made a true statment and hence would be a Truthful. So, there's at least one Truthful (but we don't know it must be the fourth native). Could there be one Truthful? Apparently, yes, since that would be consistent with everything that's been said, if the fourth native is a Truthful. And, similarly there could be two Truthfuls (only the second and fifth), or three Truthfuls (only the first, second and fifth). But there cannot be four Truthfuls, since that would imply both the third and fourth natives have lied. And, there cannot be five Truthfuls for the same reason. So we know the number of Truthfuls must be one or two or three. Now, what might the fifth native have said to settle the issue? If he said "three", Jones would still be in doubt; if the fifth was lying then there'd be one Truthful (native number four), but if the fifth was telling the truth there'd be three Truthfuls (one, two and five). If the fifth native said "two", there are still two possibilities: either native four is the only Truthful, or natives two and five are. If the fifth native said either "four" or "five", Jones would know he was a liar, and hence there cannot be two or three Truthfuls since each of those cases requires that the fifth native be a Truthful. If the fifth native said "one" and he is a Truthful, then the first three must be liars, but then that implies the fourth native is telling the truth, which means the fifth must be a liar after all. If the fifth native said "one" and he is a liar, then what does Jones know? There cannot be two or three Truthfuls, since the fifth native is a liar. But there also cannot be one Truthful since that would make the fifth native's statement true. So, actually, the fifth native cannot have said "one". So, the fifth native could have said either "four" or "five", and that would have been sufficient for Jones to conclude that the fourth native was a Truthful, and that the other four were not.