Star problems Advanced ← Back to chapter

Probability and Statistics: Star problems

Ten optional challenges to stretch your reasoning. Work on paper, use hints when you need them, and check the answer or full solution when you are ready. You can skip these problems and continue the course.

1 of 3 stars: Stretch
2 of 3 stars: Challenge
3 of 3 stars: Deep challenge

Stars indicate difficulty within this set.

0 of 10 completed

Progress saved in this browser.

Problem 1 of 10

Problem 1 Two order rules and a separation rule

Difficulty: 1 of 3 stars, Stretch

Six distinct cards numbered $1,2,3,4,5,6$ are placed in a row. How many arrangements have $1$ somewhere to the left of $2$ , have $3$ somewhere to the left of $4$ , and do not place $1$ and $2$ next to each other? Explain why every division or multiplication in your count is valid.
1. Hint 1
  First count arrangements satisfying just the two left-to-right rules.
2. Hint 2
  Among those arrangements, forbidden neighbors can occur only as the ordered block $12$ . Treat this block as one object.
Answer

$120$ arrangements.

Full solution

There are $6!=720$ unrestricted arrangements.
Swapping the labels $1$ and $2$ pairs every arrangement with one having the opposite order of that pair.
Thus exactly half have $1$ before $2$ .
Within that half, swapping $3$ and $4$ preserves the first condition and reverses the second, so exactly half also have $3$ before $4$ .
This gives $720/4=180$ .

Now remove the arrangements in which $1$ and $2$ are neighbors.
Since $1$ must precede $2$ , they form the single ordered block $12$ .
Together with $3,4,5,6$ this gives five distinct objects.
Exactly half of their $5!$ orders have $3$ before $4$ , by the same label-swap pairing.
There are therefore $5!/2=60$ forbidden arrangements.

The desired count is
$180-60=120.$
Treating adjacency as an unordered block would incorrectly double the subtracted count: the block $21$ was never among the $180$ arrangements.
The pairing explanations also avoid assuming that unrelated-looking restrictions are automatically independent.

Answer

$120$ arrangements.

Key idea

A symmetry count needs a bijection that preserves every restriction already imposed.
Problem 1: Mark complete
Problem 2 Evidence from an unmarked bag

Difficulty: 1 of 3 stars, Stretch

Bag $A$ contains four red and two blue counters; bag $B$ contains two red and four blue counters. A fair coin selects a bag, and then two counters are drawn uniformly at random from that same bag without replacement. Both drawn counters are red.

(a) Given this evidence, what is the probability that bag $A$ was selected?

(b) Repeat the experiment with replacement: return the first counter before an independent uniform second draw. If both are red, what is the new conditional probability? Explain why the two answers differ.
1. Hint 1
  Compute the probability of two reds under each bag separately, then include the equal bag-selection probabilities.
2. Hint 2
  Conditioning keeps only the two-red outcomes. The relative likelihoods of that evidence, rather than the original equal chances of the bags, determine the answer.
Answer

(a) $6/7$ . (b) $4/5$ .

Full solution

Without replacement, the two-red probabilities are $(4/6)(3/5)=2/5$ from $A$ and $(2/6)(1/5)=1/15$ from $B$ .
After including the fair bag choice, the probabilities of the joint events are $1/5$ and $1/30$ .
The probability of the evidence is their sum, $7/30$ .
Therefore

$P(A\mid\text{two reds})=\frac{1/5}{7/30}=\frac67.$

With replacement, the second draw has the original color probabilities and is independent of the first, conditional on the chosen bag.
The likelihoods are now $(4/6)^2=4/9$ and
$(2/6)^2=1/9.$
Including the equal bag weights and conditioning gives
$(4/9)/(4/9+1/9)=4/5.$

Without replacement, a first red removes half of bag $B$ 's red counters but only one quarter of bag $A$ 's.
A second red is consequently stronger evidence for $A$ in that experiment: the likelihood ratio is $6:1$ instead of $4:1$ .
Equal prior chances do not remain equal after evidence is observed.

Answer

(a) $6/7$ . (b) $4/5$ .

Key idea

