Nonadjacent selections: gaps and circular cases

All lessons · Türkiye’s Olympiad route

Your goal: count selections with separation rules, explain a reversible change of positions, and decide when a row argument must change for a circle.

Study plan: two sessions of about 60–75 minutes, with additional time for the final proof challenges. In the first session, complete the diagnostic, four examples and their nearby tasks. In the second, attempt the written problems before opening hints. Revisit any solution-assisted problem on another day.

Preparation context: original combinatorics practice intended to support TÜBİTAK high-school mathematics first-stage preparation, with written-proof extensions. The released 2026 first-stage paper has 32 multiple-choice questions in 180 minutes. This lesson develops one method; it is not a full mock or an exact difficulty match.

Before you start: you should be comfortable choosing a subset, using combinations, applying the sum and product rules, and explaining a reversible correspondence. The gap-variable method briefly rebuilds the needed stars-and-bars idea.

Three questions before the new idea

Try these without a formula sheet. The explanations identify the prerequisite to repair if you get stuck.

Diagnostic 1

How many two-element subsets does {1,2,3,4,5,6} have? Does choosing 2 and then 5 create a different subset from choosing 5 and then 2?

Explanation and next step

There are 6 × 5 = 30 ordered choices of two different labels. Every two-element subset appears twice, in its two possible orders. Thus there are 30/2 = 15 subsets. Both orders in the question give {2,5}. If this distinction was unclear, revisit combinations before continuing.

Diagnostic 2

List all two-element subsets of {1,2,3,4,5} that contain no consecutive integers.

Explanation and next step

The complete list is {1,3}, {1,4}, {1,5}, {2,4}, {2,5}, {3,5}: six subsets. To avoid omissions, group them by their smaller element. A smaller element of 4 or 5 leaves no possible larger element. If you counted {3,1} again, return to Diagnostic 1; if you missed a pair, practise organising cases by a uniquely determined feature.

Diagnostic 3

Six positions are labelled 1 through 6 in order. Is {1,6} a nonadjacent selection in a row? What changes if the same labels lie in this clockwise order on a circle?

Explanation and next step

In a row, positions 1 and 6 are not neighbours, so the selection is valid. In a circle, 6 is joined back to 1, so it is invalid. The labels remain fixed in both models: selecting {1,3} and selecting {2,4} are different choices. The issue here is the extra adjacency, not a division for rotations.

Name the objects before counting

$A$ row of n labelled positions means 1,2,…,n, with only consecutive labels adjacent. A selection is a subset: its members are distinct and their order of selection does not matter. A nonadjacent selection never includes both i and i + 1.

We write C(n,k), read “n choose k”, for the number of k-element subsets of an n-element set. For example, C(6,2) = 15. For 0 ≤ k ≤ n, it can be computed as n!/[k!(n − k)!], where n! = 1 × 2 × ⋯ × n and 0! = 1. The reason for the denominator k! is that each subset has k! possible orders. There is one empty subset, so C(n,0) = 1. For a nonnegative integer n, set C(n,k) = 0 when k < 0 or k > n. We will not use this notation with a negative first argument.

Keep two questions separate: Can such a selection exist? and How many exist? If k ≥ 1 positions are selected in a row, the k − 1 internal spaces need at least one unselected position each. Thus n ≥ k + (k − 1) = 2k − 1 is necessary. It is also sufficient: choose 1,3,…,2k − 1. Empty selections need no gap rule.

The gap-removal bijection

Why does an ordinary combination count fail? Choosing k arbitrary positions allows neighbours. Instead, remove the empty space that every valid selection is already forced to contain. The remaining freedom is an ordinary subset choice.

Write a valid selection in increasing order as a₁ < a₂ < ⋯ < aₖ. Nonadjacency says aᵢ₊₁ ≥ aᵢ + 2. Define the compressed positions by

bᵢ = aᵢ − (i − 1), for i = 1,2,…,k.

The first selected position moves zero places, the second moves one, the third moves two, and so on. We remove one compulsory space before each selected position after the first. For example, the selection 2,5,8,12 becomes 2,4,6,9.

1. The new labels are valid. The difference bᵢ₊₁ − bᵢ equals aᵢ₊₁ − aᵢ − 1, which is at least 1. Thus the b-values are strictly increasing. Also b₁ ≥ 1 and bₖ ≤ n − k + 1. They form a k-element subset of {1,…,n − k + 1}.
2. Every new subset can be expanded. Start with any increasing b₁,…,bₖ in that shorter row and put aᵢ = bᵢ + (i − 1). Then aᵢ₊₁ − aᵢ ≥ 2, a₁ ≥ 1 and aₖ ≤ n. The expanded selection obeys every original rule.
3. Nothing is duplicated or lost. Subtracting i − 1 and then adding it returns the original label, and the reverse order also returns the original label. These maps are inverses. That is why this is a bijection, rather than just a plausible picture.

