The Unapologetic Mathematician

Mathematics for the interested outsider

An Elegant Miniature

Over at The n-Category Café, David Corfield links to Noam Elkies’ “Introduction to Analytic Number Theory”, in which he discusses the theory-builder vs. problem-solver divide. It shouldn’t be surprising that I’m more of a theory builder, but I’ve solved a problem or two. Still, I get frustrated when venturing into what people have called “a collection of elegant miniatures”. Yes, they’re pretty, but I don’t see what to do with them. With the glut of Hungarians in the department here, I’m brought face to face with this a lot.

But I do appreciate them in small doses. And, coincidentally enough, while I was in San Diego I was told about a problem that had been circulating for a day or so. Something in my brain wants to say that it had even originated from Noam Elkies, but that may just be memory fail on my part from arriving in Bowling Green at about 03:30. Since I’ve managed to solve it, I thought I’d throw it out here. Thoughts can go in the comments, as can questions for clarification, but if you see a whole solution (or enough to spoil it), email it instead to me for verification. Remember, I’ve picked up the moniker “Mathochist”, and my degree gives the title “Dr” before it — without a space or an underscore or anything — and I receive my email through gmail. No, determining my email address is not the puzzle.

Here it is: given whole numbers r and b, we want to pick r red points and b blue points in the plane, subject to two conditions. The first is that no three points (whether red, blue, or a some of each) are collinear. The second takes a bit of explaining. We want to pick “blocking points” (in white) so that no red point can “see” a blue point. That is, there should be a blocking point on the line segment joining each red point to each blue point. Given r red points and b blue points, there are rb such segments, so rb blocking points would be easy. However, we want to do it with r+b-1 blocking points.

Here’s a non-example. Pick the red points at (1,0), (2,0), (3,0), and so on up to (r,0). Pick the blue points at (1,1), (2,1), (3,1), and so on up to (b,1). Then you can place the blocking points at (1,\frac{1}{2}), (\frac{3}{2},\frac{1}{2}), and so on by half-integers up to (\frac{r+b}{2},\frac{1}{2}). These r+b-1 points suffice to block all red-blue pairs. Unfortunately, all the red points and all the blue points are collinear, so it doesn’t work in general.

March 26, 2009 - Posted by John Armstrong | Uncategorized | | 14 Comments

