L1: One school has 1000 doors and 1000 students. Initially all doors are closed. A student goes around the school and opens every door. Another student closes every second door. The next student changes the state of each third door - if it is open he closes it, if it is closed he opens it. And so on. The N-th student changes the state of all N-th doors. How many doors will be open after the last student goes around the school? Give a general formula (like a function of number of doors) and explain how you arrived to it.

L2: There is a sheet of paper with ink spilled on it. The shape of the spill is unknown and may be not contiguous. The ink covers less then one square inch of the paper. Prove that you can put a one-inch grid on the paper so that all grid intersections are not on ink.

L3: There are 10 gnomes. Each one has either black or white hat on (they don't know which one). They stand in line facing in one direction so gnome 10 sees the hats of gnomes 1 through 9, gnome 9 sees the hats of gnome 1 through 8, etc. They are asked in turn, starting from the end of the line (gnome 10), what color is the hat they wear. If they answer correctly -- they live, otherwise they get silently squashed. The gnomes hear what the ones behind them say, but don't know what has hapened to them.

Beforehand the selfless gnomes decide to come up with a plan that saves the lives of the most number of gnomes even in the case of the worst hat assignment. All pledge to follow the plan, even if they know that they surely die while saving others. What's the best plan, and what's the number of gnomes that are guaranteed to survive?