Invariance (Tuklas Vol. 13, No. 1 - Nov. 19, 2011)

INVARIANCE

Consider this scenario: At first, a room is empty. Each minute, either one person enters or two persons leave. After exactly \(3^{1999}\) minutes, could the room contain \(3^{1000}+2\) people?

Problems such as this present a significant level of shock factor to those who would encounter them for the first time. Of course, we can always try to use brute force in solving problems like these, but it is highly impractical. So instead of trying to deal with the mess and complexity of the problems head on, it would be wise for us to "reduce" them by only considering the essential properties or entities that such problems possess. There are many ways in which we can do this, but for this article, we are mainly focusing on determining invariants.

As the term implies, an invariant is an aspect of a problem that does not change, even if the conditions and other properties of the problem do change. It can be numeric or non-numeric in nature, though in most cases, it is found to be a numerical quantity. 

An example of an invariant can be seen in Euler's Formula. This formula states that there is a relationship between the number of edges (\(e\)), vertices (\(v\)) and faces (\(f\)) of a polyhedron without "holes", in particular \[v - e + f = 2\] Meaning whether the polyhedron is a cube, a tetrahedron or a "buckyball", the quantity \(v-e+f\) is always equal to 2, and as such, it is an invariant. 

Now let us return to the problem posed at the beginning of the article. We can start by making a general case, wherein we let \(n\) be the number of people in the room. After one minute, there will be either \(n+1\) or \(n-2\) people. Note that the difference between the two possible outcomes is 3. The next minute, the possible number people in the room can be \(n+2, n-1\) or \(n-4\). Observe that the difference between any two outcomes is either a 3 or 6. 

In the long run, we can actually conclude that, at any fixed time \(t\), the possible values for the population of the room differ from one another by a multiple of 3. 

So after \(3^{1999}\) minutes, it would be possible for us to have \(3^{1999}\) people in the room (this means that 1 person comes in after every minute.). Based on our conclusion above, the other possible populations of the room should differ \(3^{1999}\) by a multiple of 3. And since \(3^{1999}\) is a multiple of 3, hence the other population outcomes should also be a multiple of 3. This means therefore that \(3^{1000}+2\) will not be a valid population. 

The problem above gave us an example of a divisibility invariant (divisible by 3). The simplest divisibility invariant is parity, which merely refers to the oddness or evenness of a number. This concept will be explored in greater detail through the following problems. 

Let \(a_1, a_2, \ldots, a_n\) represent an arbitrary arrangement of the numbers \(1, 2, 3, \ldots, n\). Prove that if \(n\) is odd, the product \[(a_1 - 1)(a_2 - 2)(a_3 - 3)\ldots(a_n - n)\] is an even number. 

What we can do here is consider the sum of the terms.  \[\begin{align*} (a_1 - 1)(a_2 - 2)(a_3 - 3)\ldots(a_n - n) & = (a_1 - 1)(a_2 - 2)(a_3 - 3)\ldots(a_n - n)-(1+2+...+10) \\ & = (1+2+...+10) - (1+2+...+10) \\ & = 0 \end{align*} \]

The sum therefore is an invariant, since its always equal to zero (an even number), regardless of the arrangement of the numbers. Since the number of terms is odd, the only possible way for them to have an even sum is for the \(n\) terms to have at least one even number. This basically solves the problem. 

In the figure below you may switch the signs of all numbers of a row, column, or a parallel to one of the diagonals. In particular, you may switch the sign of each square corner square. Prove that at least one -1 will remain in the table.

1	1	1	1
1	1	1	1
1	1	1	1
1	-1	1	1

Let \(S\) represent the eight boundary squares (except the four corners). We note that the product of those squares is equal to -1. After every transformation, it is either none get switched (this is in the event that the sign of the corner square is altered), or two of the squares in \(S\) get switched: 

1 and 1 becomes -1 and -1,

-1 and -1 becomes 1 and 1,

1 and -1 becomes -1 and 1,

-1 and 1 becomes 1 and -1.

Since the product of the resulting pair is the same as the original pair, the product of the squares in \(S\) will always remain at -1. This means that there will always be at least one -1 in the table. 

The vertices of a cube are labeled \(a, b, c, d, w, x, y, z\) as seen in the figure. Vertices \(a\) and \(c\) are initially given a value of 1, while the rest of the vertices are given a value of 0. If you are allowed to add 1 to each of any pair of adjacent vertices, can you eventually get all the vertices to have the same value? 

