Problem 641: A Flea on a Chess Board

Mathematical Foundation

Definition 1 (Cell Colour). For a point $(x,y) \in \mathbb{R}^2$, define the colour function

The cell is white if $\chi = 0$ and black if $\chi = 1$.

Theorem 1 (Orbit Period). The sequence of reduced positions $(k\,dx \bmod 2W,\; k\,dy \bmod 2H)_{k \ge 0}$ is periodic with exact period

Proof. Consider the $x$-coordinate modulo $2W$. The map $k \mapsto k\,dx \bmod 2W$ is the orbit of $0$ under repeated addition of $dx$ in the cyclic group $\mathbb{Z}/2W\mathbb{Z}$. The order of the element $dx$ in this group is

since the subgroup generated by $dx$ in $\mathbb{Z}/2W\mathbb{Z}$ has order $2W / \gcd(dx, 2W)$ by the structure theorem for cyclic groups. Similarly, the $y$-coordinate modulo $2H$ has period $L_y = 2H / \gcd(dy, 2H)$. The joint sequence $(x_k \bmod 2W, y_k \bmod 2H)$ returns to $(0,0)$ precisely when both coordinates simultaneously return to $0$, which occurs at $k = \operatorname{lcm}(L_x, L_y) = L$. That $L$ is the exact period follows from the minimality of the lcm among common multiples of $L_x$ and $L_y$. $\square$

Lemma 1 (Colour Determination on the Torus). The colour of the cell visited at step $k$ depends only on the residue pair $(k\,dx \bmod 2W,\; k\,dy \bmod 2H)$.

Proof. Write $k\,dx = 2Wq_x + r_x$ where $r_x = k\,dx \bmod 2W$. Then $\lfloor k\,dx / W \rfloor = 2q_x + \lfloor r_x / W \rfloor$, so $\lfloor k\,dx / W \rfloor \bmod 2 = \lfloor r_x / W \rfloor \bmod 2$. The analogous identity holds for the $y$-coordinate. Therefore

which depends only on $(r_x, r_y)$. $\square$

Theorem 2 (Colour Counting via Full Periods). Let $w$ and $b$ denote the number of white and black cells visited in one full period $\{0, 1, \ldots, L-1\}$, so that $w + b = L$. Then across all $N+1$ positions $\{0, 1, \ldots, N\}$:

where $r = (N+1) \bmod L$ and $w_r$ is the number of white cells among the first $r$ positions of a period.

Proof. By Lemma 1 and Theorem 1, the colour sequence $(\chi_0, \chi_1, \ldots)$ is periodic with period $L$. The $N+1$ positions $\{0, \ldots, N\}$ decompose into $\lfloor (N+1)/L \rfloor$ complete periods, each contributing exactly $w$ white cells, plus a partial period of length $r = (N+1) \bmod L$ contributing $w_r$ white cells. The black count follows from complementarity. $\square$

Editorial

The colour sequence on the torus Z/(2W) x Z/(2H) is periodic with period L = lcm(2W/gcd(dx,2W), 2H/gcd(dy,2H)). Count white/black cells in one period, then scale to N+1 positions via division with remainder. We enumerate one full period on the torus. Finally, decompose N+1 positions into full periods + remainder.

Pseudocode

Enumerate one full period on the torus
Decompose N+1 positions into full periods + remainder

Complexity Analysis

• Time: $O(L)$ where $L = \operatorname{lcm}(L_x, L_y) \le 4WH / (\gcd(dx,2W) \cdot \gcd(dy,2H))$.
• Space: $O(L)$ for the prefix-sum array (reducible to $O(1)$ if only the total count is needed after a single enumeration pass).

Answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

/*
 * Problem 641: A Flea on a Chess Board
 *
 * Colour sequence on the torus Z/(2W) x Z/(2H) has period
 * L = lcm(2W/gcd(dx,2W), 2H/gcd(dy,2H)).
 * Enumerate one period, then scale via division with remainder.
 */

ll gcd_(ll a, ll b) { return b ? gcd_(b, a % b) : a; }
ll lcm_(ll a, ll b) { return a / gcd_(a, b) * b; }

pair<ll, ll> count_colours(ll W, ll H, ll dx, ll dy, ll N) {
    ll Lx = 2 * W / gcd_(dx, 2 * W);
    ll Ly = 2 * H / gcd_(dy, 2 * H);
    ll L = lcm_(Lx, Ly);

    // Enumerate one full period
    vector<ll> prefix(L + 1, 0);
    ll x = 0, y = 0;
    for (ll k = 0; k < L; k++) {
        ll colour = (x / W + y / H) % 2;
        prefix[k + 1] = prefix[k] + (1 - colour);
        x = (x + dx) % (2 * W);
        y = (y + dy) % (2 * H);
    }

    ll w = prefix[L];
    ll full = (N + 1) / L;
    ll rem = (N + 1) % L;
    ll white_total = full * w + prefix[rem];
    ll black_total = (N + 1) - white_total;
    return {white_total, black_total};
}

int main() {
    auto [w, b] = count_colours(2, 3, 3, 4, 999);
    cout << "Problem 641: white=" << w << " black=" << b << endl;
    return 0;
}

"""
Project Euler Problem 641: A Flea on a Chess Board

The colour sequence on the torus Z/(2W) x Z/(2H) is periodic with period
L = lcm(2W/gcd(dx,2W), 2H/gcd(dy,2H)).  Count white/black cells in one
period, then scale to N+1 positions via division with remainder.
"""

from math import gcd


def lcm(a, b):
    return a * b // gcd(a, b)


def count_colours(W, H, dx, dy, N):
    Lx = 2 * W // gcd(dx, 2 * W)
    Ly = 2 * H // gcd(dy, 2 * H)
    L = lcm(Lx, Ly)

    # Enumerate one full period
    white_prefix = [0] * (L + 1)
    x, y = 0, 0
    for k in range(L):
        colour = (x // W + y // H) % 2
        white_prefix[k + 1] = white_prefix[k] + (1 - colour)
        x = (x + dx) % (2 * W)
        y = (y + dy) % (2 * H)

    w = white_prefix[L]
    full, rem = divmod(N + 1, L)
    white_total = full * w + white_prefix[rem]
    black_total = (N + 1) - white_total
    return white_total, black_total


# Verification with small cases
assert count_colours(2, 3, 1, 1, 0) == (1, 0)  # origin is white
print(count_colours(2, 3, 3, 4, 999))
print("Problem 641: A Flea on a Chess Board")