Optimize ordered data under constraints

Your feedback matters:

Lesson progressPractice problems 0/3

Difficulty: Advanced
Estimated time: 29 minutes
Domains: Problem Solving and Data Analysis
Techniques: Constrained-dataOrdered-slotsExtremal-constructionComplementary-sumsFeasibility

What you’ll learn

Turn a mean into a total, and a median and range into fixed spots in an ordered list.
Keep rules like positive, integer and distinct in view while you fill the other spots.
Make one group as large as possible by making the rest as small as possible.
Prove a maximum or minimum can’t be beaten, then build a list that reaches it.
Check a finished list for count, order, total, median, range, every rule and what the question asks for.

Prerequisites

Why this matters on the SAT

Build the list that reaches the limit

Usually you’re given a list and asked for its mean or median. Some SAT questions flip that around. They fix the mean and the median, say, and ask for the smallest possible range. Now there’s no list to work from. You have to build one that pushes the range as low as it can go.

Solution to the example

Start with what can’t change. Nine values with a mean of $14$ must add up to

9(14)=126.

Put the values in order. The fifth one is the median, $10$ . Could the range be $8$ or less? The smallest value is at most $10$ , so the largest would be at most $18$ . Then the first five values are at most $10$ each, and the last four are at most $18$ each. Even the biggest total you could reach is

5(10)+4(18)=122,

which is short of $126$ . So the range has to be at least $9$ .

And $9$ works. Keep the first five values at $10$ and make the last four $10+9=19$ . That’s $50+76=126$ , right on target:

10,\ 10,\ 10,\ 10,\ 10,\ 19,\ 19,\ 19,\ 19.

Its median is $10$ , and its range is $19-10=9$ . The answer is B.

Notice the two parts. The first shows that nothing smaller than $9$ can work. The second shows that $9$ really can. You need both: a bound on its own might name a value no list can reach, and a list on its own doesn’t show you can’t do better. Bound it, then build it.

SAT example

A data set consists of $9$ integers. The mean of the data set is $14$ , and the median is $10$ .

What is the minimum possible range of the data set?

A
$8$
B
$9$
C
$10$
D
$14$

Translate the conditions into slots

Start by writing the unknown values in order, from least to greatest:

x_1\le x_2\le \cdots \le x_n.

Each position is a slot. Now every condition in the question becomes a rule about certain slots. In the opening example, the mean made the total $126$ , the median locked slot $5$ at $10$ , and the range tied the smallest and largest values together. Here’s the same idea for any list of $n$ values:

What each condition tells you about the slots

Condition	What it means for the slots
A mean of $M$ for $n$ values	The total is $nM$ .
A median of $m$ , with an odd number of values	The middle slot is $m$ . Slots to its left are at most $m$ , and slots to its right are at least $m$ .
A range of $R$	$x_n-x_1=R$ , so the largest minus the smallest is fixed. Move one end and the other has to move with it.
Positive integers	Every slot is one of $1,2,3,\ldots$ .
Distinct integers	No two slots are equal, so each is bigger than the one before: $x_1<x_2<\cdots<x_n$ .
Values from $L$ through $U$	Every slot sits between the two bounds: $L\le x_i\le U$ .

Say $11$ positive integers have median $6$ . The middle of $11$ values is slot $6$ , so the slots start out like this:

The median locks slot six

Slots	$1$ - $5$	$6$	$7$ - $11$
What the order allows	At most $6$	Exactly $6$	At least $6$
Smallest positive values, if repeats are allowed	$1,1,1,1,1$	$6$	$6,6,6,6,6$

This doesn’t answer anything yet. It shows what’s locked, so you can see which slots are still free to push.

Common mistake:

If the values must be distinct, you can’t use a number twice, so every $\le$ between slots becomes $<$ . When you need the smallest or largest values allowed, use consecutive integers. For example, three distinct positive integers can’t all be $1$ . The smallest they can be is $1$ , $2$ and $3$ .

Decide which way to push

Once the slots are set, ask what the question wants large or small, and which slots feed it.