Consequently, for integers k ≥ 1 and n ≥ 2k − 1, the number is

R(n,k) = C(n − k + 1,k).

Here R(n,k) names the number of nonadjacent k-element selections from a row of length n. We also use R(n,0) = 1 for every n ≥ 0, and R(n,k) = 0 if k < 0 or k is too large to fit. In particular, R(0,0) = 1 and R(0,k) = 0 for k ≥ 1. These conventions let us discuss an empty remaining interval without inventing a position.

Worked example 1. Compress a selection, then reverse it

How many four-element subsets of {1,2,…,12} contain no consecutive integers?

Sort the four selected labels and subtract 0,1,2,3 respectively. By the proved bijection, we obtain an arbitrary four-element subset of {1,…,9}. Therefore the answer is C(9,4) = (9 × 8 × 7 × 6)/(4 × 3 × 2 × 1) = 126.

For a concrete check, 2,5,8,12 compresses to 2,4,6,9. Expanding 2,4,6,9 gives back 2,5,8,12. The example illustrates the map; the inverse argument above proves it works for every permitted subset.

Your turn 1

Count the nonadjacent three-element selections from {1,…,10}. Give the compression and its inverse, not only a number.

Compare with a full solution

Send (a₁,a₂,a₃) to (a₁,a₂ − 1,a₃ − 2). The result is a three-element subset of {1,…,8}. Conversely add 0,1,2 to its increasing entries. Successive differences increase by 1, so they become at least 2, and the last label is at most 10. These operations are inverse. The count is C(8,3) = 56.

A wider gap changes the shift

Suppose at least d unselected positions are required between consecutive selected positions, where d ≥ 1 is an integer. Then aᵢ₊₁ − aᵢ ≥ d + 1. Replace the earlier shift by bᵢ = aᵢ − d(i − 1). The difference bᵢ₊₁ − bᵢ is at least 1, and the largest possible b-value is n − d(k − 1). Adding d(i − 1) reverses the map and restores the required separation.

For k ≥ 1, such a selection exists exactly when n ≥ k + d(k − 1). In that range, its count is C(n − d(k − 1),k). Below that range, the answer is zero. Notice that a row has only k − 1 compulsory internal gaps: it has no rule forcing empty positions before the first choice or after the last unless the problem says so.

Worked example 2. Reserve two spaces, not one

Four positions are selected from a row labelled 1 through 14. At least two unselected positions must lie between successive selected positions. How many selections are possible?

The required difference is at least 3. Compress the increasing selected labels by subtracting 0,2,4,6. They become four distinct labels in {1,…,8}, and adding those amounts reverses the process. The answer is C(8,4) = 70.

The condition is attainable, for example with 1,4,7,10. Subtracting only 0,1,2,3 would enforce only one empty space; the shift must match the stated minimum.

Your turn 2

Three positions are selected from a row of 13. Positions 1 and 13 must be unselected, and at least two unselected positions must lie between consecutive selections. Count the choices.

Compare with a full solution

All selections lie in positions 2 through 12, a row of length 11. Relabelling these positions 1 through 11 preserves their distances; this is a whole consecutive interval. For three choices with two compulsory spaces in each internal gap, compress by 0,2,4. The count is C(11 − 4,3) = C(7,3) = 35. The unselected endpoints are already outside that interval, so they should not be subtracted again.

Fixed labels: remove their neighbours, then keep the pieces

If a particular position is selected, its neighbours are forced to be unselected. The remaining eligible positions may form two or more separate intervals. Do not join these intervals into a new row. Positions on opposite sides of a forced gap can both be selected. Joining the intervals would invent an adjacency that the original row does not have.

If two remaining intervals have lengths L and M, and you need r further selections, decide how many, say t, are in the left interval. There are R(L,t) choices on the left and R(M,r − t) on the right. Every left choice can be combined with every right choice, so multiply. Then add over all possible t. Each final selection has one definite left-hand count t, so different cases do not overlap.

Worked example 3. A required middle position splits the row

Choose five nonadjacent positions from 1 through 15, with position 8 required to be selected. How many choices are there?

