The Toughest Brain Teaser

People seem to like the brain teasers I’ve posted.  So here’s another.

I first ran across this when I was about 12 years old.  I still remember it as one of the toughest brain teasers I ever faced.

It is a very simple problem to explain, but the answer may not be obvious.  So take your time and think it through.

Find the Counterfeit Coin

You have 12 identical coins.  One of them is counterfeit.  The counterfeit coin may be heavier or lighter than the others.

Using a simple balance scale, and in just 3 weighings, identify the counterfeit coin, and determine whether it is lighter or heavier than the others.

The Challenge

Is it possible to solve this problem?

1. If “Yes” then what is the solution?
2. If “No” then why is it impossible?

Pythagorean Triplets and Diophantine Equations

Last week I posed a challenge that came from my high school computer teacher: Can you find an efficient method (or “algorithm”) to generate Pythagorean triplets?

As a reminder, a Pythagorean triplet is a set of three integers that satisfy the Pythagorean equation:

$a^2 + b^2 = c^2$

This equation is an example of a Diophantine equation. Diophantine equations are just polynomials that require the solutions to be integers. Because of that, they can be hard to solve.

The Brute Force Method

The first method most people try is the brute force method: they simply try a bunch of triplets and see if they work. Not exactly elegant, and very, very slow. But it does work.

A Substitution Method

I didn’t like the idea of having to try triplets over and over again to see if they worked. I wanted a solution you could simply calculate. Here’s the approach I came up with:

Brain Teaser: Finding Pythagorean Triplets

In an earlier post I wrote about a brain teaser from middle school.  Here’s one that is a bit more advanced.

My high school computer teacher issued us a challenge:

“I want you to write an algorithm to identify Pythagorean triplets.”

At the time, I didn’t know what an algorithm was; but a dictionary solved that problem. Sadly, the dictionary let me down on the rest of the problem.

In case you’ve forgotten your geometry, a Pythagorean triplet is any set of integers $(a, b, c)$ that satisfy the Pythagorean equation:

$a^2 + b^2 = c^2$

$(3, 4, 5)$ is an example of a Pythagorean triplet. It works because:

$3^2 + 4^2 = 5^2$

Likewise, $(8, 15, 17)$ works. Go ahead and try it.

So that’s what we want to find. But how do we find them?

Brain Teaser: Proof That 2 = 1

This is a classic brain teaser I learned in middle school (or “junior high school” where I grew up).

Let’s prove that:

$2 = 1$

Here’s the proof:

The Beauty of Flipboard

I’ve been using Flipboard on my iPad since it was first released. It’s a fantastic application, and has won a ton of awards as a result. Apple named it the 2010 App of the Year, Oprah raved about it with MC Hammer, and Time Magazine called it one of the Top 50 innovations of 2010.

So what is so great about it?