IZhO олимпиада по математике 2008 года | Казахстанские олимпиады

Положим $A=\{(a_1, \dots, a_8) | a_i\in \Bbb N , 1\leq a_i\leq i+1\}\hbox{ для всех }i=1, \dots, 8\}$. Назовем подмножество $X\subset A$ * разреженным * , если для любых двух различных элементов $(a_1, \dots, a_8), (b_1, \dots, b_8)\in X$ существуют хотя бы три индекса $i$ таких, что $a_i\ne b_i$.

Найдите наибольшее возможное количество элементов в разреженном подмножестве множества $A$.