Solve at least one puzzle from each section and get a free lunch at a place of your choice in the vicinity of our San Diego office (some restrictions apply). Please solve all of them by yourself, no teamwork here. Mail your answers to puzzles@divo.com.

Puzzles

Logical Puzzles
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?

Software Puzzles
S1: There is a link list of identical structures. Each element of the list has a pointer to the next element. There are no back pointers. The head of the list is unknown, but you have a pointer to one of the elements in the middle of the list. How would you delete this element and free the unused space? In other words you need to build the same link list but without one particular element. You can assume that at the moment no other programs reference any list elements. 'C' code may be a good answer.
S2: You have a link list of unknown length. The last element of the list points to NULL. You know the head of the list. There is a suspicion that due to a software bug one of the elements points back to one of the previous elements. You may say that link list loops. Design an algorithm to determine if this is true using a very limited amount of memory.

Firmware Puzzles
F1: You have an embedded system in which all the memory and all internal registers already contain some useful data. How will you swap the contents of two internal registers R1 and R2 without destroying any data? Generic assembly commands may be used. (It turned out to be a real-life problem. We actually had to use it in one of our projects).

Hardware Puzzles
H1: Build a three-input XOR element from eight two-input AND-NOT elements.