Conditional probabilities depend on how evidence was generated; replacement changes the likelihood even when the bag contents stay the same.
Problem 2: Mark complete
Problem 3 An impossible statistical report

Difficulty: 1 of 3 stars, Stretch

A report claims that five real measurements have mean $12$ , population variance $8$ , and include the value $18$ . Here population variance means the sum of the squared deviations from the mean divided by $5$ .

Prove that the report is impossible. If the mean $12$ and the measurement $18$ are retained, find the least possible population variance and describe every list attaining it.
1. Hint 1
  The other four measurements have a forced sum and hence a forced mean.
2. Hint 2
  Write the other measurements as $10.5+d_1,\ldots,10.5+d_4$ , where $d_1+\cdots+d_4=0$ . Expand their squared deviations from $12$ .
Answer

The population variance must be at least $9$ . Equality occurs only for the list $18,10.5,10.5,10.5,10.5$ , in any order; variance $8$ is impossible.

Full solution

The five measurements sum to $60$ .
After one occurrence of $18$ is set aside, the other four sum to $42$ , so their mean is $10.5$ .
Write them as $10.5+d_i$ for $i=1,2,3,4$ , with
$\sum d_i=0.$

The total squared deviation from $12$ is

$6^2+\sum_{i=1}^4(d_i-1.5)^2=36+9+\sum_{i=1}^4d_i^2\ge45.$

Dividing by $5$ gives population variance at least $9$ , contradicting the reported value $8$ .
Notice that the single value $18$ contributes only $36$ to the squared-deviation total.
Comparing $36$ with the claimed total $40$ would miss the contradiction: the remaining measurements must collectively balance its positive deviation and cannot all equal $12$ .

Equality in the derived bound requires $d_i=0$ for all four remaining measurements.
Thus they must all be $10.5$ .
This list has mean $12$ and variance $45/5=9$ , proving both attainability and the complete equality classification.

Answer

The population variance must be at least $9$ . Equality occurs only for the list $18,10.5,10.5,10.5,10.5$ , in any order; variance $8$ is impossible.

Key idea

A reported mean constrains the remaining deviations; an extreme observation forces spread elsewhere in the data.
Problem 3: Mark complete
Problem 4 Arranging a repeated-letter code

Difficulty: 2 of 3 stars, Challenge

A code uses exactly three copies of $A$ , two copies of $B$ , and two copies of $C$ . Copies of the same letter are indistinguishable. How many distinct seven-letter codes have no adjacent $A$ 's and no adjacent $B$ 's? Adjacent $C$ 's are allowed.

If a code is selected uniformly from all distinct arrangements of these seven letters, what is the probability that it satisfies both restrictions? Explain why your construction counts each allowed code once.
1. Hint 1
  Delete the three $A$ 's from an allowed code. What four-letter skeleton remains?
2. Hint 2
  Insert the $A$ 's into three different gaps of a $BBCC$ skeleton. If the two $B$ 's touch in the skeleton, their intervening gap must be chosen.
Answer

$48$ allowed codes, with probability $8/35$ .

Full solution

First arrange the non- $A$ letters $B,B,C,C$ .
There are $4!/(2!2!)=6$ skeletons, each with five gaps: before the first letter, between successive letters, and after the last.
To avoid adjacent $A$ 's, insert one $A$ into each of three distinct gaps.

Three skeletons have adjacent $B$ 's: $BBCC,CBBC,CCBB$ .
For each, the gap between the two $B$ 's must receive an $A$ .
The other two occupied gaps can be any two of the remaining four, giving $\binom42=6$ choices.
In the other three skeletons the $B$ 's are already separated, so any three of the five gaps work: $\binom53=10$ choices.

There are therefore $3\cdot6+3\cdot10=48$ allowed codes.
Deleting every $A$ from a finished code recovers its unique skeleton, and the positions of the deleted letters recover its occupied gaps.
This proves that the construction neither duplicates nor omits an allowed code.

All distinct codes number
$7!/(3!2!2!)=210.$
Under the stated uniform selection, the probability is
$48/210=8/35.$
One should divide by $210$ , not by $7!$ , because identical-letter permutations are not different outcomes.

Answer

$48$ allowed codes, with probability $8/35$ .

Key idea