Position 8 is already one of the five choices; positions 7 and 9 cannot be chosen. We need four further choices from 1–6 and 10–15, two rows of length 6. A length-6 row has R(6,0) = 1, R(6,1) = 6, R(6,2) = C(5,2) = 10 and R(6,3) = C(4,3) = 4; four choices cannot fit.

If t choices are on the left, only t = 1,2,3 work. For t = 1, the count is 6 × 4 = 24. For t = 2, it is 10 × 10 = 100. For t = 3, it is 4 × 6 = 24. These disjoint cases give 24 + 100 + 24 = 148.

Positions 6 and 10 may both be chosen: the actual unselected positions 7 and 9 separate them from the required position 8. Compressing both remaining intervals into a single length-12 row would incorrectly make 6 and 10 neighbours.

Your turn 3

Choose four nonadjacent positions from 1 through 11, with position 6 required. Count the choices.

Compare with a full solution

Positions 5 and 7 are forbidden, leaving rows 1–4 and 8–11. Three further choices are needed. A length-4 row can supply at most two; it has R(4,1) = 4 and R(4,2) = C(3,2) = 3. Thus the split must be 1 + 2 or 2 + 1. Their counts are 4 × 3 and 3 × 4, giving 24. The left count uniquely identifies the case, and every counted choice obeys the original adjacency rule.

A circle has one more adjacency

Now place labels 1 through n clockwise on a circle, with n ≥ 3. Neighbours are consecutive labels, and also n and 1. The labels stay fixed. Two subsets with different labels are different choices, even if one picture could be rotated into the other. This is different from the rotational identification in circular arrangements.

For k ≥ 1, every selected position needs an unselected position immediately after it clockwise. Those following positions are all different. Thus a circle needs n ≥ 2k. Conversely, choosing 1,3,…,2k − 1 works whenever n ≥ 2k. The circle has k compulsory gaps, including the gap that crosses the label n back to label 1.

To count without overlooking that last gap, ask whether label n is selected. For 1 ≤ k ≤ the greatest integer not exceeding n/2:

• Label n is not selected. The remaining labels 1,…,n − 1 form a row. Choose k of them in R(n − 1,k) = C(n − k,k) ways.
• Label n is selected. Labels 1 and n − 1 are forbidden. The remaining row 2,…,n − 2 has length n − 3; choose k − 1 of it in R(n − 3,k − 1) = C(n − k − 1,k − 1) ways. If k = 1, this simply means making the one empty remaining choice.

These cases are disjoint and cover every selection. Hence the circular count is C(n − k,k) + C(n − k − 1,k − 1). For k = 0 there is one empty selection; for k > n/2 there are none.

Worked example 4. Close a row and count the new restriction

Twelve labelled positions form a circle in order. Count the nonadjacent four-element selections.

If 12 is absent, we choose four nonadjacent positions from the length-11 row 1–11. There are C(8,4) = 70 choices. If 12 is present, positions 1 and 11 are absent, leaving a length-9 row, 2–10, for three further choices. There are C(7,3) = 35 choices. The total is 105.

We can also check by starting with the 126 row selections from Example 1. A row selection fails only when it contains both 1 and 12. Those two choices forbid 2 and 11, leaving a length-8 row, 3–10, for two more choices. There are C(7,2) = 21 bad selections. Thus 126 − 21 = 105, agreeing with the direct split. The two endpoint conditions must hold together to create the extra circular violation.

Your turn 4

Ten labelled positions form a circle. Count the nonadjacent four-element selections, and explain why there is no division by 10.

Compare with a full solution

If 10 is absent, the count is R(9,4) = C(6,4) = 15. If 10 is present, 1 and 9 are absent and we choose three from the length-7 row 2–8: R(7,3) = C(5,3) = 10. The answer is 25. Labels are fixed, so rotated subsets with different labels are different objects; dividing by 10 would answer a different question and would not even give an integer here.

Two bridges for the harder problems

Read restrictions as lengths of empty gaps

For a nonempty valid row selection (k ≥ 1 and n ≥ 2k − 1), let g₀ count the unselected positions before the first selection, gₖ those after the last, and g₁,…,gₖ₋₁ those between successive selections. There are n − k unselected positions in total. Nonadjacency means the internal gaps are at least 1; the end gaps may be zero. After reserving 1 in each internal gap, the remaining n − 2k + 1 positions are distributed among k + 1 named gaps.

