Problem of the Month (October 2006)

This month I feature two problems which are generalizations of problems in "The Puzzling Adventures of Dr. Ecco", by Dennis Shasha. The first concerns how to rank several players in a tournament, and the second concerns how to build a building whose rooms have a tree structure.

Problem #1: The designers of a sports tournament want not only to identify the best player, but to completely rank the players. Assuming that the best player always wins a match, and assuming that the match schedule can not depend on the results of earlier matches, how many rounds and matches are necessary to do this? For example, the shortest tournaments for 2, 3, or 4 players are shown below. Time travels from left to right, the matches are represented by boxes, and the output of each box is assumed to be sorted.

In general, assume that we are playing some game where k players play at a time, and that the results of a match rank the k players. How many rounds and matches does it take to completely rank n players? How do the answers change if we only want to identify the top p players? How do the answers change if each match only identifies the best player?

Problem #2: An eccentric builder wants to build a 1-story building containing equal size rectangular rooms and no hallways. In addition, the building is to have a tree structure, so there is a unique path between any two rooms. The lobby must have a1 doors, and each of those rooms must have a2 more doors, and so on up to some final splitting with an doors. We say this is a a1a2...an building. What is the smallest aspect ratio for the rooms that will allow such a building?

ANSWERS

Problem #1:

It turns out that for k=2 these have been well-studied and are called Sorting Networks. Gavin Theobald sent me this page.

Let S(n) the fewest games needed to sort n players. Sune Kristian Jakobsen proved that ∑ log2 i (for 1≤i≤n) ≤ S(n) ≤ (3n2 – n)/2.

Corey Plover told me that Donald Knuth covered this problem in Section 5.3.4 of "The Art of Computer Programming", Volume 3, and sent two figures from that section. He also gave me some other references:

R.J. Nelson and R.C Bose showed that S(2n) ≤ 3n – 2n and therefore S(n) = O(nlog 3) in [JACM 9 (1962) p282-296].
T.N. Hibbard found a simpler construction using the same number of comparisons in [JACM 10 (1963), p142-150].
R.W. Floyd and D.E. Knuth proved S(n) = O(n1+c/√(log n)) in [Notices of the Amer. Math. Soc. 14 (1967), p283].
R.L. Drysdale and F.H. Young showed S(256) ≤ 3651 in [SICOMP 4 (1975), p264-270].
Ajtai, Komolos and Szemeredi showed that S(n) = O(n log n) in [Combinatorica 3 (1983), p1-19].

Here are the smallest known sorting tournaments for k=2:

nS(n)rounds
needed
100
211
333
453
595
6125
7166
8196
921-257
1025-297
1129-357-8
1233-397-8
1337-457-9
1441-517-9
1545-567-9
1649-607-9

Here are the smallest known sorting tournaments for k=3:

Here are the smallest known sorting tournaments for k=4:

Problem #2:

Here are the smallest known aspect ratio tree packings:

aiaspect
ratio		building
8>1
82>1
(Jeremy Galvagni)
72>1
621
622>1
63>4/3
(Jeremy Galvagni)
5221
52223/2
(Jeremy Galvagni)
523>4/3
(Jeremy Galvagni)
53>1
4231
4232??
424>7/4
(Jeremy Galvagni)
4321
4322??
433>8/5
(Jeremy Galvagni)
44>1
341
342>1
35>1
222221
(Jeremy Galvagni)
222222??
22223??
22241
22242??
2225>4/3
(Jeremy Galvagni)
2241
2242>1
(Jeremy Galvagni)
225>1
(Jeremy Galvagni)
2331
2332>10/7
(Jeremy Galvagni)
2343/2
(Jeremy Galvagni)
2421
(Jeremy Galvagni)
2422>6/5
(Jeremy Galvagni)
243>4/3
251
252>1
26>1
27>4/3

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 12/3/06.