Foxy
Dennis, a professor of computer science at New York University, is the author of The Puzzling Adventures of Dr. Ecco (Dover, 1998); Codes, Puzzles, and Conspiracy (W.H. Freeman & Co., 1992); Database Tuning: A Principled Approach (Prentice Hall, 1992); (coauthored with Jason Wang and Bruce Shapiro) Pattern Discovery in Biomolecular Data: Tools, Techniques, and Applications Oxford University Press, 1999); and (coauthored with Cathy Lazere) Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists (Springer Verlag, 1998). He can be contacted at DrEcco@ ddj.com.
The two judges happened to be among the world's best women table tennis players. I Fei and Tiffany had each won a recent world championship. But their manner showed only concern for their sport. It seems that Strategy was trying to subvert Talent.
I Fei began: "Two international teams are to meet in either a mini- or maxi-competition at a table tennis tournament. Each team consists of 25 players, but for the mini-competition, only the nine best players will appear. Team A is the better team on the average, but team B has some excellent players as well.
"Since you are a mathematician, Dr. Ecco, we will state the problem in a way that you will find clear. Suppose we number the players from 0 (the best) to 24 (the worst) in each team so A[0] is the best player on the A team and B[0] is the best player on the B team. Then player A[i] will beat player B[i] by two points for every i between 0 and 24 inclusive. However, B[i] can beat A[i+1] (for every i between 0 and 23) by 2 points. Moreover, a strict transitivity holds, so for example, A[i] can beat A[i+1] by 4 points, and B[i+1] by 6 points. Similarly, B[i] beats A[i+1] by 2 points, B[i+1] by 4 points, A[i+2] by 6 points and so on. Do you get the picture?"
Ecco nodded.
Liane sketched out the relationships as you can see here. 
Tiffany continued: "The B team coach (whom we'll call 'Foxy') knows all of this. The A coach (whom we'll call 'Trusting Bull') does not. Foxy knows that his team will lose every game by 2 points, if he plays his best player (B[0]) against Trusting Bull's best player (A[0]), his second best player (B[1]) against Trusting Bull's second best (A[1]) and so on. Foxy, therefore, wants to figure out a way to organize the competition in such a way that the B team wins more games than the A team, but without arousing the slumbering suspicions of Trusting Bull. Trusting Bull might become suspicious if the average point spread in games when A players win is too high or if the maximum point spread in those games is too high.
"So, Foxy has set himself the problem of pairing up his players against the A team players in such a way that no B player loses by more than 10 and that the average point spread for games when A players win is well under 7. Even Trusting Bull would notice bigger point spreads than this. We are not of course asking for you to help Foxy, but rather asking whether he can achieve his sneaky goals and, if so, how.
"Here is an example to show you how this would go: If there were just five players on each side, then Foxy might pair up
| Ateam | Bteam |
|---|---|
| 0 | 4 |
| 1 | 0 |
| 2 | 1 |
| 3 | 2 |
| 4 | 3 |
which would enable B players to win by 2 points in every game except against A[0]. However, B[4] would then lose by 18 points. Foxy wouldn't choose this strategy because he would arouse the suspicions of Trusting Bull. Besides, he needs only a majority of games, not 4 out of 5."
Reader: First try to figure out a winning strategy for Foxy in the case of the mini-competition (nine players on each team) and then for the case of the maxi-competition (25 players on each team). In neither case should a B player lose by more than 10 points and the average B loss should be as near to 6 points as possible. One last wrinkle not mentioned by the champions: In the case of 25 players, at least five of the B wins should be by 2 points.
Last Month's Solution
Ecco and Liane's approach in the case where an ambulance would leave a hospital, pick up victims, and then return to the same hospital was the following: Consider every pair of victims and every site and see which pairs could be picked up from which site within the survival times of both victims. Then the program would pick among these pairs provided the choice produced no conflicts. Use the remaining ambulances to pick up single victims.
1. Given the initial distribution of ambulances, Ecco and Liane figured out how to pick up 14 victims. They used all three ambulances to pick up two victims from Pasteur and from De Gaulle, but none of those from Austerlitz. From Pasteur, remembering that counting starts at 0, they picked up victims 4 and 5 [at positions (53,48) and (51,47), respectively]. Also, victims 6 and 8; and 7 and 10. From De Gaulle, they picked up 15 and 18; 16 and 29; and 19 and 26. From Austerlitz, two of the four ambulances each picked up one victim: 0 and 2.
2. Distribute five ambulances to Pasteur, five to De Gaulle, and zero to Austerlitz. One Pasteur ambulance picks up victim 14. All others pick up victim pairs: victims 0, 2; 3, 4; 5, 7; and 6, 8. All 5 De Gaulle ambulances pick up victim pairs: 10, 12; 13, 23; 15, 18; 16, 29; and 19, 26. Thus, the ambulances picked up 19 victims altogether.
Reader Notes
Several of the solutions proposed by readers to the Wildfires puzzle (DDJ, January 2001) used a diagonal placement of cisterns and some produced far better results than Dr. Ecco's, notably those of Onno Waalewijn (who proposed using every fifth diagonal); Tomas G. Rokicki (who varied the gaps slightly to achieve high- and low-density coverage, http://tomas.rokicki.com/fire/); and Rodney Meyer.
Tomas expressed the advantage of diagonals this way: "Diagonal rows of cisterns work better to enclose fires than orthogonal rows. This is because the fires tend to spread orthogonally, and also because diagonal rows block the fire in two directions at once, where orthogonal rows only block the fire in one direction."
Andrew Palfreyman, on the other hand, chose a strategy in which he excluded strikes closest to the edges of the forest with surprisingly good results. Stuart Halloway fought fires by arranging cisterns in squares having holes. Mark Murphy used a random pattern and suggested mating this puzzle with the one about biodiversity. John Trono suggested a criss-cross diagonal strategy that worked nicely.
I think the diagonal strategies have it, but suspect that cistern layout depends a lot on the assumptions, viz. regular wind direction changes along north-south-east-west axes. A more realistic simulation in which wind direction may change continuously would be very worthwhile when this idea is reduced to practice.
DDJ
