content top

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.

Read More

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?

 

Read More

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:

Read More

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?

Read More

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:

Read More
content top