Here is the small counting bridge. To distribute q identical units among m named gaps, write q stars and m − 1 bars in a row. The numbers of stars before, between and after the bars are the gap contents. Adjacent bars allow a content of zero. Reading these contents reverses the encoding. Choosing the bar positions therefore gives C(q + m − 1,m − 1) distributions. With q = n − 2k + 1 and m = k + 1, this reproduces C(n − k + 1,k).

This second description becomes useful when gaps have upper bounds. In a binary word, write 1 for selected and 0 for unselected. “No adjacent 1s” means each internal zero-gap has length at least 1. “No three consecutive 0s” means every zero-gap, including both end gaps, has length at most 2. Those are different conditions, and both must be kept.

Mark one selected label before counting around a circle

A circle has no first selected position. To make an ordered gap list, temporarily mark one of the k selected labels as a starting label. Now read clockwise and record the k unselected gap lengths after successive selections. Once the starting label and this list are known, the whole labelled selection is recovered by moving gap length + 1 at each step.

For the ordinary nonadjacent rule, each gap is at least 1 and their sum is n − k. Subtract 1 from each. The k new values are nonnegative and sum to n − 2k, so there are C(n − k − 1,k − 1) lists. Choose the marked starting label in n ways. This counts pairs consisting of a valid selection and one of its marked selected labels.

Each unmarked selection occurs exactly k times, once for each possible marked member. Therefore, for k ≥ 1 and n ≥ 2k, its count is (n/k) C(n − k − 1,k − 1). The division by k removes the temporary mark. It does not identify rotations. Even a symmetric pattern has exactly k distinct choices of a marked label. Problem 9 asks you to extend this argument carefully to wider gaps.

Why does a gap list really reconstruct a valid circle? Every step length is positive, the total of the k step lengths is n, and every partial total before the last step is strictly less than n. Thus no selected label repeats before we return to the start. The stated lower bounds hold in every gap, including the closing gap.

“Largest possible” and “cannot add one” differ

$A$ maximum nonadjacent selection has the largest possible number of selected positions. A maximal one merely has no unselected position that can be added while keeping nonadjacency. A maximal selection can be smaller than a maximum one.

For a nonempty nonadjacent selection on a circle, maximality is exactly the condition that every unselected gap has length 1 or 2. If a gap has at least 3 positions, its second position can be added: it is not next to either selected endpoint. Conversely, in a gap of length 1 its only position is adjacent to a selected endpoint, and in a gap of length 2 each position is adjacent to one selected endpoint. No position can then be added. This proves both directions; checking a picture alone would not.

Which model should you try?

• Only lower separation bounds in a row: compress the selected labels.
• Required or forbidden labels: preserve the remaining intervals, distribute the number of choices between them, then multiply and add.
• A labelled circle: split on one fixed label, or mark a selected label and count gaps.
• A bound on runs of unselected positions: use gap lengths and retain the end-gap rules.
• A condition on the sum of selected labels: track how compression changes that sum. The shift is 0 + 1 + ⋯ + (k − 1); it need not preserve parity.

Nine original written problems

These problems are original teaching material, not past-paper questions. Write the counting objects, the decisive correspondence or cases, and the final conclusion. The hints are progressive; open one at a time. The self-check points below are editorial learning rubrics, not official marking schemes.

Building the method: Problems 1–2

Problem 1. Exactly one endpoint

Choose four positions from the row 1,…,12. No two chosen positions may be adjacent, and exactly one of positions 1 and 12 must be chosen. How many choices are possible?

Hint 1

Separate the case where 1 is chosen from the case where 12 is chosen.

Hint 2

If 1 is chosen, 2 and 12 are both unavailable. What consecutive interval remains for the other three choices?

Full solution

If 1 is selected, 2 is forbidden by adjacency and 12 is forbidden by “exactly one”. Choose three nonadjacent positions from 3,…,11, a row of length 9. The count is R(9,3) = C(7,3) = 35.

If 12 is selected instead, reflecting the labels by i ↦ 13 − i gives the same count, 35. The two cases are disjoint because each has a different selected endpoint, and every valid selection belongs to one of them. The answer is 70.

Check your reasoning

One point each: identify the two disjoint endpoint cases; explain both forbidden labels in the first case; count the remaining row correctly; justify the equal second count and total 70.

Problem 2. Describe every largest selection

In the row 1,…,20, find the largest possible size of a nonadjacent selection. How many selections have that size? Describe all of them by the locations of their empty gaps.

Hint 1

Group the positions into the ten adjacent pairs (1,2), (3,4), …, (19,20).

Hint 2

For ten selected positions there are ten unselected positions. How many of them are already forced into the nine internal gaps?

Hint 3

