## Continuous Zip Code Problem February 6, 2009

Posted by keithkchan in Quiz.

This afternoon, when two colleagues and I were walking to the restaurant, we talked about the zip codes in this region. When one of my colleague said that the zip code of the contiguous region is very different (large integral difference) from the one that we are in. I began to think that how continuous we can assign the zip code.

OK. The problem can have many variants, depending on the continuity requirement. But the global continuity requirement seems to me the most natural one. That is for any contiguous regions, the difference in zip code should not be greater than some integer N. Then the first question is that does such a finite number N exists for arbitrary map. If it does exist, what is the minimal N that satisfy this requirement.

From our discussions, I thought it may be related to the well-known four colour theorem. In essence, the theorem states that for any may, four colors are sufficient to color the map so that the neighouring countries will not have the same colours. The proof of this theorem is very complicated. It has to be checked using computers. From this theorem, we know that N is at least 3. But after some trials, I think N may be well larger than 3.

At this moment I have no idea how large N can be, if it exists at all. Maybe some smart people have thought about it before and may even have solved it, I will be happy to know. But anyway, I will keep this problem in mind, it is very interesting.

Update: after making this post, I came up with a proof. Consider a graph with a circle at the centre, and with M regions contiguous to it. For any number of assigned to the central region, I can increases the number of neighbouring regions, M, indefinitely, so that N increases indefinitely. Thus N does not exist.