March 1997 Presentation Topic (continued)
Use the fact that every pair appears once and only once on some field, count the total number of pairs and the number of pairs that appear on each field, and then by dividing, find the total number of fields.
Similarly, find the number of fields in which each variety appears by taking the total number of pairs involving that variety and dividing by the number of those pairs that occur in a single field.
Knowing these two numbers should help you figure out the schedule.
Hint for the Schoolgirl's Walk Problem. Try the same strategy as in the hint for the Farmer's Wheat Problem, above.
Hint for the Tournament Scheduling Problem. Calculate the number of games that must be played on each day. Use this to show that such a schedule cannot be found when n is odd.
It can be done when n is even. The n=2 case is easy: with two teams, there is just one game, taking place on one day. Now try to find schedules that work for the n=4, n=6, and n=8 cases. Can you arrange your answers to have a general pattern which extends and works for all even n?
Hint for Question 1. Suppose a point P occurs in r blocks. Find a formula for r in terms of v and k, thereby proving that the number r does not depend on which point P you were considering.
To find this formula, see the last part of the hint for the Farmer's Wheat Problem.
Hint for Question 2. Follow the same strategy as in the hint for the Farmer's Wheat Problem.
Hint for Question 3. If we can find a group of blocks (each block of size k) that represents each of the v points exactly once, then what do we know about v/k?
Hint for Question 4. It is not possible.
Hint for Question 5. Again, it is not possible, but a non-resolvable combinatorial design does exist. Can you find it?
Hint for Question 7. Each pair of girls corresponds to a pair of numbers from 1 to 15. Consider the three possible cases: both numbers are 7 or below, both are 8 or above, or one is 7 or below and the other is 8 and above.
Hint for Question 8. Exploit the vertical structure from the Fano plane solution, and the horizontal structure from the n=8 Tournament Scheduling solution, to show that if you find a set of five lines of girls which works for day 1, then cycle the girls by 1->2->3->4->5->6->7->1 and 8->9->10->11->12->13->14->8 (with 15 left unchanged), you get a set of lines which works for day 2, and by cycling again you get a set that works for day 3, and so on.