The one remaining unselected position may enlarge an internal gap or occupy an end gap.

Full solution

At most one position can be selected from each of the ten adjacent pairs, so the size is at most 10. The selection {1,3,…,19} has size 10, so the maximum is 10.

For any size-10 selection there are ten unselected positions. Put one into each of the nine internal gaps. Exactly one unselected position remains. It lies in exactly one of eleven named places: before the first selection, in one of the nine internal gaps, or after the last selection. All other end gaps are zero and all other internal gaps have length 1.

Conversely, each of these eleven choices determines a unique row word with ten selected positions and ten unselected positions, and its internal gaps are positive. Thus it gives a valid maximum selection. Different choices have different gap lists, so there are 11 such selections. This classification also agrees with C(20 − 10 + 1,10) = C(11,10) = 11.

Check your reasoning

One point each: prove the upper bound 10; give an attaining selection; show precisely one empty position remains after the internal reservations; identify eleven distinct gap locations and justify a unique selection for each.

Change the representation: Problems 3–6

Problem 3. An unavailable middle position

Position 7 cannot be used in a row labelled 1 through 13. Choose five of the other positions with no two adjacent in the original row. How many selections are possible?

Hint 1

The positions left of 7 and right of 7 are separate rows. In particular, 6 and 8 may both be chosen.

Hint 2

Each of the two rows has length 6 and can supply at most three choices. What distributions of five choices remain?

Full solution

The eligible intervals are 1–6 and 8–13, each of length 6. Since 7 is absent, there is no adjacency across the two intervals; positions 6 and 8 differ by 2 and may both be chosen.

Each length-6 row can contain at most three selections. To make five, the numbers on the two sides must therefore be (2,3) or (3,2). We have R(6,2) = C(5,2) = 10 and R(6,3) = C(4,3) = 4. The counts are 10 × 4 = 40 and 4 × 10 = 40, respectively. The left-hand size distinguishes the cases, so the answer is 80.

Deleting label 7 and relabelling all remaining positions as one length-12 row would create a false adjacency between original labels 6 and 8. That would discard valid selections.

Check your reasoning

One point each: preserve the two separate intervals; prove only the two size distributions are possible; multiply the independent choices in each case; add without overlap to obtain 80.

Problem 4. Exactly one of two opposite labels

Twelve labelled positions lie on a circle in clockwise order. Choose four nonadjacent positions, with exactly one of labels 1 and 7 chosen. How many selections are possible?

Hint 1

First count selections containing 1, whether or not they contain 7. Then remove those containing both.

Hint 2

If both 1 and 7 are selected, remove their neighbours. The remaining positions form two rows of length 3.

Hint 3

Distribute the two further choices between those rows as 0 + 2, 1 + 1 or 2 + 0.

Full solution

If 1 is selected, 12 and 2 are forbidden. The other three choices lie in the length-9 row 3–11, so there are R(9,3) = C(7,3) = 35 selections containing 1.

If both 1 and 7 are selected, their neighbours 12,2,6,8 are forbidden. Two further choices come from 3–5 and 9–11, two length-3 rows. A length-3 row has R(3,0) = 1, R(3,1) = 3 and R(3,2) = 1. The two-choice distributions give 1 × 1 + 3 × 3 + 1 × 1 = 11 selections containing both labels.

Thus 35 − 11 = 24 selections contain 1 but not 7. Rotating every label forward by six positions is a reversible correspondence to selections containing 7 but not 1; it shows equal counts, without identifying the two subsets as the same object. These two classes are disjoint. The answer is 2 × 24 = 48.

Check your reasoning

One point each: obtain 35 with one fixed selection; identify both length-3 intervals for the overlap; include all three distributions giving 11; subtract the overlap in each exclusive case and explain the total 48.

Problem 5. Forbid both long zero-runs and adjacent ones

How many binary words of length 12 contain exactly four 1s, no two consecutive 1s, and no three consecutive 0s? A word is read from left to right; its two ends are not joined.

Hint 1

There are five zero-gaps: three internal and two at the ends. Give each its correct lower and upper bound.

Hint 2

Every internal gap has length 1 or 2, while each end gap has length 0,1 or 2. There are eight zeros in total.

Hint 3

Let s be the number of internal gaps of length 2. The two end gaps must then sum to 5 − s.

Full solution

Let g₀ and g₄ be the end zero-gaps and g₁,g₂,g₃ the internal gaps. The condition on 1s gives 1 ≤ g₁,g₂,g₃ ≤ 2. The condition on 0s gives 0 ≤ g₀,g₄ ≤ 2. Their total is 8.

