-1

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.

Jean-Claude Arbaut
  • 23,277
1011011010010100011
  • 709
  • Perhaps start by solving the problem by brute force for some small numbers of monkeys/baskets. See what you notice. – Ethan Bolker Jun 13 '18 at 18:30
  • I suggest you write try this out with a 10 baskets. How many baskets have a banana? Any ideas what these baskets have in common? Still stuck? Expand to 25 baskets. (Why did I suggest 25?) Have an idea. Can you explain why, generate a rule, and prove the rule? Using this rule count the bananas. – Doug M Jun 13 '18 at 18:32
  • This problem is a rather well known one. You may also hear it phrased in terms of light-switches (which are more intuitive and easier to explain than "putting a banana in if it needs one and taking it out if it doesn't"). Consider what is different between, say, the $16$th basket and the $15$'th basket. How many times are each visited? – JMoravitz Jun 13 '18 at 18:34
  • 1
    Notice that if monkeys visit a particular basket mulitple 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. – fleablood Jun 13 '18 at 18:38

2 Answers2

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.

fleablood
  • 124,253
0

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.

Mohammad Riazi-Kermani
  • 68,728