Deleting one letter type can expose a smaller skeleton whose gaps encode the remaining restrictions.
Problem 4: Mark complete
Problem 5 Reading until the order breaks

Difficulty: 2 of 3 stars, Challenge

Eight distinct cards numbered $1$ through $8$ are shuffled uniformly among all $8!$ orders. Read cards from left to right, stopping as soon as a newly read number is smaller than the immediately preceding number. If this never happens, stop after reading all eight cards. Let $T$ be the number of cards read, including the card that causes a stop.

(a) What is the probability that the first decrease occurs on the fourth card?

(b) Find the exact mean value of $T$ , meaning $\sum_{t=2}^8tP(T=t)$ . Explain your method without listing all shuffles.
1. Hint 1
  For any $k$ chosen positions at the beginning, every relative order of their distinct values is equally likely. How often are the first $k$ increasing?
2. Hint 2
  A shuffle with $T=t$ contributes $1$ to each of the counts $T\ge1,\ldots,T\ge t$ . Thus the mean equals $\sum_{k=1}^8P(T\ge k)$ .
Answer

(a) $1/8$ . (b) $\displaystyle\sum_{j=0}^7\frac1{j!}=\frac{685}{252}$ .

Full solution

The first $k$ cards are increasing with probability $1/k!$ : for every chosen set of $k$ values, exactly one of its $k!$ relative orders is increasing, and all are equally likely.
This statement does not assert that comparisons of neighboring cards are independent.

The first decrease occurs on card four precisely when the first three cards are increasing but the first four are not.
Since the latter increasing event is contained in the former, its probability is
$1/3!-1/4!=1/8.$

For the mean, a fixed outcome with $T=t$ can be counted as $t$ indicators: one each for
$T\ge1,\ldots,T\ge t.$
Averaging this finite identity over all equally likely shuffles gives
$\operatorname{mean}(T)=\sum_{k=1}^8P(T\ge k).$
The first two probabilities are $1$ .
For $3\le k\le8$ , reaching card $k$ means that the first $k-1$ cards were increasing, so the probability is $1/(k-1)!$ .

Consequently the mean is
$1+1+1/2!+\cdots+1/7!=685/252.$
Both a last-card decrease and a completely increasing shuffle have $T=8$ ; the reaching-card calculation correctly includes both without confusing their stopping reasons.

Answer

(a) $1/8$ . (b) $\displaystyle\sum_{j=0}^7\frac1{j!}=\frac{685}{252}$ .

Key idea

For a stopping count, averaging how many stages are reached can be simpler than finding every exact stopping probability.
Problem 5: Mark complete
Problem 6 Combining and adjusting two groups

Difficulty: 2 of 3 stars, Challenge

Group $A$ has $20$ real measurements with mean $70$ and population variance $100$ . Group $B$ has $30$ real measurements with mean $80$ and population variance $64$ . Population variances use the group size as the divisor.

(a) Find the mean and population variance of the combined $50$ measurements.

(b) Add a constant $a$ to every measurement in $A$ and a constant $b$ to every measurement in $B$ , while keeping the combined mean unchanged. Find the least possible combined population variance and all pairs $(a,b)$ attaining it. Explain why averaging the two given variances is insufficient.
1. Hint 1
  For each group, expand its deviations from the combined mean as deviations from its own mean plus a constant.
2. Hint 2
  The deviations within each group add to zero. The combined squared-deviation total splits into fixed within-group terms and terms measuring the two group means' distances from the overall mean.
Answer

(a) Mean $76$ and population variance $512/5$ . (b) Minimum $392/5$ , attained only at $(a,b)=(6,-4)$ .

Full solution

The combined mean is
$(20\cdot70+30\cdot80)/50=76.$
For a group of size $n$ , mean $m$ , and population variance $v$ , expanding around $76$ gives

$\sum (x_i-76)^2=nv+n(m-76)^2,$

because the cross term contains
$\sum(x_i-m)=0.$
Thus the original combined variance is
$[20(100+36)+30(64+16)]/50=512/5.$
The weighted within-group contribution alone is $(20\cdot100+30\cdot64)/50=392/5$ ; the different group means add another $24$ .