Let s be the number of internal gaps of length 2. The internal gaps then use 3 + s zeros, leaving 5 − s for the two end gaps. The choice of which internal gaps are long can be made in C(3,s) ways.

• s = 0 is impossible, since the end gaps cannot sum to 5.
• s = 1: the end sum is 4, allowing only (2,2). This gives C(3,1) × 1 = 3.
• s = 2: the end sum is 3, allowing (1,2) and (2,1). This gives C(3,2) × 2 = 6.
• s = 3: the end sum is 2, allowing (0,2), (1,1) and (2,0). This gives C(3,3) × 3 = 3.

Each complete gap list determines one word: write the first zero-gap, then 1, the next gap, then 1, and continue. Every counted word has four separated 1s and zero-gaps of length at most 2. Different lists give different words. The answer is 3 + 6 + 3 = 12.

Check your reasoning

One point each: distinguish internal and end lower bounds; obtain the total of eight zeros; exhaust s and the ordered end-gap pairs; prove that the gap lists count the words once, giving 12.

Problem 6. Track parity through compression

How many three-element subsets of {1,…,10} contain no consecutive integers and have an even sum of their selected elements?

Hint 1

Use the compression from Your turn 1, but track the sum as well as the upper bound.

Hint 2

The total subtracted from the three elements is 0 + 1 + 2 = 3. Therefore the parity of the sum changes.

Hint 3

Among 1 through 8 there are four odd and four even labels. An odd sum of three distinct labels has either one odd label or three.

Full solution

For increasing selected labels a₁,a₂,a₃, put b₁ = a₁, b₂ = a₂ − 1, b₃ = a₃ − 2. This is a bijection to three-element subsets of {1,…,8}. Also a₁ + a₂ + a₃ = b₁ + b₂ + b₃ + 3. Hence the original sum is even exactly when the compressed sum is odd.

Among the eight compressed labels there are four odd and four even numbers. An odd sum occurs in two disjoint cases: one odd and two even labels, counted by C(4,1)C(4,2) = 4 × 6 = 24; or three odd labels, counted by C(4,3) = 4. No other parity pattern has an odd sum.

Expanding by 0,1,2 is the same inverse as before, so it recovers precisely the valid original subsets with even sum. The answer is 24 + 4 = 28. Compression preserves the counting objects through a bijection, but it does not preserve every property unchanged.

Check your reasoning

One point each: state the bijection to subsets of 1–8; derive the sum shift of 3; count both permitted parity patterns; connect the inverse to the original condition and obtain 28.

Write complete proofs: Problems 7–9

Problem 7. Largest selections on every labelled circle

For a circle of n labelled positions, where n ≥ 3, find the largest possible size of a nonadjacent selection and count all selections of that size. Treat even and odd n separately. Different labelled subsets count separately.

Hint 1

Give every selected position its immediate clockwise neighbour. Why are these neighbours distinct and unselected?

Hint 2

For n = 2m and k = m, every circular unselected gap has length 1. For n = 2m + 1 and k = m, how many extra unselected positions remain?

Hint 3

In the odd case there is exactly one pair of consecutive unselected positions. Show that choosing its edge determines the whole selection.

Full solution

If k positions are selected, their k immediate clockwise neighbours are distinct unselected positions. Therefore 2k ≤ n. Choosing alternate positions attains k = m for both n = 2m and n = 2m + 1, so the maximum size is the greatest integer not exceeding n/2.

Even case, n = 2m. A maximum selection has m selected and m unselected positions. All m circular unselected gaps must have length 1, so selected and unselected positions alternate all the way around. Selecting 1 forces exactly the odd labels; not selecting 1 forces exactly the even labels. Both choices work and are different. There are 2 maximum selections.

Odd case, n = 2m + 1. A maximum selection has m selected and m + 1 unselected positions. Reserve one unselected position in each of its m circular gaps. Exactly one extra remains, so precisely one gap has length 2 and all others have length 1. Thus there is a unique edge whose two endpoints are both unselected.

Conversely, choose any of the n edges and leave its two endpoints unselected. Read along the other path between those endpoints. It has 2m − 1 interior positions; mark them selected, unselected, selected, and so on, ending selected. This creates m selections with all required gaps and exactly the chosen unselected edge. The construction is forced by alternation away from that edge. It works also for n = 3, when the one interior position is selected. Hence the unique edge gives a bijection, and there are $n$ maximum selections in the odd case.

Check your reasoning

