Lesson progress
0 / 10
Lesson 23.2›Chapter 23 · The Pigeonhole Principle
Lesson 23.3 · Number grouping

Build the Largest Safe Set and Prove It Is Best

A maximum problem needs two certificates: a construction that reaches the proposed size and a drawer argument that makes every larger size impossible.

Construction + upper boundDivisibility chainsFixed-gap chainsEqual-sum constructions
Your progress is saved in this browser.
The maximum-proof pattern

All sets on this page use distinct values, each at most once; all range endpoints are included. A divisibility conflict means one of two different selected values divides the other exactly. “I found a large example” is only half a proof.

1. Construction

Build a legal set of size M.

maximum ≥ M

2. Upper bound

Partition all candidates into M drawers so a legal set uses at most one object from each.

maximum ≤ M
maximum ≥ M and maximum ≤ M  ⟹  maximum = M
1

Give a maximum proof both certificates

Construction proves “at least”; drawers prove “at most.”
Not complete

Certificate A

A legal set with 33 elements proves that the maximum is at least 33.

Certificate B

A partition into 33 drawers, with at most one legal choice per drawer, proves that the maximum is at most 33.

Checkpoint

Need a hint? Start here

A construction and an upper bound answer different questions.

Show the reasoning

A safe set of size 33 proves the maximum is at least 33. A proof that every safe set has size at most 33 makes the maximum exactly 33.

2

Build the worked example’s safe set

Choose the 33 odd numbers from 35 through 99.
Not complete

Move the starting odd number

Starting value35
Selected33
Divisibility conflicts0
Three times the least105
Why 35 works: any larger odd multiple of a selected number is at least three times that number. Since 3×35=105>99, no selected number can divide another selected number.

Selected odd numbers

Checkpoint for the fixed set35,37,…,99 (even if you changed the slider)

Need a hint? Start here

For odd numbers, a larger divisible value is at least triple the smaller.

Show the reasoning

Select the 33 odd values from 35 to 99. Their smallest possible odd multiple is 3×35=105, outside the range. Thus the selection has no divisibility conflicts.

3

Build the worked example’s 33-drawer upper bound

Eleven divisibility chains plus twenty-two singleton drawers.
Not complete

Eleven chain drawers

Any two numbers inside one chain have a divisibility relationship. A safe set can choose at most one value from each chain.

Twenty-two singleton drawers

Count the partition

Numbers in chains28
Chain drawers11
Singleton drawers22
Total drawers33
The worked example grouping is not unique. It only needs to cover all 50 odd numbers and make every multi-number drawer internally unsafe.

Upper-bound checkpoint

Need a hint? Start here

Each divisibility chain allows at most one selection.

Show the reasoning

Eleven chains contain 28 of the 50 odd values. The 22 remaining singleton drawers give 33 drawers in total. Every safe set uses at most one per drawer.

4

Join the two halves into a complete proof

Thirty-three is attainable; thirty-four is impossible.
Not complete

Try a proposed selection size

Forced conflict34 objects in 33 drawers force two into one drawer.

The completed original proof

construction of size 33 ⟹ maximum ≥ 33
33 drawers ⟹ maximum ≤ 33
therefore maximum = 33

Proof checkpoint

Need a hint? Start here

Do not stop after finding one good example.

Show the reasoning

The construction reaches 33. The 33-drawer upper bound rules out 34. Together these prove both parts of an exact maximum.

5

Complete Guided Practice 2 with fixed-gap chains

From the integers1through1989, choose as many distinct values as possible without two differing by exactly4. A difference of8or12is allowed.
Not complete
Chain idea: values with the same remainder modulo 4 form a path whose neighbors differ by 4. From each chain, choose alternating positions.
ChainFirst valuesLengthSafe alternating choicesLast selected value
Chains4
Candidate numbers1989
Maximum safe size996
Next size forces a gap-4 pair997
Why alternating is best: In each step-4 chain, pair position 1 with 2, position 3 with 4, and so on. Each pair consists of numbers differing by 4, so at most one can be chosen. An unpaired last position allows one more. Therefore a chain of length L allows at most ⌈L/2⌉ choices. Alternating positions achieves that bound. The four lengths 498, 497, 497, 497 each allow 249 choices: 4 × 249 = 996. Here only neighboring positions conflict; in a divisibility chain, every pair conflicts.

