Winter/December 2010

As Archimedes famously observed and as every child on a seesaw reconfirms, if you put a heavy object far out on a lever arm, it will exert a twisting influence around any support. That twisting influence is called “torque” and is equal to the weight times the distance (the angle also comes in, but that does not concern us here). If the object is to the left of the fulcrum, the direction of the torque is counterclockwise, and vice versa. To compute the torque around a support simply sum all the torques of the individual objects.

For example, if a 10 meter board weighs 2 kilograms and its center of mass is at its middle, and we put a fulcrum at 3 meters, then the board will twist clockwise with a torque of 3x2=6 kilogram-meters. If we put a 5-kilogram weight at the very left end of the board, it will cause a counterclockwise torque of 5x3=?15 kilogram-meters. The net torque will be counterclockwise 15–6=?9 kilogram-meters.

Puzzle No. 1:

You are presented with a straight, evenly weighted board 20 meters long and weighing 3 kilograms. The middle of the board (10 meters from the left end) is the center of mass. We call that position 0. So possible positions range from –10 to +10. The board is supported at –1.5 and +1.5 by two equal supports both 10 meters from a flat floor.

On the board are 15 packages at various positions. Remove the packages one at a time in such a way that the board rests on both supports without tipping. The board will tip if the net torque around the left support (due to the packages and the board) was counterclockwise or the net torque around the right support was clockwise.

Suppose there are 6 packages at positions –8, –4, –3, 2, 5, 8 and having weights 4, 10, 10, 4, 7, 8. Before reading on, try to figure out how to remove the packages so that the board never tips. 

Solution:

First remove the package at position -4, then at 8, then at -8, then at 5, then at -3 and finally at 3.

Puzzle No. 2: 

There are 15 packages, some are at the same positions relative to the center but side-by-side across the board (so you can remove them in any order; see the table).

Package Position Weight 1 -8 4 2 -6 8 3 -6 1 4 -4 5 5 -3 10 6 -3 2 7 -2 2 8 1 10 9 2 9 10 2 5 11 3 3 12 5 9 13 5 1 14 8 5 15 8 10

Find an order of removing packages such that the board never tips.

Try this game interactively: Tyler Neylon has developed a two-person No Tipping video game.

Solution:

One way to keep the board from tipping is to remove packages in this order: 8, 14, 2, 12, 1, 15, 5, 4, 9, 7, 11, 6, 13, 3, and 10.

Fall/September 2010

Can You Hash This Out?

A puzzle from The Ohio State University

Consider a data structure that uses hashing to efficiently store and retrieve integers. Prove that for any hash table size greater than 2, even the usually-reliable prime numbers, “hash(x) = x^2” is a poor hash function. More specifically, prove that there will always be an empty bucket.

—Dr. Bruce W. Weide and colleagues at The Ohio State University

Solution:

Let n be an integer greater than 2. We wish to show there exists an integer y in the interval [0,n) such that for all integers x, x^2 mod n does not equal y. By the division algorithm we can write any x as qn+r where r is in [0,n), and (qn+r)^2 mod n is r^2, so we can assume without loss of generality that x is in [0,n). There are thus n many values possible for x, so it suffices to show that two of them “hash to the same bucket,” i.e., that there exist x1 and x2 in [0,n) such that x1^2 and x2^2 are congruent modulo n. Let x1 = 1. x1^2 mod n = 1. Let x2 = n-1. Note that x2 does not equal x1 because n>2. x2^2 = n^2-2n+1, which we now see is congruent to 1 mod n. QED.

Summer/June 2010

Can Oleg beat Erdös?

A puzzle from Carnegie Mellon University

Oleg and (the ghost of) Erdös play the following game. Oleg chooses a non- negative integer a1 with at most 1000 digits. In Round i the following happens:

Oleg tells the number ai to Erdös, who then chooses a non negative integer bi, and then Oleg defines ai+1 = |ai ? bi| or ai+1 = ai + < EM>. Erdös wins if a20 is a power of 10, otherwise Oleg wins. Who is the winner, Oleg or Erdös?

—Written by Tom Bohman, Oleg Pikhurko, Alan Frieze, and Danny Sleator at The Puzzle Toad

Solution:

This solution is a bit long, so it's on a PDF for your convenience.