 ## Finding the Counterfeit Coin

I wrote about a brain teaser I encountered as a kid and challenged you to figure out if it has a solution, and if so, what that solution is.

That brain teaser works like this:

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.

It’s a tricky problem, and I remember being stumped for a long time when I first encountered it as a kid.  But it can be solved.

There are twenty-four possible cases.  Our solution must uniquely identify each possible case.

Here is the solution.

## 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? $2 = 1$ 