The Height of Women
(or: No Repeated Difference)

Five women are standing on platforms on a stage.  The shortest woman measures 5 feet, 0 inches.  Each woman is a different height, and the difference in height between any pair of women is a different integral number of inches.  There are four platforms on the stage, raising the shorter women to the height of the tallest.  If the total platform height is a minimum, what are the heights of the other four women?

Extensions: Some obvious extensions suggest themselves.  Repeat the problem for 3,4,6,7,8 women.  Is there any pattern or procedure which helps in the solutions?

Source: Original.

Solutions were received from Kirk Bresniker, Alan O'Donnell, Jin Won Park, Philippe Fondanaiche, Graeme Finlay.

Update 11/4/2006.  Graeme Finlay and students at Q/E Jr/Sr. High School in Calgary, Alberta found fault with the solutions below.  As stated, the problem is looking for the minimum platform height, not the minimum person height. They have improved upon the original solution considerably.  Here is their email:

My students and I were looking at this problem and had a disagreement with the solution provided.

For 5 women you had the heights listed as 5'11,5'9,5'4,5'1,& 5'0 with the inches over the shortest girl being 11,9,4,1,0 but the total platform height (the sum of the heights required to make them all even) is 30 inches.

If the women's heights are 6'0, 5'11, 5'9, 5'5 & 5'0 then difference in height over the shortest is 12,11,9,5,0 but the total platform height is only 23 inches.

Kirk and Alan pointed out this is simply a veiled restating of the Golomb Ruler problem:

http://mathworld.wolfram.com/GolombRuler.html.  (I knew that.)

Alan's summary of the answer is thorough:

#     tallest  inches over shortest girl
2       5'1"    0 1 
3       5'3"    0 1 3
4       5'6"    0 1 4 6 
5       5'11"   0 1 4 9 11
6       6'5"    0 1 4 10 12 17
7       7'1"    0 1 4 10 18 23 25
8       7'10"   0 1 4 9 15 22 32 34
9       8'8"    0 1 5 12 25 27 35 41 44
10      9'7"    0 1 6 10 23 26 34 41 53 55
So the answer to part 1 of your puzzle is {5'0", 5'1", 5'4", 5'6"}

To generalize, a perfect arrangement (if there is one) requires the tallest girl to be [at least] n(n-1)/2 inches taller than the shortest.

From Guinness World Records:
http://www.amazon.com/gp/product/0553588109/103-9788456-9239026?v=glance&n=283155

"Tallest woman Zeng Jinlian (China) measured 8 ft. 1.75 in. (2.48 m) when she died on February 13, 1982.
Tallest living woman When last measured, Sandy Allen (U.S.A.) was 7 ft. 7.25 in."

So, you'll be struggling to match the criteria even with 7 'girls' >= 5'0".

However.... girls all start at not much over 12" at birth, so we could theoretically assemble 11 girls, with a minimum difference between tallest and shortest of 72" (shortest + 0 1 4 13 28 33 47 54 64 70 72). Occasionally it may be possible to assemble 12 girls, which would need a difference of 85" (7'1") (shortest + 0 2 6 24 29 40 43 55 68 75 76 85) [Unless you can find a 6.25" baby, a 7.25" baby and Sandy Allen and get them all together...]
Mail to Ken