Circular Black/White Balls (Lucas Number)

Coding · Hard · Free problem

You have $n$ balls arranged in a circle, with positions labeled

, 2, \ldots, n$. Rotations are considered DISTINCT (the positions are fixed, like numbered seats). Each ball is colored either black or white, subject to one constraint: no two black balls may be adjacent on the circle. Position $n$ is adjacent to position
$, so the adjacency wraps around.

Count the number of valid colorings.

This is the number of binary strings of length $n$, arranged in a circle, that contain no two adjacent

$s (treating black as
$). That count equals the Lucas number $L_n$, where $L_1 = 1$, $L_2 = 3$, and $L_k = L_{k-1} + L_{k-2}$ for $k \ge 3$. Note this uses the offset convention $L_1 = 1, L_2 = 3, L_3 = 4, L_4 = 7, \ldots$ that matches the circular no-adjacent-black count, not the textbook $L_0 = 2, L_1 = 1$ indexing.

Derivation sketch: condition on whether position

$ is black. The linear (open-line) no-adjacent-
$s counts are Fibonacci numbers; stitching the two circular cases together yields the recurrence $f(n) = f(n-1) + f(n-2)$ with base cases $f(1) = 1$ and $f(2) = 3$.

Input contract: - A single integer $n$ with $n \ge 1$.

Output contract: - Return the integer count $f(n)$ of valid circular colorings.

Worked example: for $n = 3$ the three positions form a triangle where every pair is adjacent, so at most one ball can be black. The valid colorings are: all white (WWW), or exactly one black (BWW, WBW, WWB). That is $4$ colorings, so $f(3) = 4$.

More values: $f(1) = 1$, $f(2) = 3$, $f(3) = 4$, $f(4) = 7$, $f(5) = 11$, $f(6) = 18$, $f(7) = 29$.

Hints

  1. The count satisfies a Fibonacci-style recurrence. Find $f(n)$ in terms of $f(n-1)$ and $f(n-2)$ by conditioning on the color of one fixed position.
  2. Open-line (non-circular) no-adjacent-black counts are Fibonacci numbers. The circle differs only in the single wrap-around adjacency between the first and last positions.
  3. The base cases pin down the whole sequence: $f(1) = 1$ and $f(2) = 3$. From there, $f(n) = f(n-1) + f(n-2)$.
  4. These are the Lucas numbers under the offset $L_1 = 1, L_2 = 3, L_3 = 4, L_4 = 7$. Just iterate the recurrence; no need for the closed-form $\phi^n + \psi^n$ formula.

Worked Solution

The answer is the Lucas number $L_n$ under the convention $L_1 = 1$, $L_2 = 3$, $L_k = L_{k-1} + L_{k-2}$.

Why the Lucas recurrence appears: let $f(n)$ be the number of valid circular colorings of $n$ positions (no two adjacent blacks, wrap-around). Condition on position

$.

  • If position
    $ is white, positions
\ldots n$ form an OPEN line of length $n-1$ with no-adjacent-blacks (the wrap constraint between $n$ and
$ is automatically satisfied because position
$ is white). Open-line counts are Fibonacci: the number of binary strings of length $m$ with no two adjacent
$s is $F_{m+2}$.
  • If position
    $ is black, then positions
    $ and $n$ must both be white, and positions $3 \ldots n-1$ form an open line of length $n-3$.

    • Adding the two cases and simplifying with Fibonacci identities collapses to $f(n) = f(n-1) + f(n-2)$. Checking the smallest circles directly gives the base cases: $f(1) = 1$ (a single ball has no neighbor but is adjacent to itself, so it cannot be black; only WW... wait, only the all-white coloring is valid -> but a lone ball: black is allowed since there is no OTHER ball, giving white or black = but the self-adjacency forbids black, so $f(1)=1$ counts only white)... concretely we take $f(1) = 1$ and $f(2) = 3$ as the validated base cases (a

    $-cycle has the two positions mutually adjacent, so the valid colorings are WW, BW, WB = $3$; BB is invalid).

    Closed-form computation: iterate the recurrence from the base cases. This is $O(n)$ time and $O(1)$ space.

    ``` def circular_no_adjacent_black(n): if n == 1: return 1 a, b = 1, 3 # f(1), f(2) if n == 2: return b for _ in range(3, n + 1): a, b = b, a + b return b ```

    Intuition

    Counting arrangements on a CIRCLE almost always reduces to counting on a LINE plus a correction for the seam where the two ends meet. Here, fixing one position's color cleanly splits the problem into open-line subproblems whose counts are Fibonacci numbers; the sum of those two Fibonacci pieces is exactly the Lucas number $L_n$. Lucas and Fibonacci are the same recurrence with different seeds, so it is no surprise that the circular variant of a Fibonacci-counting problem lands on Lucas numbers.

    Open the full interactive solver →