MathDB

Error correcting codes: differing at three positions

Source: Bundeswettbewerb Mathematik 1971, round 2 problem 2

June 14, 2006

combinatorics proposedcombinatorics

Problem Statement

The inhabitants of a planet speak a language only using the letters

A

and

O

. To avoid mistakes, any two words of equal length differ at least on three positions. Show that there are not more than

\frac{2^n}{n+1}

words with

n

letters.