Icosahedroid wrote:

Your proof is flawed. Your conclusion is "After this, the sixth group of four would have to include four members from other groups.", but this is not a contradiction to your assumption!

If 1 means a hospital must be on duty for emergencies and zero means conversely that a hospital must not be on duty for emergencies then two solutions are 1111000000000000 0000111100000000 0000000011110000 0000000000001111 1000100010001000 0100010001000100 0010001000100010 0001000100010001 0001001001001000 0100000100101000 0010010000011000 0010000110000100 0001100000100100 1000001000010100 0001010010000010 1000000101000010 0100100000010010 0100001010000001 0010100001000001 1000010000100001 or for example 1111000000000000 0000111100000000 0000000011110000 0000000000001111 1000100010001000 0100010001000100 0010001000100010 0001000100010001 0010000101001000 0001010000101000 0100001000011000 0001001010000100 1000000100100100 0010100000010100 0100000110000010 0001100001000010 1000010000010010 0010010010000001 1000001001000001 0100100000100001

That's more like it! I found out through my father that this situation actually corresponds to the one of a speedway championsship. (With 16 drivers, 20 heats with 4 in each, and everyone meets the other exactly once) Did you find a pattern, or was it just pure "guesswork"?

I found the solutions from a Finnish math discussion forum. It was said that the original solver wrote some Fortran code.

Here's a different way of finding a solution if you know a bit of algebra: Let $ Q$ be the finite field of $ 4$ elements. We can associate the $ 16$ hospitals with the $ 16$ points $ (x,y)$, where $ x$ and $ y$ are elements of $ Q$. This $ 4 \times 4$ grid contains $ 20$ lines corresponding to equations $ ax + by = c$. (There are $ 5$ possible "slopes": vertical, and one for each element of the field, and each slope has 4 parallel lines). Each pair of points is on exactly one line.

kevinatcausa wrote: Here's a different way of finding a solution if you know a bit of algebra: Let $ Q$ be the finite field of $ 4$ elements. We can associate the $ 16$ hospitals with the $ 16$ points $ (x,y)$, where $ x$ and $ y$ are elements of $ Q$. This $ 4 \times 4$ grid contains $ 20$ lines corresponding to equations $ ax + by = c$. (There are $ 5$ possible "slopes": vertical, and one for each element of the field, and each slope has 4 parallel lines). Each pair of points is on exactly one line. Wow! Thanks a lot I don't know why you want to let $ Q$ be the "finite field of $ 4$ elements" instead of just $ \{1,2,3,4\}$ though. Seems less intuitive to me

If you just tried to work on the grid modulo $ 4$, the "line" going through $ (0,0)$ and $ (1,2)$ (which you would naturally want to extend to $ (2, 2 + 2) = (2, 0)$ and $ (3,2)$ ) and the line through $ (0,0)$ and $ (1,0)$ intersect in more than one point. Essentially this is because you can't do division modulo $ 4$. The line through $ (0,0)$ and $ (2,0)$ should have a slope satisfying $ 2m = 0$, but this doesn't uniquely determine $ m$. By moving to a field, we guarantee that this equation has a unique solution for any two points not sharing the same $ x$ coordinate. On a slight tangent: For any $ q$ which is a prime power, the same argument gives an arrangement with $ q^2$ hospitals (points) and $ q^2 + q$ shifts (lines). Such a structure is known as an affine plane. The argument breaks down when $ q$ is not a prime power, because then there are no fields of order $ q$. It's a rather infamous open problem to show that if $ q$ is not a prime power, then you can not find such an arrangement with $ q^2$ points and $ q^2 + q$ lines. The most recently solved case was $ q = 10$, which required an extensive computer search. Even $ q = 12$ remains open.

This is an easy application of balanced block designs.It is well-known that a projective plane of order $4$ exists and that a affine plane if order $4$ is the reminder design of a projective plane of order $4$ so we have a $2-(16,4,1)$ design which is exactly what the problem is asked us to do.