Check counts in a nonadjacent binary-schedule investigation

The investigation brief, ungraded

A device uses a schedule of n labelled slots. Each slot is active (1) or inactive (0), and adjacent slots may not both be active. Investigate how many schedules are possible. Choose and justify your scope, compare at least two counting methods, test a conjecture with technology, prove a general claim and explain one changed assumption. Produce a written report with reproducible evidence. A numeric checkpoint is not completion of this investigation

Plan before opening the models

Record the question in your own words and choose n values small enough to enumerate. State whether the schedule is a line or a cycle, whether labels stay fixed, and whether the number of active slots is prescribed. Keep your first conjecture and any revision. Attempt the following tasks before using the model discussion. Teacher guidance and checkpoints support the report; they do not award an investigation outcome

Formulation and small cases, ungraded

For the first model, use a line with fixed labels, no wrap-around and no prescribed active count. Define aₙ, including n=0. List every valid string for n=1,2,3, explain how your list avoids duplicates and omissions, and formulate a conjecture connecting successive counts. Independent formulation and justification are ungraded

Model: define the outcome set

Let Sₙ be the set of all binary strings (b₁,...,bₙ) with bᵢbᵢ₊₁=0 for every i=1..n−1, and let aₙ=|Sₙ|. The empty string is one outcome, so a₀=1. S₁={0,1}; S₂={00,01,10}; S₃={000,001,010,100,101}. Listing binary strings in increasing numeric order and filtering adjacent ones gives a systematic audit of the small cases

Original length-three model list

\(\displaystyle S_3=\{\mathtt{000},\mathtt{001},\mathtt{010},\mathtt{100},\mathtt{101}\}\)

How many valid strings of length three appear in the model list?

Distinguish evidence from proof

The counts 1,2,3,5 suggest aₙ=aₙ₋₁+aₙ₋₂. A few matching values do not prove that relation for all n. Search for a structural partition that is disjoint, exhaustive and reversible

Conjecture and proof, ungraded

Prove aₙ=aₙ₋₁+aₙ₋₂ for n≥2 by partitioning valid strings. State the initial values and explain why they determine every later count. Then prove that the resulting recurrence counts the required objects rather than merely generating the observed numbers. Independent proof is ungraded

Model: partition by the final symbol

A valid length-n string ends either in 0 or in 1. If it ends in 0, removing that final 0 is a bijection to Sₙ₋₁. If it ends in 1, the previous symbol must be 0, and removing the final 01 is a bijection to Sₙ₋₂. The cases are disjoint and exhaustive. Thus aₙ=aₙ₋₁+aₙ₋₂, with a₀=1,a₁=2. Induction on n shows that these initial values and this recurrence produce |Sₙ| for every n

Each count from length two is the sum of the preceding two counts. Use the displayed verified values to calculate a₇

Computational exploration, ungraded

Before running, select a programming application or spreadsheet and name the functionality you will use. Justify how it supports both algorithms and identify one limitation. Write and run an independent enumeration algorithm and a recurrence algorithm for n=0..10. Record pseudocode, exact input range, results and a mismatch check. Explain why in-place updates can corrupt a two-state recurrence, why enumeration stops and how you know every candidate is visited once. Independent programming and technology use are ungraded. Retain the application/version, code or formulas, actual outputs and independent small-case checks for review

Model: exhaustive enumeration pseudocode

For n=0..10, set count=0. For each integer mask from 0 to 2ⁿ−1 inclusive, convert it to a binary string of exactly n places (the empty string for n=0), keeping leading zeros. Set valid=true; for j=1..n−1, if bit[j]=bit[j+1]=1 set valid=false. Add one when valid. Output n,count. Each n-bit string has a unique integer encoding, so the outer candidate loop has exactly 2ⁿ cases and neither repeats nor omits a string. Both loops have finite stated bounds

Model: recurrence algorithm with an invariant

For n=0 return 1. Otherwise initialise z=1,o=1 for length one. For length=1..n−1, store nextZ=z+o and nextO=z before assigning z=nextZ,o=nextO. Return z+o. The invariant is that z and o count valid strings of the current length ending in 0 and 1. Appending 0 is always allowed; appending 1 requires a previous 0. The invariant proves the update, and the length increases to n, so the loop terminates

Model: reproducible results and checks

Both algorithms should return a₀,...,a₁₀ = 1,2,3,5,8,13,21,34,55,89,144. Report the full input range and compare each pair, not just the final total. For example z₄=5,o₄=3; replacing z by z+o first and then setting o=z incorrectly gives 8,8 instead of the next state 8,5. The recurrence takes n−1 state updates; enumeration examines 2ⁿ candidates with up to n−1 adjacency checks each. A program with bounded loops is a defensible choice because it can enumerate every mask and store both old state counts. A spreadsheet is also defensible if it implements both algorithms with inspectable formulas and preserved old-state cells. Record your own run; neither application turns matching finite outputs into a general proof