To make a sum as large as possible, push the slots in it up, or make everything else as small as you can.
To make a sum as small as possible, push the slots in it down, or make everything else as large as you can.
To make the range small, pull the smallest and largest values toward each other while keeping the total. In the opening example, a range of $8$ left the total $4$ short of $126$ , so the range had to be at least $9$ .
To make the median as large as possible, try a value, add up the least the list could total with it, and compare that with the fixed total. If $7$ positive integers add up to $70$ , a median of $20$ fails, because slots $4$ through $7$ would each be at least $20$ , already $80$ . A fixed range can push the smallest values up too, so keep them as low as the range allows.

Here’s the catch. Whatever you push, the other slots have to make up the difference. A value that looks like the extreme isn’t the answer until the rest of the list can still reach the total, stay in order and follow every rule.

Use a complementary sum

Say $10$ values must add up to $50$ , and you want the $4$ greatest as large as possible. If the other $6$ add up to $20$ , the $4$ greatest get $30$ . Shrink those $6$ to a total of $14$ , and the $4$ greatest get $36$ . Every bit you take from the rest goes to the group you want.

In general, call the group you want large $B$ and everything else $C$ , the complement of $B$ . If all $n$ values have a fixed total $T$ , then

\operatorname{sum}(B)=T-\operatorname{sum}(C).

So to make $B$ large, make $C$ small:

\boxed{\text{maximize }B\text{ by minimizing its complement }C.}

This is most useful when $B$ is the greatest values. Then $C$ holds the smaller values, and the median often sets how small some of them can be.

Check your understanding:

A set of $13$ positive integers has mean $7$ and median $5$ . The $4$ greatest values form group B. What is the greatest possible mean of B?

Common mistake:

It’s tempting to start by making the largest values huge. But that can break the total, or leave no values that work on the median’s side of the list. If you get stuck, back up: turn the mean into a total, mark the locked slots, then decide which leftover sum to make small or large.

Example: Maximize the mean of the greatest values

Watch how much of the work happens before you touch the four greatest values.

Worked example

Data set A consists of $11$ positive integers with a mean of $9$ and a median of $6$ . Data set B consists of the $4$ greatest integers in data set A.

Which choice is the maximum possible value of the mean of data set B?

A
$19$
B
$20$
C
$\frac{41}{2}$
D
$22$

Step 1

Turn the conditions into slots

Eleven values with a mean of $9$ add up to

11(9)=99.

Write them in order:

x_1\le x_2\le\cdots\le x_{11}.

With $11$ values, slot $6$ is the middle, so it holds the median:

x_6=6.

Step 2

Split off the four greatest

The four greatest values sit in slots $8$ through $11$ . Their complement is slots $1$ through $7$ :

\underbrace{x_1+\cdots+x_7}_{\text{complement}} + \underbrace{x_8+\cdots+x_{11}}_{\text{target}} =99.

The total is fixed, so the smaller you make slots $1$ through $7$ , the more is left for the four greatest.

Step 3

Make the first seven values as small as allowed

The values only have to be positive, so slots $1$ through $5$ can each be $1$ . Slot $6$ is locked at $6$ , and slot $7$ can’t be less than the median, so it’s at least $6$ :

x_1+\cdots+x_7 \ge 1+1+1+1+1+6+6=17.

That leaves at most

99-17=82

for the four greatest, so their mean is at most

\frac{82}{4}=\frac{41}{2}.

Step 4

Build a list that reaches the bound

So far you know the mean can’t go above $\frac{41}{2}$ . Now show that a list gets there. Keep slots $1$ through $10$ as small as allowed, five $1$ s and five $6$ s, and give everything left to slot $11$ : $99-35=64$ .

1,\ 1,\ 1,\ 1,\ 1,\ 6,\ 6,\ 6,\ 6,\ 6,\ 64.

It has $11$ positive integers, its total is

5+30+64=99,

and its median is $6$ . Its four greatest values are $6,6,6,64$ , with mean

\frac{6+6+6+64}{4}=\frac{82}{4}=\frac{41}{2}.

The list reaches the bound, so the answer is C.

Check your understanding:

If the $11$ positive integers in the example also had to be distinct, what would be the smallest possible sum of the first seven values?

Common mistake:

After step 3, it’s tempting to pick $\frac{41}{2}$ and move on. But the inequality only shows the mean can’t go higher. It doesn’t show that any list gets there. Finish by writing a complete list in order and checking every condition.