You can actually get your hands dirty for this problem, and no matter what you do, you will not be able to get the desired result of making all values equal. But how can you prove this? 

We can let \(s_1 = a + c + w + y\) and \(s_2 = b + d + x + z\). Hence at the start, \(s_1 -s_2 = 2\). The end result we want is such that all the vertices will have the same value; this implies therefore that \(s_1 - s_2 = 0\). 

What happens when we add 1 to each of any pair of adjacent vertices? Notice that every time we pick such a pair, one of them belongs to \(s_1\), and the other belongs to \(s_2\). Therefore each time we perform the process, 1 is added to both \(s_1\) and \(s_2\). This makes the difference \(s_1 - s_2\) remain equal to 2, which means it is actually an invariant. 

Since the difference can never be equal to 0, thus we can conclude that we cannot get all the vertices to have the same value.

ABOUT THE AUTHOR:

Timothy Robin Teng is an Instructor at the Ateneo de Manila University. He is currently finishing his Ph.D. in Mathematics at the same university.

OLYMPIAD CORNER  

from the 17th Asian Pacific Mathematics Olympiad, March 2005

Problem: Prove that for every irrational real number \(a\), there are irrational real numbers \(b\) and \(b^{\prime}\) such that \(a+b\) and \(ab^{\prime}\) are both rational while \(ab\) and \(a+b^{\prime}\) are both irrational.

Solution: 

Let \(a\) be an irrational number. We first show that there exists an irrational number \(b\) such that \(a+b\) is rational and \(ab\) is irrational.

For this, we consider the number \(a^2\). If \(a^2\) is irrational, let \(b=-a\). Then \(a+b=a-a=0\) is rational, and \(ab=a(-a) =-a^2\) is irrational. If, on the other hand, \(a^2\) is rational, let \(b=a^2-a\) (difference between a rational and irrational number). Then \(a+b=a+(a^2-a)=a^2\) is rational, and \(ab=a(a^2-a)=a^2(a-1)\) is irrational (product of a rational number \(a^2\) and irrational number \(a-1\)).

We next show that there exists an irrational number \(b^{\prime}\) such that \(ab^{\prime}\) is rational and \(a+b^{\prime}\) is irrational. Let \[ b^{\prime}=\frac{1}{a} \text{ or }b^{\prime }=\frac{2}{a}. \]
Then \(ab^{\prime}\) is a rational number, which has a value of either 1 or 2. Now note that
\[ a+b^{\prime}=\frac{a^2+1}{a}\text{ or  }a+b^{\prime}=\frac{a^2+2}{a}. \]
Next we take the difference, \[ \frac{a^2+2}{a}-\frac{a^2+1}{a}=\frac{1}{a} \] where the result is an irrational number. This implies that at least one of \(\frac{a^2+1}{a}\) and \(\frac{a^2+2}{a}\) is irrational (both of them cannot be rational since the difference of two rational numbers is a rational number). This shows that there exists an irrational \(b\) such that \(a+b^{\prime}\) is irrational.

 

PROBLEMS

1. From 2011 subtract half of it at first, then subtract \(\frac{1}{3}\)of the remaining number, next subtract \(\frac{1}{4}\) of the remaining number, and so on, until \(\frac{1}{2011}\) of the remaining number is subtracted. What is the final remaining number?
2. In triangle \(ABC\), \(\angle A = 96^{\circ}\). Extend \(BC\) to an arbitrary point \(D\). The angle bisectors of \(\angle ABC\) and \(\angle ACD\) intersect at \(A_1\), and the angle bisectors of \(\angle A_1BC\) and \(\angle A_1CD\) intersect at \(A_2\), and so on. The angle bisectors of \(\angle A_4BC\) and \(\angle A_4CD\) intersect at \(A_5\). Find the size of \(\angle A_5\) in degrees.
3. Let \(a_1 , \ldots , a_n, b_1, \ldots , b_n\) be positive numbers, prove that \[ \sum_{i=1}^{n}{\frac{1}{a_{i}b_{i}}}\sum_{i=1}^{n}(a_{i}+b_{i})^{2} \geq 4n^{2}. \]

We welcome readers to submit solutions to the problems posed below for publication consideration. Solutions must be preceded by the solver's name, school affiliation and year level. The deadline for submission is November 26, 2011.