Missing Keys in the Pocket

I have recently encountered an interesting problem online, which requires knowledge of conditional probability to solve.

You leave your apartment groggily one morning, closing the door behind you. Suddenly, you are hit by a terrifying question: Do you have your keys, or are you now locked out?

You stand there thinking about it for a few seconds, before deciding that yes, you probably have your keys, further estimating that 80% of the time, you have them. You also decide that there is an equal chance of your keys either being in your left pocket or your right pocket, and if they aren’t in either pocket then you don’t have them at all.

Slowly, perversely enjoying the sweat, you slide your hand into your right pocket, and find that your keys are not there. What should you now think is the probability that your keys are in your left pocket? 

The answer:

Two-thirds. To solve this without (much) explicit calculation, imagine all the scenarios where your right pocket is empty. 60% of the time, your right pocket will be empty (20% of the time because you forgot the keys, and 40% of the time where you remembered the keys but they were in the left pocket). The given information puts you in this 60%. Of this 60%, 2/3 of the time you actually have the keys. 

Of course, the above could be expressed more elegantly in equations.

Riddles about Pants and Shorts

One day I met four men, only one of whom was wearing purple pants. Each of them made one statement, then left.

A: At least two of us are lying.
B: The purple pants person is lying.
C: Everyone here is lying.
D: Only one of the other people is lying.

Who is wearing the purple pants?

---

On another day, I met another three people, only one of whom was wearing scarlet shorts. They made one statement each, and then left.

A) B wears the scarlet shorts!
B) A wears the scarlet shorts!
C) If B is lying, so am I. If B is telling the truth, so am I.

Who wears the scarlet shorts?

Problems with Friends

A is a friend of B if and only if B is a friend of A.

Problem 1:
There are N people in the world, N > 1. Is it possible for everyone to have a unique number of friends?

---

A person is popular if none of his friends have more friends than him.
A person is a loner if none of his friends have less friends than him.

Problem 2:
In general, are there more loners or popular people?

Page Flipping in the Lecture Halls

One lecturer likes to provide lecture notes consisting of many slides. As it is costly to print out that many number of pages, most students fit multiple slides onto a single page to reduce the number of pages needed.

A useful consequence of fitting multiple slides on one page is that one only needs to flip the page every X slides, where X is the number of slides on one page. This itself leads to the interesting phenomenon of there being a loud series of page flipping sounds every X slides, since most students need to flip the page to get to the next slide.

One day, I fell asleep during the lecture. I was awoken by the sound of page flipping. Apparently, the lecturer had just advanced past a slide. No worries, time to pay attention. The lecturer continued to teach, and slowly finished two more slides. Another loud series of page flipping sounds echoed through the lecture hall. Then he taught another slide, and when he was done many students began flipping their pages as well.

Glancing about myself, I suddenly realized that students tended to fit 4, 6, and 9 pages onto a slide. And, knowing that the lecturer had not taught past slide 50, I was able to deduce which slide the lecturer was on when I woke up.

Sweets Sharing Puzzle

Two kids (who are not goats), Alice and Bala, have 100 sweets to share between themselves. However, they cannot agree on how to split the shares. Because of their arguing, a random authority figure arrives to impose order. The authority figure demands for Alice to make a sharing proposal (in the form of a sweet split) to Bala, who then has the choice to accept the proposal or not. If Bala does not accept the proposal, he can then make a counter-offer to Alice. This process of offering and counter-offering proceeds back and forth until a proposal is accepted. However, the authority figure, for his troubles, will levy a "friendliness tax" of 20 sweets each time a proposal or counter-proposal is rejected, thus reducing the number of sweets to be shared.

Now, assuming that both Alice and Bala are perfect logicians, and that their aim is to maximize their sweets, what sweet split would Alice make as her first proposal?

Chinese Blackjack (Ban-luck)

Chinese Blackjack, otherwise known as "Ban-Luck" to some Singaporeans, is interesting in that it is an almost symmetric game between the player(s) and the dealer. This is because the payouts and scoring rules are identical for both player and dealer, which contributes to the simplicity of the game. In fact, if the dealer chooses to play in a particular fashion, namely hitting his cards before revealing the players' hands, then it does become a perfectly symmetric game.

Conversely, a dealer's house advantage comes solely from being able to selectively reveal some players' hands before hitting. In other words, the dealer has an advantage in that he is able to first beat hands which are likely to be weaker (by being busted), and that he is able to further build up his hand to confront stronger hands.

Out of a pure curiosity, I was considering some potential strategies for Chinese Blackjack. However, most player strategies are likely to have a minimal impact, due to the inherently limited strategic nature of the game. Chinese Blackjack forces the player to draw til at least 16, in which case it is (by statistical reasoning) unwise to draw further. The only exception to this rule is when one has a 'soft' hand, comprising of one Ace. Though I have yet to perform a through analysis of the mathematics, I believe that it is better to hit in this case. There is a small chance of improving one's hand, but the main issue is to confound the dealer's opponent model by tricking him into believing that you have a busted hand.

