Exploring Problem Spaces

Given its primary role as a database product, it’s easy sometimes to forget what a great teaching tool FileMaker Pro can be. One of my favorite educational uses for it is building models to explore problem spaces, for example…

• viewing all possible outcomes for a problem with boundary conditions
• conducting trials to confirm the likelihood of a predicted outcome
• using “brute force” to find the solution to a complex problem

..and today we’re going to look at an example of each of these.

Dice Roll

Demo Files: Dice Roll, v1 and Dice Roll, v2

This grew out of a conversation with my youngest son a few years ago when he asked me what the odds were of getting a 7 when rolling a pair of dice. I suggested he draw a picture to visualize all possible outcomes, and he came up with a 6 x 6 grid, and then counted the 7s to determine that the odds are 6 in 36 (i.e., 1 in 6).

Well good news for time-strapped FM developers, there’s no need to manually count in today’s demos… simply choose one or more values between 2 and 12, and the odds will be displayed both graphically and numerically.

The two demos are essentially the same, except for the use of a radio button set in v1 and a check box set in v2. Here’s v1 in layout mode…

And here are the field definitions:

A few points of possible interest:

1. Grid values (result_r) are calculated by adding column number to row number

2. Odds are simplified, when possible, with the help of a custom function called gcd (greatest common divisor) written by Alexander Baier

3. The conditional formatting logic to highlight the grid squares is extremely simple:

The Monty Hall Problem

Demo file: Monty Hall Problem

Can there possibly be anyone at this late date who hasn’t heard of the Monty Hall Problem? Named for the host of the TV show Let’s Make A Deal, the problem goes as follows:

1. you are a contestant on a game show
2. you are faced with three closed doors
3. behind one of them is a valuable prize
4. behind the other two is nothing
5. you choose a door but the host does not open it
6. one of the doors you did not choose is opened and revealed to be empty
7. the host offers you the option of switching to the other closed door

What should you do?

A. stick with your original choice
B. switch to the other closed door
C. it doesn’t matter: the odds are 50/50 either way

Many people, including (in some cases) professional mathematicians, find the answer to be counter-intuitive, but you don’t need to take anyone’s word for it (or trust my screen shot to necessarily reflect reality)… download the demo and run some randomized trials to see for yourself.

Note: the script to generate trials makes extensive use of the RandomNum_SFR custom function, which was previously discussed here: Generating Sample Data

Locker Toggle

Demo file: Locker Toggle

This comes from a book called How Would You Move Mount Fuji? by William Poundstone.

In a small high school with 100 students, they have a ritual on the last day of school. Each student stands in front of their closed locker, while a teacher prepares to blow a whistle.

• At the first blow of the whistle, every student opens their locker.
• At the second blow of the whistle, every second student (2,4,6,8, etc.) closes their locker.
• At the third blow of the whistle, every third student (3,6,9,12, etc.) “toggles” their locker, i.e., opens the locker if it is currently closed, or closes the locker if it is currently open.
• At the fourth blow of the whistle, every fourth student toggles their locker; at the fifth blow, every fifth student toggles their locker, and so on until the whistle has sounded 100 times.

Question: after the 100th blow of the whistle how many lockers are open?

This is one of those brain teaser questions that interviewers at high-tech companies are fond of, and an answer like “Let me crunch the numbers and I’ll get back to you tomorrow” is not what they are looking for. Also, unless you’re being interviewed for a FileMaker-related position, they don’t want to hear “Give me five minutes with FileMaker and I’ll let you know” either… but that’s the route I opted to take.

(See below for the response the interviewer would like to hear, which did not occur to me. It turns out to be surprisingly elegant.)

Table schema in this demo is bare bones, consisting of a serial number and a 100-rep number field.

The basic idea is to create a grid consisting of 100 columns and 100 rows, with columns representing lockers and rows representing whistle blows. Here you can see the first three rows (1 = open and 0 = closed).

All the heavy lifting is performed by the following script — the initial portion clears out the table, resets the next serial number to 1, and populates the first row with all 1s (since on the first whistle blow, all 100 lockers are opened).

An interesting aspect of this puzzle is that the number of lockers toggled per whistle blow decreases quite rapidly, e.g., on whistle blow 10, only ten lockers will be toggled (10,20,30,…100), on whistle blow 20, only five lockers will be toggled (20,40,60,80,100), on whistle blow 50 only two will be toggled (50,100), and after 50 only a single locker will be toggled per whistle blow.

In fact, starting with whistle blow 3, less than 50% of the lockers will need to be toggled in any given row. So the strategy for the remainder of the script is to duplicate the preceding row, and then only visit the columns (i.e., the field repetitions) within the new row that need to be toggled. This approach is extremely efficient, allowing the 100 rows to be created and populated in approximately 1 second.

Okay, now the script has finished running and we can revisit the original question: How many lockers will be open after the 100th whistle blow?

Hmmm… the ones that are open are the perfect squares between 1 and 100. So the answer is “10 lockers will be open.” But why square numbers? What makes them special? And bear in mind that the interviewer is hoping you’ll display a flash of insight that would render a brute force approach like the above unnecessary.

If you want to ponder that for a while, stop reading now.

Otherwise, let’s look at the problem from a different angle. Like many brain teasers, the wording of the problem is designed to lead you down a winding and distracting path. The wording encourages you to think about what happens with each sounding of the whistle, but what you actually care about is the state of things after the final whistle blow.

And you don’t need to know how many times each locker was opened or closed… remember that before the first whistle sounded, all the lockers were closed. All that matters is whether a given locker was toggled an odd or even number of times… and since the question asks how many lockers will end up open, the real task is to identify the lockers that will be toggled an odd number of times.

Well it turns out the reason that most of the lockers are toggled an even number of times is because most numbers have an even number of unique factors. E.g., the number 10 has these factors: 1,2,5,10 (so locker #10 is toggled four times), and the number 12 has these factors: 1,2,3,4,6,12 (so locker #12 is toggled six times). That’s right: a locker with a given number will be toggled once for each corresponding unique factor.

But square numbers are exceptional in that they always have an odd number of unique factors, e.g., the number 9 has three unique factors: 1,3,9 and the number 16 has five: 1,2,4,8,16.

So the answer the interviewer was hoping to hear is…

Most numbers have an even number of unique factors, so after 100 whistle blows, most of the lockers will have been toggled an even number of times and returned to their original closed state. But the lockers corresponding to square numbers will be open, due to having an odd number of unique factors, and therefore having been toggled an odd number of times. Since there are ten square numbers between 1 and 100, the answer is 10.