Counting words modulo a huge power of 3 without an enormous recurrence

co_op_cactus·Jun 6, 2026(edited)

I can write

|M|=\sum_{i=0}^{2023}\binom{i+2}{2}3^i

. Can we compare that with

|B|

directly, without evaluating either sum? Problem: Let

k

be a non-negative integer and let

A

be a nonempty finite set. We define a word from the alphabet

A

of length

k

as a sequence of elements of

A

of length

k

. (Notice that by definition the empty sequence is a word of length

0

.) * Let

B

be the set of all words from the nine-element alphabet

\{b, @, l, t, i, c, w, a, y\}

, whose lengths are at most

2023

. * Moreover, let

M

be the set of all words from the four-element alphabet

\{m, a, t, h\}

, whose lengths are at most

2025

and which contain the element

t

exactly twice. (For example,

tata \in M

, because it has length

4

and contains the letter

t

twice, but

mahatma \notin M

, because it contains the letter

t

only once.) Prove that the difference

|B| - |M|

is divisible by

3^{2023}

. Source: Baltic Way 2023 Shortlist · MNET-01J2

Open MNET-01J2 in the question bank →

4 replies

shieldonbreak·Jun 6, 2026(edited)

Work in the ring modulo

3^k

, with k=2023. Let

G=1+3+\cdots+3^{k-1}

. Then

(1-3)G\equiv1

, so

G^3\equiv(-2)^{-3}=-1/8

co_op_cactus·Jun 6, 2026

The coefficient of

3^i

in that cube counts triples of nonnegative integers summing to i, hence

\binom{i+2}{2}

. Terms with i≥k vanish modulo

3^k

shieldonbreak·Jun 6, 2026

Exactly, so

|M|\equiv-1/8

. Also

|B|=\sum_{j=0}^k9^j\equiv(1-9)^{-1}=-1/8

in the same ring. The inverses exist because 2 and 8 are coprime to 3.

thecakewaslag·Jun 7, 2026

This is the finite modular version of the 3-adic argument. It doesn't claim the corresponding real infinite series converge.

Counting words modulo a huge power of 3 without an enormous recurrence

co_op_cactus·Jun 6, 2026(edited)

I can write

|M|=\sum_{i=0}^{2023}\binom{i+2}{2}3^i

. Can we compare that with

|B|

directly, without evaluating either sum? Problem: Let

k

be a non-negative integer and let

A

be a nonempty finite set. We define a word from the alphabet

A

of length

k

as a sequence of elements of

A

of length

k

. (Notice that by definition the empty sequence is a word of length

0

.) * Let

B

be the set of all words from the nine-element alphabet

\{b, @, l, t, i, c, w, a, y\}

, whose lengths are at most

2023

. * Moreover, let

M

be the set of all words from the four-element alphabet

\{m, a, t, h\}

, whose lengths are at most

2025

and which contain the element

t

exactly twice. (For example,

tata \in M

, because it has length

4

and contains the letter

t

twice, but

mahatma \notin M

, because it contains the letter

t

only once.) Prove that the difference

|B| - |M|

is divisible by

3^{2023}

. Source: Baltic Way 2023 Shortlist · MNET-01J2

Open MNET-01J2 in the question bank →

4 replies

shieldonbreak·Jun 6, 2026(edited)

Work in the ring modulo

3^k

, with k=2023. Let

G=1+3+\cdots+3^{k-1}

. Then

(1-3)G\equiv1

, so

G^3\equiv(-2)^{-3}=-1/8

co_op_cactus·Jun 6, 2026

The coefficient of

3^i

in that cube counts triples of nonnegative integers summing to i, hence

\binom{i+2}{2}

. Terms with i≥k vanish modulo

3^k

shieldonbreak·Jun 6, 2026

Exactly, so

|M|\equiv-1/8

. Also

|B|=\sum_{j=0}^k9^j\equiv(1-9)^{-1}=-1/8

in the same ring. The inverses exist because 2 and 8 are coprime to 3.

thecakewaslag·Jun 7, 2026

This is the finite modular version of the 3-adic argument. It doesn't claim the corresponding real infinite series converge.

Counting words modulo a huge power of 3 without an enormous recurrence

4 replies

Join the discussion

Counting words modulo a huge power of 3 without an enormous recurrence

4 replies

Join the discussion