Mathematical Food for Thought

  
 
 

  • About

    Serves a Daily Special and an All-You-Can-Eat Course in Problem Solving. Courtesy of me, Jeffrey Wang.
  
That’s A Lot Of Numbers. Topic: Logic/NT. Level: Olympiad. April 15th, 2006

Problem: (ACoPS 3.4.21) Initially, we are given the sequence 1,2, \ldots, 100 . Every minute, we erase any two numbers u and v and replace them with the value uv+u+v . Clearly, we will be left with just one number after 99 minutes. Does this number depend on the choices we made?

Solution: We claim that the number does not depend on the choices. Let a_1, a_2, \ldots, a_n be the numbers on the board after 100-n minutes. Define \displaystyle P_n = \prod_{i=1}^n (a_i+1) . We claim that the sequence P_{100}, P_{99}, \ldots, P_1 is constant.

Noticing that (u+1)(v+1) = uv+u+v+1 , we see that replacing u, v with uv+u+v+1 has no effect on the product P_n . Indeed,

P_{k-1} = \frac{P_k(uv+u+v+1)}{(u+1)(v+1)} = P_k

so we have P_{100} = P_{99} = \cdots = P_1 by induction. Since P_{100} is clearly constant, P_1 must be as well. Seeing that P_1 is equivalent to the remaining number, we conclude that it does not depend on the choices, as desired. QED.

——————–

Comment: Problems with invariants require you to discover something (often a sum or product) that doesn’t change with each step. The term uv+u+v should remind you of Simon’s favorite factoring trick, leading to the invariant P_n as described above.

——————–

Practice Problem: (ACoPS 3.4.23) Start with the set \{3,4,12\} . You are then allowed to replace any two numbers a and b with the new pair 0.6a-0.8b and 0.8a+0.6b . Can you transform the set into \{4,6,12\} ?

Posted in Logic, Number Theory, Olympiad || 3 Comments »

3 Responses to “That’s A Lot Of Numbers. Topic: Logic/NT. Level: Olympiad.”

  1. WLOG Says:
    April 15th, 2006 at 6:40 pm

    i know a certain person who really likes this type of problems **cough Hesterberg cough** :)

  2. QC Says:
    April 15th, 2006 at 9:36 pm

    Nice invariant.

  3. QC Says:
    April 15th, 2006 at 9:37 pm

    Oh, also:

    \sqrt{x^2 + y^2 + z^2} is invariant, so no such transformation is possible.

Leave a Reply

You must be logged in to post a comment.
Google

 

  
 
free web counters
Etronics