Разделы 
Дополнительно
Задача по математике - 789
2014-02-27 
Ð ассмотрим множество векторов #V_{16},# состоящее из всех векторов размерности 16, у которых координаты принимают значения #-1,0,1,# и количество нулевых координат в точности равно 8. Доказать, что найдётся подмножество #W \subseteq V_{16},# состоящее из попарно неортогональных векторов, размера а) не менее 12000; б) не менее 28000.
Решение:
Для решения пункта (а) достаточно рассмотреть набор #U# из векторов, у которых стоит 1 на первом месте, и ещё 7 единиц стоят на остальных местах. Очевидно, что скалярное произведение любых двух векторов из #U# положительно и #|U| = C_{15}^{7} = 6435.# Ð ассмотрев множество #U \bigcup (- U)# получим искомое. В пункте (б) рассмотрим другое множество #U.# Ð азобьём множество координат на первые 5 координат #I# и оставшиеся 11 координат #J.# Тогда #U# состоит из
• множества #U_{1}# из векторов с тремя единицами в #I# и 5 единицами в #J;#
• множества #U_{2}# из векторов с 4 единицами в #I# 1 4 единицами в #J;#
• множества #U_{3}#из векторов с 4 единицами в #I,# 3 единицами и одной - 1 в#J;#
• множества #U_{4}# из векторов с 5 единицами в #I# и 3 единицами в #J;#
• множества #U_{5}# из векторов с 5 единицами в #I,# двумя единицами и одной - 1 в #J;#
• множества #U_{6}# из векторов с 5 единицами в #I,# одной единицей и двумя - 1 в #J;#
Можно проверить некоторым перебором, что в множестве #U# любые два вектора имеют положительное скалярное произведение. Его размер #|U| = C_{5}^{3}C_{11}^{5} + C_{5}^{4}C_{11}^{4} + C_{5}^{4}C_{11}^{3}C_{8}^{1} + C_{11}^{3} + C_{11}^{2}C_{9}^{1} + C_{11}^{2}C_{9}^{1} = 14025.# Ðналогично предыдущему пункту получается множество #W = U \bigcup (-U)# из 28050 элементов.
Ð ассмотрим множество векторов #V_{16},# состоящее из всех векторов размерности 16, у которых координаты принимают значения #-1,0,1,# и количество нулевых координат в точности равно 8. Доказать, что найдётся подмножество #W \subseteq V_{16},# состоящее из попарно неортогональных векторов, размера а) не менее 12000; б) не менее 28000.
Решение:
Для решения пункта (а) достаточно рассмотреть набор #U# из векторов, у которых стоит 1 на первом месте, и ещё 7 единиц стоят на остальных местах. Очевидно, что скалярное произведение любых двух векторов из #U# положительно и #|U| = C_{15}^{7} = 6435.# Ð ассмотрев множество #U \bigcup (- U)# получим искомое. В пункте (б) рассмотрим другое множество #U.# Ð азобьём множество координат на первые 5 координат #I# и оставшиеся 11 координат #J.# Тогда #U# состоит из
• множества #U_{1}# из векторов с тремя единицами в #I# и 5 единицами в #J;#
• множества #U_{2}# из векторов с 4 единицами в #I# 1 4 единицами в #J;#
• множества #U_{3}#из векторов с 4 единицами в #I,# 3 единицами и одной - 1 в#J;#
• множества #U_{4}# из векторов с 5 единицами в #I# и 3 единицами в #J;#
• множества #U_{5}# из векторов с 5 единицами в #I,# двумя единицами и одной - 1 в #J;#
• множества #U_{6}# из векторов с 5 единицами в #I,# одной единицей и двумя - 1 в #J;#
Можно проверить некоторым перебором, что в множестве #U# любые два вектора имеют положительное скалярное произведение. Его размер #|U| = C_{5}^{3}C_{11}^{5} + C_{5}^{4}C_{11}^{4} + C_{5}^{4}C_{11}^{3}C_{8}^{1} + C_{11}^{3} + C_{11}^{2}C_{9}^{1} + C_{11}^{2}C_{9}^{1} = 14025.# Ðналогично предыдущему пункту получается множество #W = U \bigcup (-U)# из 28050 элементов.
