Gru has 50 minions. The minions have become increasingly upset with the government and have
starting forming rebel cells. The minions will only form. a cell if it passes the following criteria:
1. Each cell contains an odd number of minions.
2. Every pair of cells has an even number of minions in common.
What is the largest number of cells that could be formed?
The largest number of cells that could be formed is:
Hints:
Linear algebra is often first done with real numbers ℝ. However, linear algebra can also be done
if we restrict to just using integers. The most common symbol for integers is ℤ. Furthermore,
linear algebra can be done on some subsets of the integers, for example {0,1} = ℤ2. For ℤ2
addition and multiplication are defined as usual except that 1 + 1 = 0. For this question, we
only need two symbols: a 0 to represent that a minion is not in the cell and a 1 to represent when
the minion is in the cell. Also, in ℤ2 a 0 represents an even amount and a 1 represents an odd
amount. This means instead of ℝ50 or ℤ50 we will use ℤ250.
Number the minions from 1 to 50 and let the cells be 𝑣1,𝑣2,…,𝑣𝑚 ∈ ℤ250; if minion 𝑗 is in cell 𝑣𝑖
then the 𝑗th position of 𝑣𝑖 is a 1 otherwise it is a 0. For example, say minion 3 is in 𝑣1 but not
𝑣2 then:
In other words, a 1 means the corresponding minion is in 𝑣𝑖 and a 0 means the corresponding
minion is not in 𝑣𝑖.
To complete the problem, show that 𝑣1,𝑣2,…,𝑣𝑚 are linearly independent.