Lesson Math circle level problem on the hundred-handed monster Briareus

Math circle level problem on the hundred-handed monster Briareus

Problem 1

In the number line, we have marked 98 integer numbers, from 1 to 98, inclusive. Let call this set Z98.


The numbers can be in one of two states: "in" (inside of the Briareus mouth) or "out" (out of the mouth).


Briareus performs 98 steps, from 1 to 98 iclusive, changing at each step the status of some subsets of the set Z98.


The initial status of all numbers in Z98, before the counter starts counting the steps, is "out": 
                                                                                     the sheep are grazing in the field.



        From this time moment, the counter is on, 
                   counting the steps



1st step: the initial status of all numbers in Z98 is changed to opposite: 
                                                              now all the sheep are inside the Briareus mouth.


2nd step: all even numbers of Z98 obtain status "out"; odd integers of Z98 still keep status "in".


3rd step: all integer numbers multiple 3, that had status "out", obtain status "in";
          all integer numbers multiple 3, that had status "in",  obtain status "out".


4th step: all integer numbers multiple 4, that have status "out", obtain status "in";
          all integer numbers multiple 4, that have status "in",  obtain status "out".


Thus for every integer number "n" in Z98, and for every step "m" from 1 to 98, the status of "n"
is changed from the current to opposite, every time when m is the divisor of n.


From this description, you easily conclude that the status of every integer number "n" remains THE SAME 
as it was originally before step 1, if "n" has EVEN numbers of divisors;

                               and, vice versa, the status of every integer number "n" becomes OPPOSITE 
to as it was originally before step 1, if "n" has ODD numbers of divisors.


    (Here all divisors of integer "n" do count, including 1 and "n" itself).

  
                    +------------------------------------------+
                    |    It is the key idea of the solution.   |
                    +------------------------------------------+


Next, use this interesting fact from the number theory: 


      integer number n has odd number of divisors  
      if and only if the number n is a perfect square.

      In opposite, integer number n has even number 
      of divisors if and only if number n is not 
                  a perfect square.


Here again all the divisors of integer number "n" do count, including 1 and number "n" itself.


By applying this property to the current problem, we can conclude,
that after completing all 98 steps of changing status,
the only numbers that will get the opposite status comparing with
the initial status, are the perfect squares 1, 4, 9, 16, . . . , 81.


So, these 9 sheep with the perfect square numbers will have the status "in".
They will be in the Briareus mouth and will be eaten.


The rest 98-9 = 89 sheep with the numbers that are not perfect squares, will get the status "out",
same as their initial status before step 1, i.e. will be out the Briareus mouth and will remain on the field.



ANSWER.  89 sheep with the numbers that are not perfect squares1 4, 9, 16, . . . , 81, 
         will remain alive in the flock after Briareus left.