Both algorithms count linear binary schedules with no adjacent active slots. The counts at lengths eight and nine are 55 and 89; each next count is their sum. What total should both algorithms produce at n=10?

A first-order matrix state model

For n≥1 use vₙ=(zₙ,oₙ)ᵀ and the displayed matrix M. Then vₙ₊₁=Mvₙ, v₁=(1,1)ᵀ, and vₙ=Mⁿ⁻¹v₁. Matrix multiplication uses both old state counts simultaneously. The total is the sum of the two components

The first and second components of vₙ count schedules ending in 0 and 1, respectively. The next ending-in-1 count equals the current ending-in-0 count. If v₄=(5,3)ᵀ, what is the ending-in-1 count at length five?

Fixed-weight extension, ungraded

For exactly k active slots, derive a formula for the valid linear schedules. Explain the maximum feasible k, include k=0, and compare your formula with enumeration for small n. Sum over k to recover the unrestricted count. Independent derivation and communication are ungraded

Model: remove mandatory gaps

Write active positions as i₁<...<iₖ with iᵣ₊₁≥iᵣ+2. Map them to jᵣ=iᵣ−(r−1). Then 1≤j₁<...<jₖ≤n−k+1. The inverse iᵣ=jᵣ+(r−1) restores the gaps, so this is a bijection. The count is C(n−k+1,k) when 0≤k≤floor((n+1)/2), and zero for larger k. For k=0, the unique empty position set gives the all-zero string

How many length-seven binary schedules on a line have no adjacent active slots and exactly three active slots?

Model: a second exact formula

Partition Sₙ by its number k of active slots. Every valid string belongs to exactly one class, so aₙ is the sum of C(n−k+1,k) over k=0..floor((n+1)/2). At n=7 the terms are 1+7+15+10+1=34. Agreement with the recurrence follows because both methods count the same well-defined set, not just because a table happens to match

Changed assumptions and evaluation, ungraded

Investigate both a specified active slot and cyclic adjacency. For the cycle take n≥3, keep labels fixed, and treat first/last slots as adjacent. Derive each count, test boundary cases and explain why rotating a labelled string does not make it the same outcome. Identify which original claims must change. Independent extension and evaluation are ungraded

Model: force a labelled slot active

Forcing slot j active forces its existing neighbours inactive. The remaining separated left/right lines have lengths max(0,j−2) and max(0,n−j−1). Choose a valid string independently on each, giving their count product. For n=7,j=3, the lengths are 1 and 3, so the count is a₁a₃=2×5=10. At an endpoint only one neighbour exists; an empty remaining line has one choice

For a line of seven binary slots in which adjacent slots cannot both be active, how many schedules have slot three active?

Model: close the line into a labelled cycle

For n≥3, split by slot one. If it is 0, the other n−1 slots form a free valid line. If it is 1, slots two and n must be 0, leaving a free line of length n−3. Thus cₙ=aₙ₋₁+aₙ₋₃. At n=3 the four cyclic strings are 000,001,010,100. At n=5 the count is a₄+a₂=8+3=11, instead of the linear count 13. The excluded linear strings have both endpoints active. Dividing by n is unjustified when rotations have unequal orbit sizes; this investigation keeps labels fixed

How many binary schedules on five fixed, labelled slots have no adjacent active slots when the first and last slots are also adjacent?

Communicate your report, ungraded

Present your question, assumptions, definitions, small-case evidence, conjecture and any revision, two algorithms with invariant/termination reasoning, reproducible outputs, general proof, extension and limitations. Distinguish observed data from proved claims. Cite any external tools used and include enough detail for another student to reproduce your computation. Independent written communication is ungraded

Model report conclusion

Under the linear fixed-label binary model, a₀=1,a₁=2 and aₙ=aₙ₋₁+aₙ₋₂. A disjoint reversible partition proves this recurrence. Independent enumeration checks n=0..10, and a two-state matrix update computes the same counts. A gap-removal bijection gives the fixed-weight formula. For a labelled cycle of length at least three, cₙ=aₙ₋₁+aₙ₋₃. These results do not automatically apply to unlabelled rotations, unequal slot durations, minimum separation greater than one, or a device with additional physical constraints

Teacher guidance and assessment boundary

Ask for the learner’s formulation and first conjecture before the model discussion, then inspect their own case lists, code or spreadsheet, mismatch checks, proof and revised conclusions. Discuss leading zeros, the empty string, simultaneous updates, endpoint cases and fixed labels. Judge mathematical communication, justification and reproducibility using the school’s criteria. No numeric response here establishes completion of an investigation or an official assessment outcome