After the shifts, keeping the combined mean requires $20a+30b=0$ .
Adding a constant does not change deviations from a group's own mean, so its own variance stays fixed.
The new combined variance is therefore

$\frac{392}{5}+\frac{20(a-6)^2+30(b+4)^2}{50}.$

The last numerator is a sum of nonnegative squares.
Its minimum is zero exactly when $a=6$ and $b=-4$ , and this pair satisfies $20a+30b=0$ .
Both adjusted group means then equal $76$ .
This proves the minimum and uniqueness.
An unweighted average ignores the unequal group sizes; even a weighted average misses the spread between their means.

Answer

(a) Mean $76$ and population variance $512/5$ . (b) Minimum $392/5$ , attained only at $(a,b)=(6,-4)$ .

Key idea

Pooled variance contains both variation within groups and variation between group means.
Problem 6: Mark complete
Problem 7 Which distribution has the larger upper tail?

Difficulty: 2 of 3 stars, Challenge

Two real-valued performance measurements are modeled as normal: $X$ has mean $70$ and standard deviation $8$ , and $Y$ has mean $74$ and standard deviation $4$ . Success means a measurement is at least a cutoff $c$ .

(a) Find all real $c$ for which $P(X\ge c)>P(Y\ge c)$ , and identify the equality cutoff.

(b) At $c=82$ , estimate both success probabilities. You may use $P(Z\ge1.5)\approx0.0668$ and $P(Z\ge2)\approx0.0228$ for a standard normal $Z$ . Its upper-tail probability is strictly decreasing in the cutoff.

(c) If only the stated means and standard deviations are known, construct two non-normal distributions with those same summaries for which the success-probability ranking at $82$ reverses. For a finite distribution, use probability-weighted means and variances.
1. Hint 1
  Convert the same cutoff into a standard normal input for each measurement and compare those inputs.
2. Hint 2
  For the counterexample, try two equally likely values for $X$ . For $Y$ , place some probability exactly at $82$ and choose one lower value and its probability to preserve both summaries.
Answer

(a) Exactly $c>78$ , with equality at $c=78$ ; $Y$ has the larger success probability for $c<78$ . (b) Approximately $0.0668$ for $X$ , $0.0228$ for $Y$ . (c) Let $X$ equal $62$ or $78$ with probability $1/2$ each; let $Y$ equal $72$ with probability $4/5$ and $82$ with probability $1/5$ .

Full solution

Under the normal models, the standardized cutoffs are $(c-70)/8$ and $(c-74)/4$ .
Since the same standard-normal upper-tail function is strictly decreasing, $X$ has the larger success probability exactly when

$\frac{c-70}{8}<\frac{c-74}{4},$

which simplifies to $c>78$ .
Equality holds exactly at $78$ , and the comparison reverses below it.
Thus the higher mean alone does not determine the chance of passing every possible cutoff.

At $82$ , the inputs are $1.5$ for $X$ and $2$ for $Y$ , giving the supplied estimates $0.0668$ and $0.0228$ .
The decimals are rounded normal-table values, not exact fractions.

For a counterexample without normality, take $X=62,78$ with equal probabilities.
Its mean is $70$ , its variance is $(64+64)/2=64$ , and
$P(X\ge82)=0.$
Take $Y=72$ with probability $4/5$ and $Y=82$ with probability $1/5$ .
Its mean is $74$ and its variance is $(4/5)\cdot4+(1/5)\cdot64=16$ , but
$P(Y\ge82)=1/5.$
The ranking has reversed while both summaries are preserved.
The endpoint counts in this discrete example, unlike a single point under a continuous normal model.

Answer

(a) Exactly $c>78$ , with equality at $c=78$ ; $Y$ has the larger success probability for $c<78$ . (b) Approximately $0.0668$ for $X$ , $0.0228$ for $Y$ . (c) Let $X$ equal $62$ or $78$ with probability $1/2$ each; let $Y$ equal $72$ with probability $4/5$ and $82$ with probability $1/5$ .

Key idea

Mean and standard deviation support a tail calculation only after a distributional model is justified.
Problem 7: Mark complete
Problem 8 Failures without an independence promise

Difficulty: 3 of 3 stars, Deep challenge