Same method, new target: the median

Shrinking the complement works when you want the greatest values large. To make the median large, you need a different finish, but you still start from the slots.

Suppose a data set has $9$ positive integers, mean $11$ , and range $14$ . You want the greatest possible median.

The total is

9(11)=99.

Could the median be $18$ or more? Look at what that forces. The largest value is at least the median, so it would be at least $18$ . With a range of $14$ , the smallest value would then be at least

18-14=4.

So the first four values would each be at least $4$ , and the last five, from the median up, would each be at least $18$ . The smallest total you could get is

4(4)+5(18)=106,

which is more than $99$ . So the median can’t be $18$ or more.

Now build a list with median $17$ . Put the median and the four values above it at $17$ , which uses $5(17)=85$ . That leaves $99-85=14$ for the first four. The range makes the smallest value $17-14=3$ , and $3+3+3+5=14$ :

3,\ 3,\ 3,\ 5,\ 17,\ 17,\ 17,\ 17,\ 17.

Its total is $99$ , its range is $17-3=14$ , and its median is $17$ . So the greatest possible median is

\boxed{17}.

The target changed, but the moves didn’t: turn the conditions into slots, rule out anything better, then build and check the list that reaches the limit.

Check your understanding:

The list above has median $17$ . Why doesn’t that list alone prove that $17$ is the greatest possible median?

Verify the final list

Before you pick an answer, check your list against the question, not against what you meant to write.

Check the finished list

Check	Ask yourself
Count	Are there exactly $n$ values?
Order	Are the values written from least to greatest?
Number rules	Is every value an integer? If the question asks, is each one positive, within the bounds and different from the rest?
Mean	Does the total equal $n$ times the given mean?
Median	Is the right value sitting in the middle slot?
Range	Does the largest value minus the smallest equal the given range, or the one you’re claiming?
The question	Does the group or statistic the question asks about actually reach your answer?

Do these by hand. Desmos can add up a finished list, but it can’t tell you which slots to squeeze, which inequality proves nothing does better, or whether distinct values change the best arrangement.

Practice problems

These three match what you’ve seen: the smallest range, the largest mean of the greatest values, and the largest median. The second adds distinct values and a cap.

Find the smallest range

Practice problem

A data set consists of $11$ integers. Its mean is $13$ , and its median is $9$ .

What is the minimum possible range of the data set?

Calculator loads as you approach

Start from the slots and the total. The calculator can add up your finished list.

Distinct values with a cap

Practice problem

Data set A consists of $14$ distinct integers, each from $1$ through $25$ , inclusive. The mean of data set A is $15$ . Data set B consists of the $6$ greatest integers in data set A.

What is the maximum possible value of

\operatorname{mean}(B)-\operatorname{mean}(A)?

Calculator loads as you approach

Pick the six greatest allowed values first. The calculator can total the other eight or check your finished list.

Find the greatest median

Practice problem

A data set consists of $7$ positive integers. Its mean is $10$ , and its range is $12$ .

What is the greatest possible median of the data set?

Your answer

Calculator loads as you approach

Start with the range: a big median pushes the smallest value up too. The calculator can check your final total.

Finish the lesson

3 practice examples left

Finish the remaining questions correctly to complete this lesson.

Quick recap

Turn a fixed mean into a fixed total before you place any values.
Write the values in order as slots, lock the median slot, and tie the end slots together with the range.
Keep the integer, positive, distinct and bound rules in view from the start.
To make the greatest values add up to as much as possible, make the rest add up to as little as possible.
To shrink the range or raise the median, test a better value and show the total can’t fit.
Bound it, then build it: the bound shows you can’t do better, and a complete list shows the value can happen.
Check the count, order, rules, total, median, range and what the question asks for.
Work by hand, and use a calculator only to check the arithmetic once the list is decided.

Next lesson

Interpret scatterplots

Move from constructing one-variable data to interpreting direction, strength, form, clusters, and outliers in paired data.

Start next lesson

Practice

Practice this lesson

31 SAT questions use what this lesson teaches. Practice a few in a study session at the difficulty you choose.

Start practice