# Lights on a Christmas Tree

### Problem

### Solution

The state of a light depends on the number of factors of the corresponding number. All integers but squares have en even number of distinct factors. For every factor, a light was switched on/off. After an even number of such operations the light is in its original state - off.

The last light to which the algorithm applied was $\#100.$ At this point, the only lights that are on correspond to the squares between $1$ and $100,$ inclusive. There are ten of them. Thus the probability of a random light being on is $\displaystyle \frac{10}{100}=\frac{1}{10}.$

### Illustration

A step-by-step the lights on/off state is well represented by the diagram below:

### Acknowledgment

This is a paraphrase of problem 65277 from a Russian problem collection. The illustration is by Marcos Carreira.

|Contact| |Front page| |Contents| |Probability|

Copyright © 1996-2018 Alexander Bogomolny64641213 |