5
$\begingroup$

The good soldier Schweik had been ordered to line up a band of new recruits before their officer gave them a speech. The desired line sought to minimize the average difference in height of adjacent men. Schweik put the tallest recruit first, the shortest one last, and let the remaining men stand between them in random order. Did Schweik execute his order as stated? How would you arrange the recruits?

Hint: One may answer the first question affirmatively. The intended order was, of course, different; it could have been executed in two different ways.

EDIT: The below is the Solution but I couldn't understand the answer and it has some mathematical equation. will somebody explain ?.

! Schweik must have understood his order as one to minimize

Equation 1: $$ {1\choose n} [(h_2-h_1)+(h_3-h_2)+...+(h_n-h_{n-1})] = {1\choose n} (h_n-h_1) $$

where n is the number of recruits and hi, i = 1, 2, . . . , n, is the height of the recruit in the ith position. Since$$(h_n-h_1) /n$$ can be negative, its minimization means making it a negative number of the largest absolute value. This is achieved if h1 and hn are the largest and smallest heights, respectively, with the heights of all the others not contributing to the value of expression (1). The intended order was, of course, to minimize the average magnitude of the difference in height of adjacent men, that is,

Equation 2: $$ {1\choose n} (|h_2-h_1| + |h_3-h_2| + ... +|h_n-h_{n-1}|) $$

Since n is fixed, the multiple 1/n can be ignored. Sum (2) is minimized when the heights are sorted in either ascending or descending order to yield the difference $$ (h_{max}-h_{min})$$ between the maximal and minimal heights. For any other ordering, this sum can be interpreted as the sum of lengths of segments covering the interval with endpoints at hmin and hmax with some overlaps, which makes it larger than $$ (h_{max}-h_{min})$$. A more formal proof by mathematical induction is not difficult.

Improve this question
$\endgroup$
3
  • $\begingroup$ The intended solution matches my answer (except that as stated I use a different method to prove when sum 2 is minimized). Which parts of the proof do you need help with? If your question is fundamentally a math question, it may be better to ask on Mathematics (showing of course the proof from the onset, and asking about the specific points that you don't understand). $\endgroup$
    – Gilles 'SO- stop being evil'
    Dec 18, 2014 at 18:09
  • $\begingroup$ It was the math equation for me to understand $\endgroup$
    – PR_01
    Dec 18, 2014 at 18:16
  • $\begingroup$ Would it be possible to create a more thorough and/or descriptive title for this post? Thank you! $\endgroup$
    – user20
    Dec 18, 2014 at 20:57

4 Answers 4

Reset to default
7
$\begingroup$

“Difference in height”, for a reasonable person, is a positive number (or zero for identical twins): the height of the taller person minus the height of the shorter person. With this definition, the average difference in height between adjacent recruits is minimized by lining up the recruits in monotonic order of height (tallest in front, then the next tallest behind him, etc.; or swap back and front, which makes two ways to do the lineup).

One way to prove this is to write the equations and do a bit of algebra. Being a computer scientist, I'll propose a different way. Suppose there are three recruits with height $x \lt y \lt z$. If they are lined up with $y$ in the middle, then the average difference in height is $(|y-x| + |z-y|)/2 = (z-x)/2$. If $z$ is in the middle then the average difference in height is $(|z-x| + |y-z|)/2 = (z-x)/2 + (z-y)/2$. If $x$ is in the middle then the average is $(|x-y| + |z-x|)/2 = (z-x)/2 + (y-x)/2$. This is minimized when $y$ is in the middle. Therefore, when there are three consecutive recruits such that the middle one by position is not the middle one by height, swapping positions to put the middling-height recruit in the middle lowers the height. The only line-ups that cannot be improved this way are line-ups in height order, either increasing or decreasing.

A mathematically oriented sergeant might interpret “difference in height” as a signed value: the height of the recruit minus the height of the recruit in front of him. By this definition, the average height is $(x_1 - x_n)/n$ where $x_1$ is the height of the recruit at the back, $x_n$ is the height of the recruit at the front, and $n$ is the number of conscripts (the differences $(x_1 - x_2) + \dots (x_{n-1} - x_n)$ “cancel out”). The corporal achieved the minimum average difference by lining the conscripts up in this order (it's the largest achievable absolute value, with the orientation chosen to make it negative).

Improve this answer
$\endgroup$
1
  • $\begingroup$ This solution is much eaiser to understand. +1 for that $\endgroup$
    – PR_01
    Dec 18, 2014 at 18:17
2
$\begingroup$

If the aim is to minimize the average difference in height between any two adjacent men, it seems like the thing to do would be to surround each man with the two men closest to that man in height, which would logically mean lining the men up in order of increasing height.

But that seems too easy. Am I missing something?

Improve this answer
$\endgroup$
4
  • $\begingroup$ I do believe you are right. And the other of the "two different ways" is to line them up in order of decreasing height. $\endgroup$
    – dmg
    Dec 18, 2014 at 16:00
  • $\begingroup$ On second thought, "to minimize the average difference in height of adjacent men" may mean, to minimize this for a single person (to minimize the difference between him an his adjacent people), which is again solved with sorting. $\endgroup$
    – dmg
    Dec 18, 2014 at 16:18
  • $\begingroup$ @dmg The way I interpreted that was "find the difference in height between each set of adjacent men, then find the average of those values". The best way to minimize the average in that case would be to minimize the differences. $\endgroup$
    – Roger
    Dec 18, 2014 at 16:25
  • $\begingroup$ either way, sorting is the correct way. $\endgroup$
    – dmg
    Dec 18, 2014 at 16:31
1
$\begingroup$

If I'm understanding the proposed solution correctly, the writer is saying that the order of the men other than the two on the ends does not matter.

This is easily proven false with an example. Suppose we give the heights of the men in inches, and their heights are 66, 68, 69, and 72 inches. If we arrange them in order of height, then the differences are 2, 1, and 3, for an average of 2. If we keep the shortest first and the tallest last but switch the two in the middle, so the order is 66, 69, 68, and 72, then the differences are 3, 1, and 4, for an average of 2 2/3. 2 <> 2 2/3. The order of the men in the middle matters.

The issue may be one of definitions. Normally, if you asked someone, "What is the difference between Al's height and Bob's height?", he would state the difference as a non-negative number. That is, if Al is 68 inches and Bob is 72 inches, we would say that the difference in their heights is 4 inches. Very very few people would say "If you name Al first, then it's minus 4 inches; but if you name Bob first, then it's plus 4 inches."

The formula given is using signed numbers when it should be using absolute values.

Side note: The divisor is not n but (n-1). If there are 3 men, then there are 2 height differences, not 3: h1 vs h2 and h2 vs h3.

Improve this answer
$\endgroup$
0
$\begingroup$

Another way to think of it:

All the recruits are the same height. This would result in the absolute minimum in average differences between the height of adjacent soliders... 0.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.