IMO Shortlist 1977 problem 5
Kvaliteta:
Avg: 0,0Težina:
Avg: 0,0 There are
words of length
over the alphabet
. Prove that the following algorithm generates the sequence
of all these words such that any two consecutive words differ in exactly one digit.
(1)
(
zeros).
(2) Suppose
. Let
be the exponent of
in the representation of
as a product of primes, and let
. Replace the digit
in the word
by
. The obtained word is
.
![2^n](/media/m/8/e/a/8ea40429bb1e68f68f9e7a97fd5351f7.png)
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
![\{0, 1\}](/media/m/0/c/c/0cce8478ddc4bbb2519e90b51db305b7.png)
![w_0, w_1, \ldots, w_{2^n-1}](/media/m/9/d/d/9dd77c42cb41a1a1fea8e2f2cf79e58b.png)
(1)
![w_0 = 00 \ldots 0](/media/m/4/1/8/4183a6d6a6dc04f0bc51c8b90120fde4.png)
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
(2) Suppose
![w_{m-1} = a_1a_2 \ldots a_n,\quad a_i \in \{0, 1\}](/media/m/3/1/5/315fe06f60d35578b072825400a4ab6b.png)
![e(m)](/media/m/0/d/a/0da43079a22d45a29d6062ab266cf526.png)
![2](/media/m/e/e/e/eeef773d19a3b3f7bdf4c64f501e0291.png)
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
![j = 1 + e(m)](/media/m/a/5/5/a55c7fd1b12b74d6be7018ae7b575929.png)
![a_j](/media/m/f/b/4/fb4396184a1d5c46d3bf9b21a89afa1e.png)
![w_{m-1}](/media/m/6/a/0/6a0385c797adcb34cbe4d49c8e3004f5.png)
![1 - a_j](/media/m/3/b/d/3bdea00880df74df8069dc9555bbdd74.png)
![w_m](/media/m/6/0/1/6018a4d81f3c3905d39402329032be90.png)
Izvor: Međunarodna matematička olimpijada, shortlist 1977