As a dealer, there is much more room for strategic analysis. It is quite possible to compute, via extended Monte Carlo simulation, the probability of a 4, 3 card hand being busted (assuming the basic opponent model given by the hit-til-16 rule). Furthermore, with some computing power or pre-computed tables, it is possible to obtain the precise odds of a player's hand being superior to yours, and the odds of a drawn card improving your hand, given the already exposed hands. However, I have my doubts regarding the feasibility of such implementations.

Proofs of Arithmetic Progression

Challenge:

Find as many proofs of the arithmetic progression; i.e. prove 1 + 2 + 3 + 4 + ... + n = 0.5 * n * (n + 1)

I have thought of four proofs, as detailed below.

---

Proof 1: Proof by Pairing

We pair the first and last elements, then the second first and second last elements, and so on. Each pair will have the same sum, since the earlier element gains 1 while the later element loses 1. Now, divide any pair by half. If there are even number of elements, all elements will be paired, and since each pair is the same, the average is found by diving any pair by half. Now, if there are odd number of elements, the remaining element, lying in the center of the sequence, will have the same value as the half of any pair, and this also yields the average.

Having the average, the sum can be found by simply multiplying by the number of elements, which is n. Hence,

Sum = 0.5 * (first element + last element) * (number of elements)
==> Sum = 0.5 * (n + 1) * (n)

---

Proof 2: Proof by Mathematical Induction

Suppose that the sum for a sequence (1 + 2 + ... + n) is equal to 0.5 * n * (n + 1) for some value of n = k.

Then, for the sum of a sequence (1 + 2 + ... + (k +1)), we have:
Sum = (1 + 2 + ... + k) + (k + 1)
==> Sum = 0.5 * k * (k + 1) + (k + 1)
==> Sum = 0.5 * (k + 2) * (k + 1)

Hence, if the identity is valid for n = k, it is also valid for n = k+1.

Now, consider n = 1.
Sum = 0.5 * (1) * (1+1) = 1.
Hence, it is true for n=1 ==> true for all n.

---

Proof 3: Proof by Square

Consider the following image.

A (n+1) by (n+1) square can be broken up into three pieces; n + 1 unit squares, and two arithmetic progressions of (1 + 2 + ... + n). Using this relation,

(n + 1) ^ 2 = (n + 1) + 2 * Sum
==> Sum = 0.5 * ((n + 1) * (n + 1) - (n + 1))
==> Sum = 0.5 * (n) * (n + 1)

---

Proof 4: Proof by Triangle

Consider the following image.

A triangle of base (n+1) and height (n+1) can be obtained from an arithmetic sequence of of (1 + 2 + ... + n) by adding n + 1 triangles of 0.5 unit area. Using this idea,

Sum = o.5 * (n + 1) * (n + 1) - 0.5 * (n + 1)
==> Sum = 0.5 * (n) * (n + 1)

---

I hope that you have found this exercise to be entertaining.

Coin Problems

You have pennies (1c), nickels (5c), dimes(10c), quarters (25c), and half-dollars (50). Solve the following problems:

a) Choose a combination of exactly 100 coins such that the total sum is exactly $5. There must be at least one of each coin.

b) Choose a combination of exactly 100 coins such that the total sum is exactly $5. There must be at least two of each coin.

c) Choose a combination of exactly 100 coins such that the total sum is exactly $5. There must be at least three of each coin.

d) Choose a combination of exactly 100 coins such that the total sum is exactly $10. There must be at least one of each coin.

Note: For some of the problems, there are multiple possible solutions. It is possible to arrive at a solution by trial and error. However, the ideal way of solving this exercise is to discover a method to solve all the above problems in a less tedious manner than trial and error. =)

Prisoners and Boxes

In a certain despotic nation, there are many prisoners being jailed. To alleviate the problem, the Emperor has decreed for all the prisoners to be "removed". What is decreed must be done; however the person doing the actual work is the High Jailer.

The Jailer thinks that the cost of bullets to execute everyone is too high, so he offers the prisoners the chance to earn their freedom. He proposes a game. There are X boxes in a room, with each box having the name of one unique prisoner. Since there are X prisoners, each prisoner's name is found in one and only one box.

The game is as follows: Each prisoner will be allowed to enter the room one at a time. The prisoner can then open all but one of the boxes; however, if the unopened box contains his name, everyone will be executed. If he does find his name in the opened boxes, he must restore the room to its original condition and leave the room. The prisoner will not be allowed to communicate to any prisoners that have yet to enter the room. If after all the prisoners have visited the room and found their names, they will all be released.

