Gas station without pumps

2010 July 18

Exasperating problem from Sam Shah

Filed under: Uncategorized — gasstationwithoutpumps @ 23:15
Tags:

Sam Shaw posted an interesting puzzle on his blog, which I attempted to solve without reading any of the comments discussing it.  The problem is to put n equally spaced points around a unit circle, then connect chords from one of the points to all the rest.  What is the product of the chord lengths?

SOLUTION FOLLOWS:

To do the computation, I switched to complex numbers, putting the selected point at 1.

f(n) = \prod_{k=1}^{n-1} | e^{2\pi k i/n} -1|

Naturally, the first thing I did was to try small numbers, like n=2, 3, 4, and 6. This lead to a conjecture: f(n)=n.  I wrote a short Python program to check this conjecture:

from math import *

for n in range(2,30):
    prod = 1
    for k in range(1,n):
       prod *= abs( 1- e**(complex(0, 2*pi*k/n)))
    print n, prod

This code confirmed that for small values of n, the conjecture is correct to the limits of computational accuracy on my computer. Removing the “abs” term produced the stronger conjecture

\prod_{k=1}^{n-1} (1-e^{2\pi k i/n} ) = n

Now for the challenging part: why is this surprising result true?  How can I prove it? What is it a special case of?

Perhaps the most interesting thing about the n points is that they are roots of unity, so that

\prod_{k=0}^n (x-e^{2\pi k i/n} ) = x^n -1 ~.

But we are interested in everything except the trivial root at 1, so let’s divide by x-1:

\prod_{k=1}^n (x-e^{2\pi k i/n} ) = (x^n -1)/(x-1) = \sum_{j=0}^{n-1} x^j ~.

Setting x=1, we get \prod_{k=1}^{n-1} (1-e^{2\pi k i/n} ) = n

QED

It’s a nice puzzle, and it took me far too long to do.  I came up with the complex number representation quickly, and the conjecture, but it took me a long time to realize that the critical fact was the roots of unity.

6 Comments »

  1. very nice. I like the hybrid math/programming approach. It works well to provide that clue, that allows the transition from the setup to the answer, much more smoothly.

    Comment by peeterjoot — 2010 July 19 @ 04:58 | Reply

  2. […] 2) Recognition that if the points are treated as numbers in the complex plane, they are precisely the nth roots of unity, followed by exploitation of the algebra of the nth roots of unity. These methods were able to prove the conjecture. (For example: Andrew’s comment at Sam’s original post; gasstationwithoutpumps has his/her (?) own post on the subject.) […]

    Pingback by Partial Illumination for the Chords-of-an-Ellipse Problem « Research in Practice — 2010 August 31 @ 12:21 | Reply

    • This post by “Research in Practice” makes progress on the ellipse version of the problem, which I had dismissed as badly posed. He makes the problem explicit (scale the circle vertically after placing the points on the roots of unity), then comes up with a conjecture about the values, further generalizing the conjecture to other scaling factors, and making some fairly substantial progress on establishing the conjecture. It’s not done yet, but his post is worth reading.

      Comment by gasstationwithoutpumps — 2010 August 31 @ 12:37 | Reply

  3. Excuse me…I hav 1 small question about 1 thing i dont understand…Why are the points connected to the point 1,0 for all the values of n? Thank you

    Comment by Sarran Raaj — 2011 August 6 @ 07:43 | Reply

    • Sam simplified the problem since I wrote this solution, making (1,0) be the point that everything else connects to. In the original problem there were just n equally spaced points with chords to one of them. Rotating the unit circle so that (1,0) was the point everything else connected to was the first insight that lead to a solution. Rotation of the unit circle is just the selection of a coordinate system, and does not change any geometric properties like chord lengths.

      Comment by gasstationwithoutpumps — 2011 August 6 @ 08:25 | Reply


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: