It’s been an awfully long time since I’ve posted anything; time to finally break the silence.

This problem appeared elsewhere on the internet some months ago; some of you may have already seen it. I don’t want to say right away where I saw it, because there was some commentary which included some rough hints which I don’t want to give, but I’ll be sure to give credit when the solution is published. I’ll bet some of you will be able to find a solution, and will agree it’s quite cute. Here it is:

Given integers m, n \geq 1, show that it is possible to construct a set of m + n points in the plane, let’s say x_1, \ldots, x_m, y_1, \ldots, y_n, so that no three points of the set are collinear, and for which there exist points z_1, z_2, \ldots, z_{m+n-1}, all lying on a straight line, and arranged so that on the line between any x_i and any y_j, some z_k lies between them.

So no x_i can “see” any y_j, because there’s always some z_k blocking the view. As the proposer observed, the problem would be easy if we had m n z‘s to play with, one for each pair (x_i, y_j). But here there are only m+ n-1 z‘s, so some of them will have to do more than their fair share, blocking the view between quite a few (x, y)-pairs simultaneously. Thus, you have to arrange the x‘s and y‘s so that a lot of the lines between them will be coincident at a point z, and subject to the constraint I italicized above.

Please submit solutions to topological[dot]musings[At]gmail[dot]com by Friday, July 17, 11:59 pm (UTC); do not submit solutions in Comments. Everyone with a correct solution will be inducted into our Hall of Fame! We look forward to your response.

About these ads