Divisibility by 9 and Chameleon Colors

This brain teaser asks for a simple, usable rule to decide whether an integer is divisible by 9, and then for a convincing argument that the rule always works. It takes a familiar school trick and treats it with full mathematical seriousness: you are not just expected to recall the rule, but to explain why it holds in every case, not just for a few examples. The setup is entirely within ordinary base-10 notation, but the question gently pushes you from pattern spotting into more formal reasoning.

To answer well, you need to connect everyday decimal representation with modular arithmetic, and to express that link clearly. Strong solutions typically rephrase a generic multi-digit number in algebraic form and track its remainder when divided by 9. Interviewers watch for comfort with congruences, the ability to justify each step rather than hand-wave, and a clean explanation that could convince a skeptical audience rather than just assert a known fact.

What it tests

Problems about divisibility rules for numbers in a given base are governed by modular arithmetic and the structure of place value. The key insight is that powers of the base (like $10^k$ in decimal) have predictable remainders when divided by certain numbers (like 9), because $10 \equiv 1 \pmod{9}$. This means that each digit's contribution to the number is, modulo 9, just itself, so the sum of the digits captures the original number's residue mod 9. This pattern holds because the base minus 1 (here, 9) always divides $10^k - 1$ for any $k$, making the digit sum a complete invariant for divisibility by 9. The general principle is that the structure of our number system encodes certain divisibility properties directly into the digits, via modular congruence.