Three sensors are used on the same trial. Each sensor individually fails with probability $1/3$ . No independence assumption is made. Let $q$ be the probability that at least two sensors fail.

(a) Find the smallest and largest possible values of $q$ . Prove both bounds and describe joint failure patterns attaining each.

(b) Show that every value between your bounds can occur while all three individual failure probabilities remain $1/3$ .

(c) What would $q$ be if the three failures were mutually independent?
1. Hint 1
  Let $p_j$ be the probability of exactly $j$ failures. Count the total failure probability by sensors and by the number of failures in a trial.
2. Hint 2
  For an upper-bound construction, allow either no failures or exactly two. In the latter case, treat the three possible failing pairs symmetrically.
Answer

(a) $0\le q\le1/2$ , with both endpoints attainable. (b) Every $q$ in this interval is attainable. (c) Under mutual independence, $q=7/27$ .

Full solution

Let $p_j$ be the probability of exactly $j$ failures.
Summing the three individual failure probabilities counts a trial with $j$ failures $j$ times, so
$p_1+2p_2+3p_3=1.$
Since $q=p_2+p_3$ , it follows that $2q\le1$ , while probabilities give $q\ge0$ .
This argument uses no independence.

To attain $q=0$ , choose exactly one failing sensor uniformly among the three on every trial.
Each sensor fails with probability $1/3$ , and two never fail together.
To attain $q=1/2$ , use no failures with probability $1/2$ and choose each of the three failing pairs with probability $1/6$ .
Each sensor belongs to two pairs and again fails with probability $1/3$ .

For any target $q\in[0,1/2]$ , first choose the second construction with probability $2q$ and the first with probability $1-2q$ , using an auxiliary random choice.
Both constructions have the same individual failure probabilities, so their mixture does too.
Only the second can produce at least two failures, giving probability
$(2q)(1/2)=q.$

Under mutual independence, exactly two fail with probability $\binom32(1/3)^2(2/3)=2/9$ , and all three fail with probability $1/27$ .
Their sum is $7/27$ , one particular value within the full possible interval.

Answer

(a) $0\le q\le1/2$ , with both endpoints attainable. (b) Every $q$ in this interval is attainable. (c) Under mutual independence, $q=7/27$ .

Key idea

Individual probabilities do not determine joint behavior; bounds and explicit constructions reveal what dependence can change.
Problem 8: Mark complete
Problem 9 A fixed median with the least spread

Difficulty: 3 of 3 stars, Deep challenge

Five real numbers lie in $[0,10]$ , have mean $6$ , and have median $m$ . Repeated values are allowed, and the median is the third value after sorting.

(a) Find every possible value of $m$ .

(b) For each possible $m$ , find the least population variance and describe every data set attaining it. Your proof must respect the order restrictions imposed by the median.
1. Hint 1
  Write the values in order as $x_1\le x_2\le m\le x_4\le x_5$ and use their sum $30$ to bound $m$ .
2. Hint 2
  For $m\le6$ , at least three values are no larger than $m$ . Fix the sum $S$ of those three and bound the squared deviations of each group by the square of its group mean. Treat $m\ge6$ by using the last three values.
Answer

(a) $10/3\le m\le10$ . (b) The least variance is $\tfrac32(m-6)^2$ . The unique multiset attaining it consists of three copies of $m$ and two copies of $15-3m/2$ .

Full solution

For sorted values, the total is at most $3m+20$ and at least $3m$ .
Since it equals $30$ , necessity gives
$10/3\le m\le10.$
For every such $m$ , the list containing three $m$ 's and two copies of $n=15-3m/2$ lies in $[0,10]$ , has mean $6$ , and has median $m$ .
This proves sufficiency.

For the variance bound, recall that $r$ numbers with sum $S$ have squared deviations from $6$ totaling at least $(S-6r)^2/r$ .
This follows by expanding around their own mean $S/r$ ; equality requires all $r$ numbers equal.

If $m\le6$ , let
$S=x_1+x_2+m.$
Then
$S\le3m\le18.$
Applying the group bound to these three values and the other two gives total squared deviation at least

$\frac{(S-18)^2}{3}+\frac{(30-S-12)^2}{2}=\frac56(S-18)^2\ge\frac{15}{2}(m-6)^2.$

