I have been doing various problems from Putnam and Beyond, but I think it's time to post about a new section, Invariants. An invariant is simply something that does not change. I'll give an example of how they can be used to solve contest problems:
67. An ordered triple of numbers is given. It is permitted to perform the following
operation on the triple: to change two of them, say a and b, to (a + b)/
√2 and (a − b)/√2. Is it possible to obtain the triple (1,√2, 1 +√2) from the triple
(2,√2, 1/√2) using this operation?
Let's say we start with a triple (x,y,z), what we can do is find something that does not change when we apply our operation, and if that something is different for our beginning and desired end, then we are done, and we cannot go to that end.
Our invariant turns out to be I(x,y,z)=x^2+y^2+z^2. As
((a + b)/√2)^2 + ((a − b)/√2)^2=(1/2)((a+b)^2-(a-b)^2)=a^2+b^2
Therefore, whichever two numbers from (x,y,z) we pick as our a and b, the sums of their squares are the same.
t I(1,√2, 1 +√2)=6+2√2
and I(2,√2, 1/√2)=6+1/2, which are definitely not the same thing, so we are done.
No comments:
Post a Comment