Lesson progress
0 / 10
Chapter 26›Lesson 26.6
Binary choices · exact quantities · original-aware bracket models

Design Exact-Quantity Boxes and Brackets with Binary Choices

Use each box as an on/off bit, prove the smallest possible number of boxes, avoid gaps in the reachable totals, and compare two different meanings of a tournament “bye.”

Grade 5 Olympiad10 interactive missionsWorks offlineAutosaves
Your answers and progress save automatically in this browser.
The design question

How can whole boxes make every requested total?

Each box has two states: take it or leave it. With n boxes there are at most 2^n subsets, including the empty subset. To supply every quantity from 0 through T, at least T+1 different totals are needed.

2^n ≥ T+1

Two reusable tests

w₁ ≤ 1,   w₂ ≤ 1+w₁,   w₃ ≤ 1+w₁+w₂,   …

Use positive whole-number box quantities, sorted from smallest to largest for this test. Each box can be taken at most once; boxes cannot be opened or split. After the smaller boxes cover every total from 0 through S, the next box must be at most S+1.

1, 2, 4, 8, … creates the widest gap-free range.
1
Binary-choice foundation

Turn whole boxes into on/off bits

Not complete
One box, one bit: 0 means leave the box; 1 means take it.
five-bit mask10111
selected total23
all subsets32
positive totals31
Bit-choice checkpoint.
Need a hint?

Each box has two choices, including the option to leave every box.

2
Lower-bound proof

Prove the minimum number of boxes

Not complete
required totals, including 0251
minimum boxes8
subsets with one fewer box128
subsets with enough boxes256
Why this is a proof: fewer boxes do not create enough subsets even before we worry about duplicate totals. So no clever rearrangement can beat this lower bound.
Minimum-box checkpoint.
Need a hint?

Count T+1 totals, including zero, then compare powers of two.

3
Gap-free invariant

Make every total without leaving a hole

Not complete
boxes8
sum of boxes250
continuous coverage0–250
first missing totalnone
If every total from 0 through S is covered, the next box must satisfy w ≤ S+1.
Coverage checkpoint.
Need a hint?

If smaller boxes cover 0 through S, the next box must be at most S+1.

4
Exercise 13

Pack 250 eggs into the fewest exact-choice boxes

Not complete
Why the final box leaves no gap

Without the 123-box, the first seven boxes cover 0–127. With it, the same choices cover 123–250. These intervals overlap at 123–127, so together they cover 0–250.

Each mask follows the box order displayed here, from left to right. Read the quantities above the bits; this order differs from the descending powers in Mission 1.

original task: place 250 eggs into as few boxes as possible so that every request from 1 through 250 can be met by taking whole boxes.
1, 2, 4, 8, 16, 32, 64, 123
request200
selected boxes4
mask
verified sum200
Both halves of optimality: seven boxes have only 2^7=128 subsets, fewer than the 251 required totals. The eight displayed boxes cover every total from 0 through 250.
250-egg checkpoint.
Need a hint?

The first seven boxes cover 0–127; the last adds 123 to that whole interval.

5
Test 26, Question 11

Scale the design to 500 eggs

Not complete
1, 2, 4, 8, 16, 32, 64, 128, 245

The first eight powers-of-two boxes cover every total through 255. The last box has 245 eggs, and 245≤256, so it overlaps the old range instead of creating a gap.

request373
selected boxes
mask
verified sum
500-egg checkpoint.
Need a hint?

The first eight boxes total 255; subtract from 500.

6
Test 26, Question 10 · general design laboratory

Build an optimal exact-quantity system for a target

Not complete

original target: 1000 bullets

1,2,4,8,16,32,64,128,256,489

Selected total: 743 · mask:

Design a new system

minimum boxes
first powers cover
adjusted box
final coverage
Construction rule: If T=1, use one box containing 1. Otherwise, use 1, 2, 4, …, 2n−2, then put the remaining amount into one adjusted box. If that adjusted box is no greater than one more than the earlier coverage, there is no gap.
Design checkpoint.
Need a hint?

The initial powers cover 2^(n−1)−1; the final box holds the remainder.

7
Worked example 7 and Guided Practice 7

Keep two tournament “bye” counts separate

Not complete
A four-slot bracket with three players
First pair: Player A vs Player B → one winnerSecond pair: Player C vs empty slot → C advances without playingFinal: first-pair winner vs C

One empty first-round slot gives one bye in this fixed bracket. For 58 entrants in 64 slots, six empty slots are paired with players, giving six first-round byes. A different model pairs the remaining players anew each round: when the count is odd, exactly one player advances without playing. Then 58→29→15→8→4→2→1 gives one bye at 29 and one at 15: two bye occurrences in total.

Worked solution: subtract the number of entrants from the next power of two, write the difference in binary, and count its 1-bits. The worked example calls this number “bye person-times.”
Terminology clarification: in a standard fixed bracket, the number of empty first-round slots is the entire difference P-N. The worked example’s count is the total bye occurrences in the round-by-round model just described. It also equals the number of 1-bits in P−N. These are two different tournament arrangements, so their bye counts need not match.
next power of two P
standard empty slots P−N
binary difference
round-by-round byes
EntrantsNext bracketEmpty first-round slotsDifference in binaryRound-by-round byes
243256131101₂3
58646110₂2
233291001₂2
Tournament checkpoint.
Need a hint?

First find the entire gap; then count the powers of two in that gap.

8
Core design check · optional original reading

Justify a complete box design

Not complete
Optional: explore the Ten-Perfect Product solutions

This is a precomputed solution list, not a search running in your browser. To build it, enumerate distinct-digit factor pairs, group pairs with the same product, then keep pairs that together use all ten digits and satisfy the three inequalities.

Try verifying 230×76=184×95: check both products, all ten digits, and each inequality before inspecting another row.

Printed conditions: use the digits 0 through 9 exactly once across four natural numbers A,B,C,D, with A×B=C×D, A>C, A>B, and C>D. The worked example reports 210 arrangements.
original discrepancy disclosed: the worked example paragraph also prints 1380 as the smallest possible A. An exhaustive audit of the literal conditions finds 210 arrangements but includes 64 with a three-digit A; the smallest is 230. The maximum 9730 agrees with the worked example. The page preserves the printed conditions and does not silently remove those 64 cases.
all solutions210
three-digit A64
four-digit A146
A range under literal rules230–9730
1

Core design checkpoint: boxes 1, 2, 4, 8, 16.
Need a hint?

Use the lower bound and the gap rule together to justify a design.

9
Independent practice

Exact-choice design workshop

Not complete

Correct all eight answers to complete this workshop. Use positive whole-number box quantities; each box can be taken once or left, and cannot be opened. A powers-first design uses 1,2,4,… for all but the final box, which holds the remaining items. The required totals include zero.

Need a hint?

Answers: 6; 16; 8; 245; 489; 6; 2; 250. Six boxes have 64 subsets. The adjusted quantities are 500−255 and 1000−511. The fixed 64-slot bracket has 6 empty slots; pairing remaining players anew each round gives two byes. Adding 123 to coverage 0–127 adds coverage 123–250.

10
Mastery check

Exit ticket and certificate

Not complete
Need a hint?

Answers: 7; 123; 8; 2; 5. Seven boxes provide 128 subsets. Boxes 1,2,4 reach only 7 before the 9-box, leaving 8 missing. For 23 players paired anew each round: 23→12→6→3→2→1, with byes at 23 and 3. Five boxes can cover 0–31.

Optional reflection — not graded.