Needless to say, the boxes are arranged randomly. Still, each prisoner has a fairly good chance of finding his name; there is only a 1 / X chance of failing outright.

One of the prisoners, who is an amateur mathematician, remarks that the chance of everyone surviving is ( (X - 1) / X ) ^ X . He notes that by applying limits and using l'Hôpital's rule, the chance of surviving will increase with X, reaching e^-1 (0.368) when there are infinity prisoners. Not too bad a chance, he thinks.

At this point of time, another prisoner, an expert mathematician, speaks up and claims to have a better strategy! He shouts, "Why, with my plan, it is almost certain that we'll all survive!"

What is the mathematician's plan, and what is the chance of survival?

---

Note: This problem was derived from The condemned prisoners and the boxes, but the solution for our problem is more easily obtained.

Estimating NUS EE Statistics

The NUS commencement booklet has much data, including the names and honors classification of each graduate in the cohort. Privacy issues aside, this vast amount of data can be put to some use.

Doing a very rough count of the number of graduating EE students in each honors class, I found the following numbers: 15% First, 30% Second Upper, 30% Second Lower, 10% Third, 15% Pass. Coupled with the additional knowledge of the CAP requirement to obtain these honors classifications, I was able to obtain an estimate of the statistics of the NUS EE cohort.

First, I assumed a normal fit for the CAP distribution. Combining this with the known honors distribution, I was able to obtain a series of equations, like 0.15 = P(X > 4.5) , which represents the First Class degrees. These equations are made normal by assuming two parameters, µ and σ.

Of course, the linear system yields no solution. Hence, it is necessary to find the best fit for the linear system, such as via linear least squares. I used an applet for this task, arriving at the values of µ=3.884 and σ=0.626. In other words, the mean CAP for an ECE graduate is 3.884 while the std. dev is 0.626.

Now, all this seems pretty useless, with one exception. Using the normal statistics, I was able to compute the percentile that I was at, given the knowledge of my CAP at graduation. This should be a computation that anyone with a basic knowledge of statistics can perform.

Children and Daughters

Here are two interesting problems for you.

Problem 1:

I have 100 children. The oldest 99 are girls. What is the chance that I have 100 daughters?

Show Answer

The answer is 1/2. Quite obvious, really.

Simple, no? Now for the next problem.

Problem 2:

I have 100 children. At least 99 of them are girls. What is the chance that I have 100 daughters?

Show Hint 1

No, the answer is not 1/2. Try again.

Show Hint 2

Use conditional probability to solve the problem.

Show Answer

The answer is 1/101. Compute this by finding P(A|B), where event A is having 100 daughters, and event B is having at least 99 daughters.

A fun problem, though I didn't really get it right instantly too.

A Physics Thought Experiment

Consider the scenario illustrated by the following diagram:

There is a hot object initially at temperature T. The hot object is instantly teleported into a larger container, which contains a perfect vacuum and has a perfectly reflective inner surface. The closed container is perfectly reflective at all frequencies.

Assume that the container is magically suspended in the larger container. As the container contains a perfect vacuum, no heat is lost by conduction or convection. Heat can hence only be lost by radiation.

Does the final temperature of the hot object depend on the size of the larger container?

Test your Induction

The following sequence of three characters obeys a certain secret rule.

2, 4, 6

Your task is to infer the secret rule. To help you to discover the secret rule, you can produce any number of three character sequences for testing. I will then reply whether the produced sequence(s) obey the secret rule. (Pls try to propose sequences only in the tagboard; I will update the tested sequences in this post.)

As you can propose any number of character sequences for testing, you should only attempt to report the secret rule when you are absolutely sure that you have the correct rule in mind. To keep the game suspenseful, post rules only in the comments.

Interesting Maths Problem

I just encountered an interesting maths problem which I would like to share.

There are three classes in a school, each with the same number of students. The fraction of girls in class A is the same as the fraction of boys in class C. Also, class B has one-fifth of all the boys in the school.

What is the fraction of girls in the school ?

For your info, this question is a Sec One question. Frankly, I'm quite surprised at this fact. In anycase, I didn't use algebra to solve this problem - that felt unfair. Anyway intuition should prove helpful in tackling this question.

The Problem of the Bones

I've just stumbled upon an extremely interesting problem, to which I've only been able to derive a partial solution after some intuitive thinking. The problem itself is called "The Problem of the Bones". Here's the problem statement :

Imagine that a creature from outer space walks you before a pit. In the pit are 10,000 leg bones. The creature tells you, "I have cracked each bone at random into two pieces by throwing them against a rock. What's the average ratio of the length of the long piece to the length of the short piece?

This problem is pretty difficult to solve. I've only been able to obtain a solution for the case where there are infinity leg bones in the pit.

I'm now attempting a simulation to obtain the answer. If you are able to solve this problem, please leave the solution in the comments.