If $m\ge6$ , use $S=m+x_4+x_5\ge3m\ge18$ instead; the same expression and inequality follow.
Dividing by $5$ gives variance at least $\tfrac32(m-6)^2$ .
Equality forces $S=3m$ , the selected three values all equal to $m$ , and the other two equal to $15-3m/2$ .
The constructed list realizes these conditions, including $m=6$ , where all values are $6$ .

Answer

(a) $10/3\le m\le10$ . (b) The least variance is $\tfrac32(m-6)^2$ . The unique multiset attaining it consists of three copies of $m$ and two copies of $15-3m/2$ .

Key idea

An order statistic imposes active constraints on several data points, so variance minimization must respect groups on each side of it.
Problem 9: Mark complete
Problem 10 How many values can exceed a threshold?

Difficulty: 3 of 3 stars, Deep challenge

Twenty real scores in $[0,100]$ have mean $50$ and population variance $100$ .

(a) What is the largest possible number of scores that are at least $70$ ? Prove the bound and describe every list attaining it.

(b) More generally, let $n$ real values have mean $\mu$ and positive population variance $\sigma^2$ . For $t>0$ , prove that the fraction $p$ of values at least $\mu+t$ satisfies $p\le\sigma^2/(\sigma^2+t^2)$ . State the equality conditions, including any restriction needed for a finite list. No normal-distribution assumption is available.
1. Hint 1
  Using only squared deviations from $50$ wastes the information that the deviations sum to zero. Try squaring distances from a different center.
2. Hint 2
  For part (a), expand $\sum(x_i-45)^2$ . For part (b), use the shifted center $a=\mu-\sigma^2/t$ and compare every qualifying term with $(\mu+t-a)^2$ .
Answer

(a) At most $4$ scores; equality requires sixteen scores equal to $45$ and four equal to $70$ . (b) $p\le\sigma^2/(\sigma^2+t^2)$ ; equality requires only the values $\mu-\sigma^2/t$ and $\mu+t$ , with respective fractions $t^2/(\sigma^2+t^2)$ and $\sigma^2/(\sigma^2+t^2)$ , so both counts must be integers.

Full solution

For part (a), the mean makes $\sum(x_i-50)=0$ , and the variance gives
$\sum(x_i-50)^2=2000.$
Therefore

$\sum_{i=1}^{20}(x_i-45)^2=2000+20\cdot25=2500.$

Each score at least $70$ contributes at least $25^2=625$ , while all other terms are nonnegative.
There can be at most four such scores.
Equality requires every qualifying score to be exactly $70$ and all others to be exactly $45$ .
This list lies in the required interval and has mean $50$ and variance $100$ .

For the general result, set
$a=\mu-\sigma^2/t.$
Expanding around the mean yields
$\sum(x_i-a)^2=n[\sigma^2+(\mu-a)^2].$
Each of the $np$ qualifying values contributes at least $(\mu+t-a)^2$ , and the remaining terms are nonnegative.
Consequently

$p\le\frac{\sigma^2+\sigma^4/t^2}{(t+\sigma^2/t)^2}=\frac{\sigma^2}{\sigma^2+t^2}.$

Equality requires all qualifying values to be $\mu+t$ and all others to equal $a$ .
Balancing their deviations from $\mu$ gives exactly the stated fractions, and direct substitution gives variance $\sigma^2$ .
For a finite list, $n\sigma^2/(\sigma^2+t^2)$ must be an integer; when it is, the two-value construction proves attainability.
If it is not, the real-valued fraction bound still holds, but equality cannot occur.

Answer

(a) At most $4$ scores; equality requires sixteen scores equal to $45$ and four equal to $70$ . (b) $p\le\sigma^2/(\sigma^2+t^2)$ ; equality requires only the values $\mu-\sigma^2/t$ and $\mu+t$ , with respective fractions $t^2/(\sigma^2+t^2)$ and $\sigma^2/(\sigma^2+t^2)$ , so both counts must be integers.

Key idea

A carefully shifted square can combine mean and variance into a sharper tail bound than deviation squares alone.
Problem 10: Mark complete