14 Comments »

  1. Hi John,

    as a hint for your other readers:
    I was a little disappointed that the easiest possible solution works :-)

    Martin

    Comment by Martin | March 27, 2009 | Reply

  2. John wrote:

    “Still, I get frustrated when venturing into what people have called “a collection of elegant miniatures”. Yes, they’re pretty, but I don’t see what to do with them.

    As a layman may i ask

    What you “do” with the theory/ abstraction?

    p.s: this question is NOT meant to provoke. i would just like to understand what goes on beyond the theory/problem divide in math.

    Thanks,

    anon

    Comment by anon | March 27, 2009 | Reply

  3. The tongue-in-cheek answer is that we solve problems. The snide answer is to ask what you do with a painting.

    Comment by John Armstrong | March 27, 2009 | Reply

  4. http://www.research.att.com/~njas/sequences/A158794

    A158794 Multiple of 4 which are not the sum of seven positive cubes.

    212, 364, 420, 428 (list; graph; listen)

    COMMENT

    Boklan and Elkies: It is conjectured that every integer N>454 is the sum of seven nonnegative cubes. We prove the conjecture when N is a multiple of 4. It is believed that the exceptional set for Linnik’s seven cubes theorem is 5, 22, 23, 50, 114, 167, 175, 186, 212, 231, 238, 239, 303, 364, 420, 428, 454.

    REFERENCES

    Linnik, U. V.: On the representation of large numbers as sums of seven cubes. Rec. Math. [=Mat. Sbornik] N.S. 12(54) (1943), 218-224.

    Dickson, L.E.: All integers except 23 and 239 are the sums of 8 cubes. Bull. Amer. Math. Soc. 45 (1939), 588-591.

    Waring, E.: Meditationes Algebraicss� [3rd ed. (1782)]: an English translation of the work of Edward Waring, edited and translated from the Latin by Dennis Weeks. Providence, RI: Amer. Math. Soc., 1991.

    LINKS

    Kent D. Boklan, Noam D. Elkies, Every multiple of 4 except 212, 364, 420, and 428 is the sum of seven cubes, Mar 26, 2009.

    http://arxiv.org/abs/0903.4503

    CROSSREFS
    Cf. A000578, A003072, A003325, A003327, A003328, A003329, A057907, A122730.

    KEYWORD
    bref,fini,full,nonn,uned,new

    AUTHOR
    Jonathan Vos Post (jvospost3(AT)gmail.com), Mar 26 2009

    Comment by Jonathan Vos Post | March 27, 2009 | Reply

  5. And this has what to do with the problem? Jonathan, you really need a better on-topic filter.

    Comment by John Armstrong | March 27, 2009 | Reply

  6. It’s a publication from the past 24 hours by Noam D. Elkies! It’s an old problem, wit a new partial solution, and arguably one of the “elegant miniatures.” Really, I still consider that on-topic.

    Comment by Jonathan Vos Post | March 27, 2009 | Reply

  7. It’s interesting to read this from the perspective from somebody whose mathematical education is still very much in the early stages. Judging from my own experiences, even all the way up through high school students of mathematics are in the dark about the very existence of the theoreticians. Since early math education is so focused on the mechanics (which of course lends itself to the view that all mathematicians do is solve problems), I feel like bright mathematics students who don’t have a particular aptitude for clever problem solving can get scared off. A good high school math teacher should make it clear that building theory is a vital component of mathematics that one can aspire to even if they aren’t IMO-level problem solvers.

    Comment by Nick | March 28, 2009 | Reply

  8. To paraphrase Tim Gowers on “The Two Cultures of Mathematics” is the purpose of solving problems to be better able to understand the theory, or is the purpose of understanding the theory to be better able to solve the problems? To me, who both uses Math as a scientists and engineer, and publishes “pure” Math, this is a false dichotomy. Both are good.

    I tell myself sometimes that the purpose of Mathematics is INSIGHT — whether of a practical domain, or insight into abstract structure, or even self-insight as to one’s mental and aesthetic nature.

    Comment by Jonathan Vos Post | March 29, 2009 | Reply

  9. Sure, both are good. Just like both algebra and analysis are good. But some people are more attuned to one than the other. Category theory resonates with me, but I can’t stand mucking around with epsilontics. Others are the other way around.

    I’m not arguing that one side is better than the other. Only that I am better on one side than the other.

    Comment by John Armstrong | March 29, 2009 | Reply

  10. This is a fantastic problem! Moreover, it’s not just some isolated curiosity, where one might wonder what’s the point of it all — it’s connected with some exquisite algebraic geometry (which quite coincidentally I’d been thinking about recently). So it ought to appeal at least to those theory-minded algebraic geometers out there.

    “I was a little disappointed that the easiest possible solution works :-)

    I have to smile too — ‘disappointed’ would not at all describe how I felt! It’s lovely.

    Comment by Todd Trimble | March 30, 2009 | Reply

  11. I have to say, I’m not certain by what metric “easiest possible” is meant.

    Comment by John Armstrong | March 30, 2009 | Reply

  12. I can’t be certain what he meant, but I can think of some plausible measures. But to say much more might give too much away.

    Comment by Todd Trimble | March 30, 2009 | Reply

  13. I meant that your non-solution is already a very good hint. I hope I don’t give too much away if I say that one only has to modify it slightly (actually one could say by an epsilon…) in order to get a solution.
    And I thought that more or less this was the obvious first idea to solve the problem. (I agree that still the solution is beautiful and I admit that it took me some time to solve the problem, but I was a little disappointed that my very first thought about a solution turned out to be right.)

    Comment by Martin | April 1, 2009 | Reply

  14. [...] that the problem comes from The Unapologetic Mathematician, the blog written by John Armstrong, who posted the problem back in March this year. He in turn had gotten the problem from Noam Elkies, who kindly responded [...]

    Pingback by Solution to POW-13: Highly coincidental! « Todd and Vishal’s blog | July 22, 2009 | Reply


Leave a comment