Five points: prove the size bound; construct an attaining selection; classify the two even alternating patterns; prove the unique double gap in the odd case; construct and recover the unique selection for each of the n edges, including n = 3.

Problem 8. Maximal need not mean maximum

On a circle with labels 1,…,9, count all nonadjacent selections to which no further position can be added. Explain why some counted selections have fewer elements than a maximum selection.

Hint 1

Use the proved criterion for maximality: every circular unselected gap must have length 1 or 2.

Hint 2

If k positions are selected, the 9 − k unselected positions lie in k gaps. Bound 9 − k between k and 2k.

Hint 3

For k = 3 all gaps have length 2. For k = 4 use the odd-circle classification from Problem 7.

Full solution

The empty selection is not maximal because any one position can be added. For a nonempty selection with k members, maximality means all k unselected gaps have length 1 or 2. Thus k ≤ 9 − k ≤ 2k. The left inequality gives k ≤ 4 and the right gives k ≥ 3. Only k = 3 or 4 is possible.

For k = 3, six unselected positions occupy three gaps of length at most 2, so every gap has length 2. The selections are exactly {1,4,7}, {2,5,8}, {3,6,9}. To see completeness, starting from any selected label forces a step of three around the circle; each of these three sets is obtained from three possible starting labels. Thus there are 3 selections of size 3.

For k = 4, the selection has maximum size on a 9-position circle. Problem 7 proves that there are 9 such selections, each with one unselected gap of length 2 and the other three of length 1. They satisfy the maximality criterion as well.

The total is 3 + 9 = 12. The first three selections cannot be enlarged by adding a single position, yet they have only three members; four-member selections exist. This explicitly separates maximality from maximum size.

Check your reasoning

Five points: exclude the empty set; justify the gap criterion in both directions; derive k = 3 or 4; count each size completely; use a three-member example and a four-member example to explain the distinction.

Problem 9. A general circular separation theorem

Let n,k,d be integers with n ≥ 3, k ≥ 1, d ≥ 1 and n ≥ (d + 1)k. Choose k positions on a labelled circle of size n so that, moving clockwise from each selected position to the next selected position, at least d unselected positions occur. When k = 1, the gap goes once around the circle back to that position. Prove that the count is (n/k) C(n − dk − 1,k − 1), and use your proof to count the choices for n = 18, k = 4, d = 2.

Hint 1

Temporarily mark one selected label. The mark supplies a starting point for an ordered list of circular gaps.

Hint 2

After subtracting d from each gap, what is the sum of the k nonnegative remainders?

Hint 3

Count pairs (selection, marked selected label) in two ways. Check that reconstructing from a gap list never repeats a selected label before returning to the start.

Full solution

Temporarily mark one selected label. Starting there and moving clockwise, let g₁,…,gₖ be the numbers of unselected positions after the successive selected labels. There are k gaps, including the one closing back to the marked label. Each gᵢ ≥ d, and their sum is n − k.

Put hᵢ = gᵢ − d. These are nonnegative integers with sum n − (d + 1)k, which is nonnegative by hypothesis. The stars-and-bars bijection gives C(n − (d + 1)k + k − 1,k − 1) = C(n − dk − 1,k − 1) ordered gap lists. This also works for k = 1: there is one gap list and no bars.

Choose the marked label in n ways. For each such label and gap list, move clockwise by g₁ + 1, then g₂ + 1, and so on. Every step is positive, the total of all k steps is n, and every proper partial sum is less than n. Thus we obtain k distinct selected positions and return to the start only at the end. The lower bound d holds in every circular gap, including the last. Conversely, any marked valid selection determines that one starting label and that one ordered gap list. We have therefore counted exactly n C(n − dk − 1,k − 1) marked selections.

Every unmarked labelled selection has exactly k possible marked members, even if its pattern has rotational symmetry. Dividing by k gives (n/k) C(n − dk − 1,k − 1) selections. The division removes the mark, not the labels or rotations.

For n = 18, k = 4 and d = 2, the condition 18 ≥ 3 × 4 holds. The answer is (18/4) C(9,3) = (18/4) × 84 = 378. At the boundary n = (d + 1)k there is exactly one gap list (all gaps have length d); the same argument gives n/k = d + 1 labelled selections. For k = 1 it gives n choices, as it should.

Check your reasoning

Five points: define the marked object and all k circular gaps; derive the shifted gap sum and its count; prove the reconstruction is valid and reversible; divide by exactly k with the labelled convention preserved; compute 378 and check k = 1 or the boundary n = (d + 1)k.

