MathDB

2

Part of 2013 North Korea Team Selection Test

Problems(1)

The number of elements is a power of 2

Source: North Korea Team Selection Test 2013 #2

5/17/2014
Let a1,a2,⋯ ,ak a_1 , a_2 , \cdots , a_k be numbers such that ai∈{0,1,2,3}(i=1,2,⋯ ,k) a_i \in \{ 0,1,2,3 \} ( i= 1, 2, \cdots ,k) . Let z=(xk,xk−1,⋯ ,x1)4 z = ( x_k , x_{k-1} , \cdots , x_1 )_4 be a base 4 expansion of z∈{0,1,2,⋯ ,4k−1} z \in \{ 0, 1, 2, \cdots , 4^k -1 \} . Define A A as follows: A={z∣p(z)=z,z=0,1,⋯ ,4k−1} A = \{ z | p(z)=z, z=0, 1, \cdots ,4^k-1 \} where p(z)=∑i=1kaixi4i−1. p(z) = \sum_{i=1}^{k} a_i x_i 4^{i-1} . Prove that the number of elements in X X is a power of 2.
combinatorics proposedcombinatorics