6
$\begingroup$

There was a security guard in a bank. In front of him were 100 lockers in rows of 10. He thought of something as he saw all the lockers were closed. He started opening all the lockers whose lock numbers were multiples of 1, then closed all lockers whose number was a multiple of 2,and did the same for 3 and so on. If the locker was open, he closed it, if closed, opened it. He went to open multiples of 1 (all),then 2,4,6,8...and then 3,6,9.. And then finally reached 100.

After all the opening and closing,in the end, how many lockers are open and how many closed?

$\endgroup$
8
  • 1
    $\begingroup$ The number of divisors determines the status of the locker at the end. $\endgroup$
    – Sigur
    May 31, 2013 at 23:55
  • 1
    $\begingroup$ I know that the perfect square lockers will be open, primes closed, but how will you ensure that an amount of lockers are opened or closed? $\endgroup$
    – Rohinb97
    Jun 1, 2013 at 0:00
  • 2
    $\begingroup$ What happens if the locker number has an even number of divisors? Will it be closed or opened at the end? $\endgroup$
    – Sigur
    Jun 1, 2013 at 0:02
  • 1
    $\begingroup$ @Sigur I can see by observation that all the perfect squares have an odd number of divisors, and the rest have an even number. But how can that be proven to always be the case? $\endgroup$ Jun 1, 2013 at 1:29
  • 3
    $\begingroup$ @ZettaSuro If $n$ is not a perfect square then for every divisor $x$ there is another divisor $\frac{n}{x}$ of $n$ such that $x \neq \frac{n}{x}$ (since $n$ is not a perfect square). What this means is that the distinct divisors of $n$ come in pairs and thus the number of these must be even. Also, if $n$ is a perfect square then there is exactly one number $y$ such that $y = \frac{n}{y}$. All other divisors again come in pairs. $\endgroup$
    – Alraxite
    Jun 1, 2013 at 15:04

1 Answer 1

10
$\begingroup$

Hint: How many divisors does $7$ have? How many divisors does $8$ have? How many divisors does $9$ have? What's special about $9$ and why?

Further Hint: If $a$ divides $n$, then $n = ab$ by definition. For example, $2$ divides $8$ because $8 = 2 \cdot 4$. In this way, divisors arise naturally in pairs.

If the numbers appearing in these pairs are all distinct, then there will be an even number of divisors. For example, the divisors of $8$ (in pairs) are $1$ and $8$ and also $2$ and $4$.

What about when the numbers in the pair aren't distinct? This can only happen if $n = a \cdot a$ for some $a$ (that is, if $n$ is a perfect square). For example, the divisors of $9$ (in pairs) are $1$ and $9$ and also $3$ and $3$. We don't count the $3$ twice, of course, so we get an odd number of divisors.

$\endgroup$
13
  • $\begingroup$ Are you hinting me and testing me or telling the answer? $\endgroup$
    – Rohinb97
    May 31, 2013 at 23:57
  • 3
    $\begingroup$ @Rohinb97, I think Austin has given you one heck of a hint. Now you mull on it. $\endgroup$
    – DonAntonio
    May 31, 2013 at 23:58
  • $\begingroup$ See my comment above. How will you ensure that 78 or 53 is open or closed? Taking out prime factors is too lengthy, and perfect square and primes only solve half of problem. $\endgroup$
    – Rohinb97
    Jun 1, 2013 at 0:10
  • 1
    $\begingroup$ @Rohinb97 A locker will be flipped when any of its divisors is encountered, not just the prime ones. Divisors of $7$: $1$, $7$. Divisors of $8$: $1$, $2$, $4$, $8$. Divisors of $9$: $1$, $3$, $9$. $\endgroup$ Jun 1, 2013 at 1:31
  • 1
    $\begingroup$ Rohin, have you looked at the comment from @Alraxite? $\endgroup$ Jun 1, 2013 at 23:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .