Shape Operator

Lawnmower Puzzle Solution

23 Apr 2017

I recently posted a geometry puzzle about an autonomous lawn mower steered by a rope and a peg. How much rope remains unspooled from the peg when the mower collides with it? If you haven’t seen the puzzle yet, go check out last week’s post and give it a try.

Lawnmower puzzle


Lawnmower Puzzle

08 Apr 2017

One of the joys of being an engineer at Desmos is that my collaborators occasionally bring me math problems that they need to solve to make something that they’re building work right. I love tricky little geometry problems, and I’d solve them as a hobby if they weren’t part of my job. When it helps our team get on with the work, so much the better.

In today’s post, I’d like to share one of these puzzles that came up while building Lawnmower Math, and invite you to solve it yourself.


Geometry, Algebra, and Intuition

28 Feb 2017

I have a confession to make: I have always found symbolic algebra more intuitive than geometric pictures. I think you’re supposed to feel the opposite way, and I greatly admire people who think and communicate in pictures, but for me, it’s usually a struggle.

For example, I have seen many pictorial “proofs without words” of the Pythagorean Theorem. I find some of them to be quite beautiful, but I also often find them difficult to unpack, and I never really think “oh, I could have come up with that myself.”

Here’s Pythagoras’ own proofImage by William B. Faulk, lifted from the Pythagorean Theorem Wikipedia Page. It’s worth looking at some of the many other visual proofs given there.:

Pythagoras' visual proof of the Pythagorean theorem.

I like this proof a lot. It’s fairly simple to interpret (more so than some of the other examples in the genre), and quite convincing. We have

c^2 = a^2 + b^2

because, along with the same four copies of a triangle, both sides of this equation fill up an identical area.

Even so, it’s odd to me that this diagram involves four copies of the triangle. This is one of those “I couldn’t have come up with this myself” stumbling blocks.

For comparison, I’ll give an algebraic proofHere and throughout I am using the word “proof” quite loosely. Forgive me, I am a physicist, not a mathematician. of the Pythagorean theorem using vectors. The condition that three vectors a, b, and c traverse a triangle is that their sum is zero:

a + b + c = 0

Solving for c gives

c = -(a+b)

and then dotting each side with itself and distributing gives

\begin{aligned} c \cdot c &= \left(a+b\right) \cdot \left(a + b\right) \\ &= a \cdot a + a \cdot b + b \cdot a + b \cdot b \\ &= a^2 + b^2 + 2 a \cdot b \end{aligned}

The condition that vectors a and b form a right angle is just that a \cdot b = 0, and in that special case, we have the Pythagorean theorem:

c^2 = a^2 + b^2

The thing I like about this algebraic manipulation is that it is a straightforward application of simple rules in sequence. There are dozens of ways to arrange 4 congruent triangles on a page (probably much more than dozens, really), but the algebra feels almost inevitableIt does take practice to get a feel for which rules to apply to achieve a given goal, but there are really only a few rules to try: distributivity, commutativity, associativity, linearity over scalar multiplication, and that’s about it..

  1. Write down the algebraic condition that vectors forming the sides of any triangle must satisfy.
  2. We’re interested in a function of one of the side vectors, c^2, so we solve for c and apply the function to both sides.
  3. We transform the right hand side by applying distributivity of the dot product across addition, and commutativity of the dot product, i.e. a \cdot b = b \cdot a.
  4. Right triangles in particular are a simplifying special case where one term drops out.

I also think it’s important that the algebraic manipulation embeds the Pythagorean theorem as a special case of a relationship that holds for all triangles: the Law of CosinesThe following diagram shows the relationship between the vector form of the law of cosines, c^2 = a^2 + b^2 + 2 a \cdot b, and the angle form of the law of cosines, c^2 = a^2 + b^2 - 2 |a||b|\cos C In the angle form, C is an interior angle, but in the vector form, if a \cdot b = |a||b|\cos(\theta_{ab}), then \theta_{ab} is an exterior angle. This is the origin of the difference in sign of the final term between the two forms.. If you have a theorem about right triangles, then you’d really like to know whether it’s ever true for non-right triangles, and how exactly it breaks down in cases where it isn’t true. Perhaps there’s a good way to deform Pythagoras’ picture to illustrate the law of cosines, but I don’t believe I’ve seen it.

For these reasons, I’ve generally been satisfied with the algebraic way of thinking about the Pythagorean theorem. So satisfied, I recently realized, that I’ve barely even tried to think about what pictures would “naturally” illustrate the algebraic manipulation.

In the remainder of this post, I plan to remedy this complacency.


Sunset Geometry

12 Dec 2016

Robert Vanderbei has written a beautiful series of articles and talks about a method for finding the radius of the earth based on a single photograph of a sunset over a large, calm lake.

Vanderbei’s analysis is an elegant and subtle exercise in classical trigonometry. In this post, I would like to present an alternative analysis in a different language: Geometric Algebra. I believe that geometric algebra is a more powerful system for formulating and solving trigonometry problems than the classical “lengths and angles” approach, and it deserves to be better known. Vanderbei’s sunset problem is simple to understand and challenging to solve, so it makes a nice benchmark.

Here’s Vanderbei’s sunset problem. If the earth was flat, photographs of the sun setting over water would look like this:

Flat earth sunset diagram

Notice that the reflection dips just as far below the horizon as the sun peaks above it.

Actual photographs of the sun setting over calm water (like Vanderbei’sUpdate: I should have been more careful to note that most photographs of sunsets over water actually don’t look like Vanderbei’s photograph (or my diagram) because of waves and atmospheric effects, and that sensor saturation artifacts make it hard to interpret images like this. Reproducing Vanderbei’s image may be somewhere between hard and impossible. More Below.) look more like this:

Round earth sunset diagram


Optimizing (part of) a Kakuro puzzle solver in Julia

02 Nov 2015

Solved Kakuro puzzle
A solved Kakuro puzzle.

Kakuro is a number puzzle that is a bit like a combination between Sudoku and a crossword puzzle. Imagine a crossword puzzle where, instead of words, blocks of boxes are filled with combinations of digits between 1 and 9, and instead of clues about words, you are given sums that a block of digits must add up to.

When you’re solving a Kakuro puzzle, it’s helpful to be able to generate all the combinations of m different digits that add up to a given sum. A recent thread on the julia-users mailing list considered how to implement this task efficiently on a computer.

In this post, I’d like to show a progression of a few different implementations of the solution of this same problem. I think the progression shows off one of Julia’s core strengths: in a single language, you are free to think in either a high level way that is close to your problem domain and easy to prototype, or a low level way that pays more attention to the details of efficient machine execution. I don’t know any other system that even comes close to making it as easy to switch back and forth between these modes as Julia does.

Attention Conservation Notice: If you’re looking for information on how to solve Kakuro with a computer, you should probably look elsewhere. This post is a deep dive into a tiny, tiny subproblem. On the other hand, I’ll show how to speed up the solution of this tiny, tiny subproblem by a factor of either ten thousand or a million, depending how you count, so if that sounds fun you’re in the right place.


Bisecting Floating Point Numbers

22 Feb 2014

Bisection is about the simplest algorithm there is for isolating a root of a continuous function:

  1. Start with an interval such that the function takes on oppositely signed values on the endpoints.
  2. Split the interval at its midpoint.
  3. Recurse into whichever half has endpoints on which the function takes on oppositely signed values.

After each step, the new interval is half as large as the previous interval and still contains at least one zero (by the Intermediate Value Theorem).

I want to highlight a couple of interesting issues that arise when implementing bisection in floating point arithmetic that you might miss if you just looked at the definition of the algorithm.