Brian's Programming and Math Challenges
Majority Algorithm
Imagine that there's a huge election being held to determine who is the coolest dØØd in the world. Naturally everyone's a candidate (altough some people have a better chance at winning than others.) A person must receive over half of the total votes in order to become the worlds coolest dØØd. Everyone on Earth is given a unique positive number to identify them. To vote for a particular person, you simply have to put his or her number in the ballot box.

When the election is over, we're left with the task of figuring out if anyone got a majority of the votes. Since there are so many votes to count, it's been decided that the tallying of votes needs to be computerized. All the votes have been stored in a large ROM chip. Unfortunately, the voting office only has a Timex Sinclair with 2K of RAM with which to perform its calculations. Therefore, it would be helpful if you could write a program which didn't use too much space and could determine who the majority winner is (or if one doesn't exist) without having to look at each vote in the ROM too many times (since there are so many votes.)

Formally: Given an array, A, consisting of N (N>0) positive integers, write a function which finds the integer that occurs a majority of the time in the array [if it exists] and return it. If it doesn't exits, return 0. The function must run in O(1) space and O(N) time.

Solution (pdf/postscript/html)

Fraction Counting Algorithm
We're all familiar with counting in positive integers. For instance, if I were to ask you to come up with an algorithm for printing out the integers from 1 to N, you would probably have no problem writing this algorithm. In fact, you would probably have no problem making the algorithm run in in O(1) space and O(N) time!

Now let's look at a similar problem in fractions. Given an integer N, write an algorithm which outputs all of the fractions between 0 and 1 whose denominators do not exceed N. For instance, if N were 5, your algorithm would output 1/5,1/4,1/3,2/5,1/2,3/5,2/3,3/4,4/5. Your challenge is to write this fraction counting algorithm in O(1) space and O(number of fractions) time.

Solution (pdf/postscript/html)

Coconut Divisibility Problem
Four boys go camping one weekend. While in the wilderness, the boys collect a number of coconuts. They take the coconuts back to their cabin and agree to divide them up equally before they leave the next morning. That night, one of the boys wakes up (from excitement) and decides to gather his share of coconuts right that moment. However, when he counts the coconuts he finds that the number is not divisible by 4, but by giving one coconut to the pet monkey, the remaining amount is divisible by 4, so the boy gives one coconut to the monkey and takes 1/4 of the rest for himself.

Later that night another boy wakes up (also from excitement) and decides to gather his share of coconuts right that moment (not realizing that the other boy has already taken his share.) When he counts the number of coconuts he finds that if he gives one to the pet monkey then the remaining amount will be divisible by 4, so the boy gives one coconut to the monkey (who has already disposed of the previous one) and takes 1/4 of the rest for himself.

The remaining two boys also wake up one by one in the middle of the night in order to get their share of coconuts, and they both have to give one coconut to the monkey before taking 1/4 of the rest.

In the morning, as the boys are leaving the cabin, they notice that there are still some coconuts left. Since each of them has taken their share, they're not really sure why there should be any left. Not wanting to think about it too hard, though, they just decide to split the remaining coconuts evenly since the remaining amount is exactly divisible by 4.

Question: How many coconuts were there to begin with? Give the minimum possible value.

Harder Question: What would the solution be if there were N boys instead of 4 (i.e. replace '4' in the problem with 'N')

Solution (pdf/postscript/html)

The Clown Lottery
A seemingly trustworthy ex-carnival clown offers you a special lottery ticket. The lottery ticket has 100 slots in which you must place all of the numbers 1-100. The trick is that you don't know what order the numbers should go in, and order matters.

"But wait!" The clown says. "You only need to get one number (or more) in the right position in order to win! And for every winning $1 ticket, I'll give you $1.50. That's an easy profit of 50 cents per winning ticket! I'll even spot you one million dollars so you can buy one million tickets (pre-filled completely randomly)!"

Question: Should you take the clown's offer?

More formally: Suppose the numbers 1..N are ordered randomly in a list. What are the chances that at least one number is equal to its position in the list?

Example List: 5,2,1,4,3 (in this list, 2 and 4 are equal to their position in the list since they are the second and fourth elements in the list).

Question: What does the probability converge to as N approaches infinity?

Solution

The "Usual" Dilemma
We’ve all wondered about this, right? When you go to a restaurant multiple times, should you try something new or just order your "usual"? Well, wonder no more! Thanks to the wonders of mathematics, we are now in a position to definitively answer this long-standing conundrum! (under certain idealized assumptions)

  • Assume that you’re going to eat at a restaurant t times. The menu has m items on it.
  • Assume that you can rank your preferences for each of the m items with a different score of 1,2,3,..., or m. A higher score indicates a better meal.
  • Assume that you have no idea how an item will taste/score before ordering it. If it helps with credulity, assume you don’t even know what the menu item is until you order it. i.e. they are simply listed as item 1, item 2, item 3, ... , item m, with no description.
  • Assume that after eating an item, you only learn its relative ranking among the items you have eaten and not its absolute score.
  • Assume that your preferences don’t change. For instance, you don’t get tired of eating the same item over and over.
  • Assume you order exactly one item on each visit.
  • Assume that after trying v (for variety) items from the menu, you then order your favorite meal (the one with the highest score) for the rest of your t − v visits.
  • Assume that the measure of your overall enjoyment of the t meals is expressed as the sum of the scores of each meal you ate.

Question: If you’re going to visit a restaurant t times and there are m items on the menu, how many different items v should you try in order to maximize your expected enjoyment of all t meals?

Solution

The Prisoners' Perfect Plan
A new warden has been appointed to a maximum security math prison that has 100 prisoners, all with life sentences (for dividing by 0). As you know, the warden of a math prison has it within her discretion to release the prisoners if she so chooses. This new warden decides to give the prisoners an opportunity to win their freedom. Her bargain is as follows:

Each day the warden will select one prisoner at random and invite him into a special math interrogation room. The room is pretty drab. Basically it just has a switch that controls an overhead light bulb. The prisoner is allowed to turn the light on or off. The warden never messes with the light switch. The light is initially off.

If during his visit to the room, a prisoner tells the warden that he thinks all of the prisoners have visited the interrogation room and he's right, then he wins the bargain and they can all go free! But if he's wrong, then they've lost their opportunity at freedom (and their pencil sharpener privileges).

The prisoners are given one day to plan their strategy. After that, the daily interviews begin, and the prisoners are no longer allowed to communicate with each other... except by using the light switch in the math interrogation room. Please note that neither the interrogation room nor the light are visible or audible (or tasteable, etc... etc...) to the prisoners when they're in their cells.

Questions:
  1. Can you devise a strategy for the prisoners such that they can (with 100% certainty) figure out when they've all been in the interrogation room?
  2. About how long do you think your strategy will take to execute?
  3. After how many days would there be a 99.9999% chance that all of the prisoners have visited the interrogation room?
This last question is the aspect of the problem that occurred to me while working on it and that I was the most interested in solving. Are the prisoners being foolish in their quest for a perfect plan?

Solution