Saturday, August 30, 2008

Warden and 23 prisoner problem

Q:
The warden meets with 23 new prisoners when they arrive. He tells them, "You may meet today and plan a strategy. But after today, you will be in isolated cells and will have no communication with one another.

"In the prison is a switch room, which contains two light switches labeled A and B, each of which can be in either the 'on' or the 'off' position. I am not telling you their present positions. The switches are not connected to anything.

"After today, from time to time whenever I feel so inclined, I will select one prisoner at random and escort him to the switch room. This prisoner will select one of the two switches and reverse its position. He must move one, but only one of the switches. He can't move both but he can't move none either. Then he'll be led back to his cell.

"No one else will enter the switch room until I lead the next prisoner there, and he'll be instructed to do the same thing. I'm going to choose prisoners at random. I may choose the same guy three times in a row, or I may jump around and come back.

"But, given enough time, everyone will eventually visit the switch room as many times as everyone else. At any time anyone of you may declare to me, 'We have all visited the switch room.' and be 100% sure.

"If it is true, then you will all be set free. If it is false, and somebody has not yet visited the switch room, you will be fed to the alligators."

What is the strategy they come up with so that they can be free?

A: Here is one that will work, though it might take long time:
Pick a person as switch A monitor. For this person, whenever he sees switch A off, put it back to on, and count it once; if the switch A is on, move the switch B.
For all other prisoners, for their first two times seeing switch A on, move the switch A to off, otherwise, move only the switch B.

Since there are 22 other prisoners, total switching from on to off of switch A will be 44 times, so the monitor will be able to count at least 44. The first count might not indicate a true visit of other prisoner since the initial status of switch A is unknown (If the initial status of switch A is off, the monitor will count it once when he visit the room)

The monitor will finally count either 44 or 45 times, and he can declare that every prisoner has visited the switch room at the 44th time, because if only 21 visited, he can count at most 43.

Note: the rule for other prisoners can not be switching A from on to off only once, as the monitor might finally count either 22 or 23. At time 22, he can not be sure about whether all other 22 has been to the room. And he might never be able to count to 23.

Quiz

1) In how many different orders can five runners finish a race?
A: 5! = 120

2) How many possibilities are there for the win, place, and show (first,
second and third) positions in a race with 12 horses?
A: 12*11*10 = 1320

3) A pair of dice is loaded. The probability that a 4 appears on the first die
is 2/7 and the probability that a 3 appears on the second die is 2/7. Other
outcomes for each die appear with probability 1/7. What is the probability of
7 appearing as the sum of the two dice?
A: p(d1+d2=7) = p(d1=1)*p(d2=6) + ...+ p(d1=6)*p(d2=1) = 5*1/7*1/7 + 2/7*2/7 = 9/49

4) Write the equation for the straight line passing through the points (5,7)
and (7,15).
A: y = ax + b ==> 7 = 5a + b and 15 = 7a + b ==> a=4 and b=-13
so the line equation is y = 4x -13.

5) One of the products our company offers is a suite of prepayment models for
various mortgage backed securities. A mortgage backed security is a bond
composed of many mortgages. Every month investors in these bonds receive the
monthly payments of the underlying mortgages. Investors like to be able to
predict the monthly payments they will receive in the future. This would be
fairly straight-forward, as home-owners generally pay the same amount every
month on their mortgages, except home-owners have an option to prepay their
mortgage at any time. A prepayment occurs when a homeowner pays the remaining
principle (each monthly payment is composed of two parts: principle and
interest) of their mortgage early. This payment, like all others, gets passed
through to the mortgage backed security抯 investors. This results in the
investors receiving a larger payment for this month, but no more payments from
this home-owner in the future. The job of a prepayment model is to take
information about a loan or a pool of loans as well as various economic
conditions and use this information to predict how fast the loan or loans will
prepay for various points in the future.

Describe the information you might need to know about the loan, home-owners,
and current and future economic conditions in order to give a general
prediction of how likely a given homeowner is to prepay their mortgage. Tell
why you would need each piece of information.

A: The prepayment will mainly come from following two reasons: 1. refinancing. 2. selling of the property, including mortgage default.
for 1. we mainly need to know the mortgage rate of the loan and tracking the mortgage rate as time goes
for 2. we might need to know more about the loan amount, remaining principle, the market value of the property, the house market trend, the family member's information for possibility of downsizing or upgrading the property, household income information, credit record, spending behavior and etc.

Thursday, August 28, 2008

contaminated pill problem

Q: You have 4 jars of pills. Each pill is a certain weight, except for contaminated pills contained in one jar, where each pill is weight + 1. How could you tell which jar had the contaminated pills in just one measurement?

A: weight p1 + 2* p2 + 3*p3 + 4*p4
if the total weight is 10weight + i, the ith jar is contaminated.

gold bar problem

Q: You've got someone working for you for seven days and a gold bar to pay them. The gold bar is segmented into seven connected pieces. You must give them a piece of gold at the end of every day. If you are only allowed to make two breaks in the gold bar, how do you pay your worker?

A: you need 1 for the first day
you need 2 for the second day.
so you have 1, 2, 4
and can pay 1, 2, 1+2, 4, 4+1, 4+2, and 4+1+2 for the seven days.

three envelop problem

Q: 三张信封(A,B,C),只有一封有$10000。你可以任选其中一封,譬如B,剩下两封必有一 封为空,譬如A,现在取走A,剩下两封。 问:你是stick to你的选择(B),还是选择剩下的另外那封(C)?

A: pick C.

p(B=$) = 1/3.
p(C=$) = 1 - p(B=$) - p(A=$) = 1 - 1/3 - 0 = 2/3

1 minute question

Q: Having an expression:

A B C D
+ B C D
--------------
E F G H I

where each letter A-I represents different digit number 0-9.

Then which number is absent in above expression?

A: It is easy to see that E = 1, A = 9, F = 0,
we can also see that 5 can not be in BCDI, as otherwise either 0 or 1 will be in GHI.

if 5 in H, then C is 7, and BCD= 678 or 876 ==> 2*BCD = 1356 or 1752, which is not possible.
if 5 in G, then B is 7, and BCD =768 or 786==> 2*BCD = 1536 or 1572, which is not possible either.

so 5 is absent.

Problem with a 100 floor building and two eggs

Q: you have two eggs. you need to figure out how high an egg can fall from a 100 story building before it breaks. the eggs might break from the first floor, or might even survive a drop from the 100th floor. What is the minimum number of drops in the worst case?
You may have following assumptions:
* An egg that survives a fall can be used again.
* A broken egg must be discarded.
* The effect of a fall is the same for all eggs.
* If an egg breaks when dropped, then it would break if dropped from a
higher window.
* If an egg survives a fall then it would survive a shorter fall.

A: let the minimum number be N
#N: 100th floor, if the first egg succeed on 99th floor, we need the last one to test the 100th floor
#N-1: 99th, as we mentioned
#N-2: 97th, here we skip 98th, as when the drop #N-1 failed on 99th, we have the second egg and the #N drop on 98th floor
#N-3: 94th, here we skip 96th, and 95th floors, as if #N-2 drop fails, we can use the second egg starting from 95th floor, and goes up to 96th floor, at most 2 drops would determine the result
#N-4: 90th,
#N-5: 85th,
... ...

therefore, #N-i => 100-1-2-...-i = 100 - i*(i+1)/2 ==> #N-13 =>9th floor, which would be the first drop ==> N = 14.