Nine adaptive checks

Use these shorter checks after the examples. The choices test recognition, calculation and common errors; they do not automatically mark your written proofs. Each check has hints, an explanation and a link back to the relevant lesson section. All lesson content and practice are free without mandatory sign-in.

Interactive practice loads here. You can also use the complete question set below.

Exit task: explain the division

Close the solutions and reconstruct Problem 9. Name exactly what a marked selection is, show how the gap list recovers it, and explain why every ordinary labelled selection is counted exactly k times. Then explain why dividing by n because “it is a circle” would not be justified here.

Planning hint

There are n choices for the marked label but k ways to mark a fixed completed selection. Those numbers answer different questions. A rotation changes the labelled subset and is not an equivalence in this lesson.

Compare with a full proof

Temporarily mark one selected label. Starting there and moving clockwise, let g₁,…,gₖ be the numbers of unselected positions after the successive selected labels. There are k gaps, including the one closing back to the marked label. Each gᵢ ≥ d, and their sum is n − k.

Put hᵢ = gᵢ − d. These are nonnegative integers with sum n − (d + 1)k, which is nonnegative by hypothesis. The stars-and-bars bijection gives C(n − (d + 1)k + k − 1,k − 1) = C(n − dk − 1,k − 1) ordered gap lists. This also works for k = 1: there is one gap list and no bars.

Choose the marked label in n ways. For each such label and gap list, move clockwise by g₁ + 1, then g₂ + 1, and so on. Every step is positive, the total of all k steps is n, and every proper partial sum is less than n. Thus we obtain k distinct selected positions and return to the start only at the end. The lower bound d holds in every circular gap, including the last. Conversely, any marked valid selection determines that one starting label and that one ordered gap list. We have therefore counted exactly n C(n − dk − 1,k − 1) marked selections.

Every unmarked labelled selection has exactly k possible marked members, even if its pattern has rotational symmetry. Dividing by k gives (n/k) C(n − dk − 1,k − 1) selections. The division removes the mark, not the labels or rotations.

For n = 18, k = 4 and d = 2, the condition 18 ≥ 3 × 4 holds. The answer is (18/4) C(9,3) = (18/4) × 84 = 378. At the boundary n = (d + 1)k there is exactly one gap list (all gaps have length d); the same argument gives n/k = d + 1 labelled selections. For k = 1 it gives n choices, as it should.

A counting-proof checklist

A complete argument should answer all five questions below. Use them to review your own proof; they are not an official contest marking scheme.

1. Objects: Which labels can be selected, how many, and which adjacencies or gap bounds are required? Are rotations considered different?
2. Representation: What information is recorded by the compressed labels, interval counts or gap list? What are its exact bounds?
3. Coverage: Does every original selection produce a permitted representation or belong to one of the stated cases?
4. Uniqueness: Can the original selection be recovered? If you deliberately count marked objects, what is the exact multiplicity of each unmarked object?
5. Conclusion: Have you justified the arithmetic, impossible cases, empty choices and any smallest permitted parameter?

My proof notebook

Use paper, or the optional browser notebook. Save a proof attempt before comparing it with the solution. The notebook does not automatically assess your proof.

Choose your next step

• If choosing and ordering were mixed up, revisit combinations and redo the diagnostic.
• If you found a transformation but could not reverse it, study bijections and explain Example 1 without a formula.
• If you lost a boundary condition, revisit the gap definitions, then try Problem 5 again. For more bounds, continue to counting integer solutions.
• If the circle arguments needed a hint, reattempt Problems 7–9 another day. Review circular permutations to compare the different conventions for rotations.
• Return to Türkiye’s study route, or open your optional local revision list.

Contest context and originality

The official high-school mathematics syllabus includes counting, and the released-paper archive supplies official practice. The 2026 high-school paper includes restricted-string counting; this supports a broad counting-method connection, not a claim that this exact method or difficulty appeared. Its questions have equal weight, one correct option each, and are not ordered by difficulty. Four wrong answers cancel one correct answer. Understand the method first, then practise choosing which questions to attempt. Sources checked 18 October 2026.

These explanations, examples, exercises and diagrams are original AI-assisted editorial teaching material using standard combinatorial ideas. They are not reproduced or translated national contest questions. The preparation connection is editorial; no organiser affiliation, endorsement, exact difficulty match or prediction of topic frequency is claimed. Check the current official instructions for your division, stage and year.

Prepared for IMOolympiad.com. Report a specific unclear step or correction. Optional progress stays in this browser; written proofs are for your own review.