SOLUTION: The hundred-handed monster Briareus was hungry and attacked a flock of 98 sheep. He didn't want to eat them all, so he developed a strange way to decide which ones to eat. With his

Algebra.Com
Question 1209438: The hundred-handed monster Briareus was hungry and attacked a flock of 98 sheep. He didn't want to eat them all, so he developed a strange way to decide which ones to eat. With his hundred hands he lined the sheep up in front of him and attached tags labeling the sheep from 1 to 98, from left to right. First he crammed all the sheep into his mouth. Then he spat out all the even-numbered sheep. Then for every sheep with a number divisible by three, he stuffed it into his mouth if it was outside or spat it out if it was already inside. He did the same for every sheep with a number divisible by 4, 5, and so on up to 98. At the end, he devoured the sheep that were left in his mouth. How many sheep were left in the flock after Briareus left?
CC12#3

Found 2 solutions by ikleyn, math_tutor2020:
Answer by ikleyn(52786)   (Show Source): You can put this solution on YOUR website!
.
The hundred-handed monster Briareus was hungry and attacked a flock of 98 sheep.
He didn't want to eat them all, so he developed a strange way to decide which ones to eat.
With his hundred hands he lined the sheep up in front of him and attached tags
labeling the sheep from 1 to 98, from left to right.
First he crammed all the sheep into his mouth. Then he spat out all the even-numbered sheep.
Then for every sheep with a number divisible by three, he stuffed it into his mouth
if it was outside or spat it out if it was already inside.
He did the same for every sheep with a number divisible by 4, 5, and so on up to 98.
At the end, he devoured the sheep that were left in his mouth.
How many sheep were left in the flock after Briareus left?
~~~~~~~~~~~~~~~~~~~~~~~

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.

Solved.


////////////////////////////////


There is a TWIN problem to it, so called the "locker problem".

You can see my solution of the "locker problem" in this site/forum under the link

https://www.algebra.com/algebra/homework/proportions/Proportions.faq.question.1132246.html

https://www.algebra.com/algebra/homework/proportions/Proportions.faq.question.1132246.html



Answer by math_tutor2020(3817)   (Show Source): You can put this solution on YOUR website!

Answer: 89 sheep

Explanation

This problem is practically identical to the locker problem
https://math.stackexchange.com/questions/2017047/the-locker-problem-why-squares
and also the light switch problem
https://math.hmc.edu/funfacts/toggling-light-switches/
They are basically the same idea just with a different coat of paint so to speak.

Any non-perfect square has an even number of factors. This leads to an even number of swaps.
For instance sheep number 6 goes free since it has four swaps (due to the four factors 1,2,3,6)
This sheep starts outside and ends outside.

Any perfect square has an odd number of factors, so those sheep numbers have an odd number of swaps.
Those unfortunate sheep start outside the mouth and end up eaten.

There are 9 perfect squares between 1 and 98 since 9^2 = 81 is the largest perfect square of the list.
9 sheep are eaten and the other 98-9 = 89 sheep survive.

--------------------------------------------------------------------------

Another approach

Let's look at a smaller flock say of 10 sheep.
The monster places all of them into its mouth.
1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Erase the even numbers
1, 3, 5, 7, 9

Then go through the multiples of 3 between 1 and 10.
If you find 3, 6, or 9 in that previous list, then erase it.
Otherwise introduce it back into the list.
We go from
1, 3, 5, 7, 9
to
1, 5, 6, 7

Now go through the multiples of 4.
If you find 4 or 8 in the previous list above then erase it. Otherwise add it in.
We go from
1, 5, 6, 7
to
1, 4, 5, 6, 7, 8

Keep this process going until reaching 10.


Here's the full process
RoundSheep In Mouth
11, 2, 3, 4, 5, 6, 7, 8, 9, 10
21, 3, 5, 7, 9
31, 5, 6, 7
41, 4, 5, 6, 7, 8
51, 4, 6, 7, 8, 10
61, 4, 7, 8, 10
71, 4, 8, 10
81, 4, 10
91, 4, 9, 10
101, 4, 9

We see that the perfect squares remain.
These sheep are eaten. The others go free.

Applying this idea to numbers 1 through 98 will show that 1, 4, 9, 16, 25, 36, 49, 64, 81 are eaten.
There are 9 of those values so 98-9 = 89 sheep go free.
It might help to make a 10 by 10 grid of numbers from 1 to 100. Cross off 99 and 100 since the list ends with 98.

RELATED QUESTIONS

The hundred-handed monster Briareus was hungry and attacked a flock of 98 sheep. He... (answered by Solver92311)
The hundred-handed monster Briareus was hungry and attacked a flock of 98 sheep. He... (answered by ikleyn)
A farmer has 2494 sheep and 2193 lamb. He farms them into flocks, keeping sheep and lamb... (answered by Edwin McCravy)
In a gaggle of geese and a flock of sheep, there are 98 eyes and 162 legs. How many geese (answered by Earlsdon)
A goat and a sheep can eat all the grass on a field in 90 days. A sheep and a cow can eat (answered by ankor@dixie-net.com)
A flock of sheep which increases in size by 15% every year. If there are currently 48... (answered by ankor@dixie-net.com)
A shepherd had an unfortunate experience. He was looking after a number (n) of sheep... (answered by stanbon)
A shepherd had an unfortunate experience. He was looking after a number (n) of sheep when (answered by robertb)
A farmer bought some sheep for $2100. Two sheep died, and he sold the rest for $30 more a (answered by ikleyn,greenestamps)