fundamental theorem of arithmetic word problem

Question

Hi here is the question I have in hand:

There are $1000$ empty baskets lined up in a row. A monkey walks by, and puts a banana in each basket, because this is a word problem, and that is what a monkey would do in this situation. There is an unlimited supply of bananas. A second monkey walks by, and removes a banana from every other basket, starting with the second basket. I may not have mentioned there are also $1000$ monkeys. Monkey $\#3$ walks by. Starting with the third basket, and visiting every third basket thereafter, this monkey removes a banana from any basket that contains a banana, and places a banana into any basket that needs one. (Monkeys don't think in terms of, "this basket is empty", they just think "this basket needs a banana".) Anyway, the fourth monkey goes by, doing the same thing to every fourth basket. This continues all afternoon until all $1000$ monkeys have walked by the $1000$ baskets. How many bananas are in baskets?

So, to my understanding this clearly has something to do with prime factorization. My thought process is,

If we take

$$1000 = 2^3 \cdot 5^3,$$

we can obtain using divisor function and multiplication principle

$$d(1000)=(3+1)(3+1)=4\cdot 4=16,$$

telling us that there are $16$ divisors of $1000$.

My problem is, how do I account for "every fourth basket" and so on? How do I conclude that there are $x$ number of bananas left? A little lost as to how I proceed in this case.

Answer 1

Hint: Notice that if monkeys visit a particular basket multiple times the first monkey will add, the second monkey will subtract, and the third will add and so on.

In the end the basket will have $0$ bananas if an even number of monkeys visit it and $1$ if an odd number of monkeys will visit it.

So this leads to the question.... which baskets will be visited by an even number of monkeys and which will be visited by an odd number of monkeys?

The total number of bananas will be the total number of baskets visited an odd number of times.

So this reduces to: Which baskets are visited an odd number of times; and how many are there.

Notice, monkey #$k$ only visits multiples of $k$ and so basket number $m$ is only visited by monkeys whose numbers divide $m$.

So the question reduces further to: Which numbers have an odd number of divisors and which numbers have an even number of divisors. And how many numbers with odd number of divisors are there in the numbers up to $1000$.

ANd that... can be determined purely logically.

Final hint: If $k |m$ then $\frac km|m$ as well.

Answer 2

The number of divisors for $$n=p_1^{\alpha _1} p_2^{\alpha _2}...p_k^{\alpha _k}$$ is $$(\alpha _1 +1) (\alpha _2 +1)...(\alpha _k +1)$$

If a number is a perfect square then it has an odd number of divisors.

The positive integers which are perfect squares are the ones which are visited an odd number of times, so they will be associated with a banana in baskets.

These are baskets number$$ \{1,4,9,16,,,,961\}$$ and there are 31 one of those.

Thus there will be 31 bananas left in those baskets.