Guided-practice checkpoint

Need a hint? Start here

Pair neighboring positions within each step-4 chain.

Show the reasoning

The chain lengths are 498,497,497,497. Each pair of adjacent positions allows at most one choice; an unpaired end allows one extra. Each chain contributes 249, giving 996. Alternating achieves it.

6

Use a general fixed-gap safe-set laboratory

Every residue chain is a path; alternate along each path.
Not complete

Choose a range and forbidden difference

Nonempty chains5
Total values30
Maximum safe set15
Guarantee threshold16

One maximum construction

Chain startRemainderLengthChoosePreview

Laboratory checkpoint

Need a hint? Start here

Separate values by their remainder modulo the forbidden difference.

Show the reasoning

For 1–30 and difference 5 there are five chains of length 6. Three alternating choices per chain give 15. The same pairing proof gives 996 for the larger example.

7

Force a divisibility pair with odd-part chains

Every positive integer is an odd number times a power of 2.
Not complete

General interval 1 through N

Odd-part drawers40
Maximum safe size40
Selections that force divisibility41
Top-half construction starts41
The numbers greater than N/2 form a safe construction: if one divided another, the larger would be at least twice the smaller and would exceed N.

Odd-part chain drawers

Test 23 transfer checkpoint

Need a hint? Start here

Repeatedly divide by 2 until an odd number remains.

Show the reasoning

All values with the same odd part form a divisibility chain. For 1–80 there are 40 chains, so 41 force a pair. For 1–100, 51 force a pair; the upper half of either interval is a largest safe set.

8

Use constructions to make equal-sum groups

The worked example’s “Divide It” puzzles reinforce the construction half of a proof.
Not complete

Use each number exactly once. Split 1–16 into four groups of four numbers each, each sum 34. Split 1–15 into five groups of three numbers each, each sum 24. Both the group size and the sum must match.

Divide 1–16 into four groups

Every group must total 34.

Divide 1–15 into five groups

Every group must total 24.

Construction lesson: a successful grouping proves that a target is achievable. An optimization problem still needs a separate upper-bound or lower-bound argument.

Construction checkpoint

Need a hint? Start here

Check group size and group sum separately.

Show the reasoning

The sum of 1–16 is 136, so four groups need sum 34 and four members each. The sum of 1–15 is 120, so five groups need sum 24 and three members each. Complementary numbers help balance the groups. After checking your own construction, the separate worked review provides examples without changing your boards.

Try a fresh problem

Choose from 1–24 while avoiding a difference of 6. What is the largest safe set size?

This fresh problem has its own checkpoint. Your written explanation is saved for comparison and is not automatically graded.

Worked explanation for the fresh problem

The six step-6 chains each have four positions. Each allows at most two choices, giving 12. Choose positions 1 and 3 in every chain, for example 1–6 and 13–18.

9

Safe-set proof workshop

Correct all eight to complete the workshop.
Not complete
Not graded yet
Answer all eight, then grade your work.
Need a hint? Start here

Revisit the mission connected to each question.

Show the reasoning

Answers:at least M;at most M;35;33;28;996;41;34. A valid construction supplies a lower bound on the maximum; a partition into pairwise-conflicting drawers supplies an upper bound. For exact difference4, pair adjacent positions in each step-4chain.

10

Exit ticket and certificate

Correct all five answers and complete all ten missions to earn the certificate.
Not complete
Chapter 23 Achievement

Safe-Set Construction & Proof Architect

This certificate recognizes

A determined learner

for building extremal constructions, partitioning candidates into chains, and proving exact maximum safe-set sizes.

Lesson 23.3 completed

Need a hint? Start here

Solve each item without using the answer shown in an earlier example.

Show the reasoning

Answers:33;34;20;61;24. Four step-4chains in1–40each have10positions and permit5choices. In1–120there are60odd-part chains, so61force divisibility. The sum1+…+15=120divided into five equal groups gives24.