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.
Saturday, August 30, 2008
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.
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.
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.
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
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.
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.
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.
赛马问题
Q: 25匹马，请找出最快的3匹。
一次只能赛5匹，只能知道这5匹马的排序，没有秒表。
力求用最少的操作。
A: divide 25 horses to 5 groups, i.e., a, b, c, d, e
5 runs determines the order in each group, i.e.
a1>a2>a3>a4>a5
b1>b2>b3>b4>b5
c1>c2>c3>c4>c5
d1>d2>d3>d4>d5
e1>e2>e3>e4>e5
assume 6th run's result is a1>b1>c1>d1>e1,
a1 will be the fastest horse
7th run with b1, c1, b2, a2, a3 will determine the second and third fastest horses.
一次只能赛5匹，只能知道这5匹马的排序，没有秒表。
力求用最少的操作。
A: divide 25 horses to 5 groups, i.e., a, b, c, d, e
5 runs determines the order in each group, i.e.
a1>a2>a3>a4>a5
b1>b2>b3>b4>b5
c1>c2>c3>c4>c5
d1>d2>d3>d4>d5
e1>e2>e3>e4>e5
assume 6th run's result is a1>b1>c1>d1>e1,
a1 will be the fastest horse
7th run with b1, c1, b2, a2, a3 will determine the second and third fastest horses.
Wednesday, August 27, 2008
上山下山题
Q: 有一个人某日从山下上山,此山只有一条路,他9:00am
出发,下午3:00pm到山顶.当然速度是不均匀的,还可能在某
些地方停住休息.
第二天,他9:00am从山顶下山,还是这条路,于下午3:00pm到底.
当然还是走走停停.
问有没有可能这个人在同一时间(当然是两天中的同一时间),
(比如都是中午12:20pm)经过同一个地方(比如一个亭子)?
A: Yes. consider two person start at 9am and arrive at 3pm with opposite direction, the two person will meet somewhere in between.
出发,下午3:00pm到山顶.当然速度是不均匀的,还可能在某
些地方停住休息.
第二天,他9:00am从山顶下山,还是这条路,于下午3:00pm到底.
当然还是走走停停.
问有没有可能这个人在同一时间(当然是两天中的同一时间),
(比如都是中午12:20pm)经过同一个地方(比如一个亭子)?
A: Yes. consider two person start at 9am and arrive at 3pm with opposite direction, the two person will meet somewhere in between.
Mark a cylinder
Q: a 10L cylinder, marked at 2L, could you mark all other integer marks with only water?
A: with only water, we measure X/2, while X is known, and (X+y)/2, while X and Y is known, by tilting the cylinder
we can get:
5L = 10L/2;
1L = 2L/2;
3L = (1L+5L)/2;
4L = (3L+8L)/2;
6L = (2L + 10L)/2;
7L = (4L + 10L)/2;
8L = (6L + 10L)/2;
9L = (8L + 10L)/2;
A: with only water, we measure X/2, while X is known, and (X+y)/2, while X and Y is known, by tilting the cylinder
we can get:
5L = 10L/2;
1L = 2L/2;
3L = (1L+5L)/2;
4L = (3L+8L)/2;
6L = (2L + 10L)/2;
7L = (4L + 10L)/2;
8L = (6L + 10L)/2;
9L = (8L + 10L)/2;
Pirate's gold distribution problem
Q:
n Pirates with unique rank from 1 to n.
m pieces of gold.
Highest pirate gives proposal and all of them vote. Half or more support, ok.
else kill him. do again.
All pirates are willing to kill others. but if there's benifit, they choose
money. and they all know others are the same.
what's the best strategy for the highest pirate to get as more gold as possible?
write a program to exam your result.
If there's no enough gold, some one will be killed. Under what condition,
the highest pirate can suvive? give the mathematical answer. If m=0,
what's your program's output? is it match the mathematical answer? if not,
what's the problem?
A: Let's label the pirates as P_1,P_2,...,P_n, where p_n has highest rank
1. If P_1 need to make proposal, well, he just keep all the gold;
2. for p_2 , he could propose to have all gold, and got vote from himself;
3. for p_3, he could propose to get m-1 gold, while giving the 1 gold to p_1, so he can win two votes
4. for p_4, he could use 1 gold for p_2, and m-1 for himself
5. for p_5, he need 2 votes, 1 gold each to p_3 and p_1, and m-2 for himself
...
6. for p_(2*m+1), he could use all m gold to p_(2*m-1), p_(2*(m-1)-1), ... , p_1, and thus gather m + 1 votes (including himself), and survive
7. for p_(2*m+2), he could use all m gold to p_(2*m), p_(2*(m-1)), ... , p_2, and survive, but he could also get vote from p_(2*m+1) with 1 gold, because otherwise p_(2*m+1) won't get anything if it is up to himself to distribute the gold. Therefore, p_(2*m+2) can randomly distribute m gold to m of the m+1 pirates: p(2*m+1), p_(2*m), p_(2*(m-1)), ... , p_2, and survive.
8. for p_(2*m+3), there is no enough gold to get m+2 votes, so he will be killed anyway
9. for p_(2*m+4), he can get one vote from himself, m vote from randomly picked m from p_(2*m+2), p_(2*m+1), p_(2*m-1), ... , p_1 (who can not get any gold if do not support the propose), and p(2*m+1), p_(2*m), p_(2*(m-1)), ... , p_2, (who won't be sure to get a gold if p_(2*m+2) is going to distribute the gold), and one vote from p_(2*m+3) (otherwise he will be killed), therefore he can get totally m+2 votes and survive.
9. for p_(2*m+5), he needs m+3 votes to survive, but can only get m+1 votes. so he will be killed anyway
10. for p_(2*m+6), he needs m+3 votes, but can only get m+2 votes
11. for p_(2*m+7), he needs m+4 votes, but can only get m+3 votes
12. for p_(2*m+8), he needs m+4 votes, and can get it from himself, p_(2*m+7), p_(2*m+6), p_2*m+5), plus m votes from randomly picked p_(2*m+4), p_(2*m+3), p_(2*m+2),, ... , p_1 (who won't either get anything or be sure to get one gold, if p_(2*m+4) is going to distribute the gold). Therefore he can get totally m+4 votes and survive.
...
13. for p_(2*m + 2^k), k>0, he can survive as he can get vote by m golds, and votes from p_(2*m + 2^(k-1)+1), ..., p_(2*m + 2^k), totally m + 2^(k-1) votes and survive...the m golds will be distributed randomly picked m from p_1 to p_(2*m+2^(k-1))
if m = 0, p_1, p_2, p_4, p_8, ... , p_(2^k) can survive, this is same as concluded above.
n Pirates with unique rank from 1 to n.
m pieces of gold.
Highest pirate gives proposal and all of them vote. Half or more support, ok.
else kill him. do again.
All pirates are willing to kill others. but if there's benifit, they choose
money. and they all know others are the same.
what's the best strategy for the highest pirate to get as more gold as possible?
write a program to exam your result.
If there's no enough gold, some one will be killed. Under what condition,
the highest pirate can suvive? give the mathematical answer. If m=0,
what's your program's output? is it match the mathematical answer? if not,
what's the problem?
A: Let's label the pirates as P_1,P_2,...,P_n, where p_n has highest rank
1. If P_1 need to make proposal, well, he just keep all the gold;
2. for p_2 , he could propose to have all gold, and got vote from himself;
3. for p_3, he could propose to get m-1 gold, while giving the 1 gold to p_1, so he can win two votes
4. for p_4, he could use 1 gold for p_2, and m-1 for himself
5. for p_5, he need 2 votes, 1 gold each to p_3 and p_1, and m-2 for himself
...
6. for p_(2*m+1), he could use all m gold to p_(2*m-1), p_(2*(m-1)-1), ... , p_1, and thus gather m + 1 votes (including himself), and survive
7. for p_(2*m+2), he could use all m gold to p_(2*m), p_(2*(m-1)), ... , p_2, and survive, but he could also get vote from p_(2*m+1) with 1 gold, because otherwise p_(2*m+1) won't get anything if it is up to himself to distribute the gold. Therefore, p_(2*m+2) can randomly distribute m gold to m of the m+1 pirates: p(2*m+1), p_(2*m), p_(2*(m-1)), ... , p_2, and survive.
8. for p_(2*m+3), there is no enough gold to get m+2 votes, so he will be killed anyway
9. for p_(2*m+4), he can get one vote from himself, m vote from randomly picked m from p_(2*m+2), p_(2*m+1), p_(2*m-1), ... , p_1 (who can not get any gold if do not support the propose), and p(2*m+1), p_(2*m), p_(2*(m-1)), ... , p_2, (who won't be sure to get a gold if p_(2*m+2) is going to distribute the gold), and one vote from p_(2*m+3) (otherwise he will be killed), therefore he can get totally m+2 votes and survive.
9. for p_(2*m+5), he needs m+3 votes to survive, but can only get m+1 votes. so he will be killed anyway
10. for p_(2*m+6), he needs m+3 votes, but can only get m+2 votes
11. for p_(2*m+7), he needs m+4 votes, but can only get m+3 votes
12. for p_(2*m+8), he needs m+4 votes, and can get it from himself, p_(2*m+7), p_(2*m+6), p_2*m+5), plus m votes from randomly picked p_(2*m+4), p_(2*m+3), p_(2*m+2),, ... , p_1 (who won't either get anything or be sure to get one gold, if p_(2*m+4) is going to distribute the gold). Therefore he can get totally m+4 votes and survive.
...
13. for p_(2*m + 2^k), k>0, he can survive as he can get vote by m golds, and votes from p_(2*m + 2^(k-1)+1), ..., p_(2*m + 2^k), totally m + 2^(k-1) votes and survive...the m golds will be distributed randomly picked m from p_1 to p_(2*m+2^(k-1))
if m = 0, p_1, p_2, p_4, p_8, ... , p_(2^k) can survive, this is same as concluded above.
Tuesday, August 26, 2008
Questions
1.信封与信题
十封不同信塞在十个特定信封里, 问有一封信塞错的概率是多少?
A: 0, as either there is no error or at least two errors
2.地球走路题
站在地球上任意一点, 向南走1m, 向东走1m,向北再走1m能回到原点的位置有几个?
A: infinite, as at some point near south pole, the girth can be 1m.
3.水桶灌水题
问现有3L跟5L的两个无刻度桶, 如何量出4L的刻度? (扩展: 貌似有几种方法, 哪种最
省水?)
A: fill 5L, pour to 3L, gather the first 2L, put the 3L water back to 5L, fill up 5L, and pour to 3L, gather another 2L. In this way, only 7L water is used.
4.秤球题
问现有21个球和一个天平, 如何用最少次数找出21球中的一个比其他轻的球? (此题我
见过的就有9球, 12球等等, 我自己被考的是21球.)
A: will have post on this kind of problem separately.
5.九点连线题
如图有以下九点方阵, 问如何用四条直线将其联起, 而且要四条直线头尾相接(一气呵
成~~)
* * *
* * *
* * *
Hint: consider the following:
* * * *
* * *
* * *
*
6.分COOKIE题
有一堆OREO饼干, 和一单列人, 每一个人走到这个饼干堆面前拿走此堆饼干总数的1/2
和一个1/2块饼干, 问开始饼干数量为多少的时候, 第四个人正好拿完.(还有, 开始为
多少时, 第十个人正好拿完等等)
A: Consider from the last person:
Let Ci be the cookie numbers before ith person take his portion,
C4 = 1
C3 = 3
C2 = 7
C1 = 15
十封不同信塞在十个特定信封里, 问有一封信塞错的概率是多少?
A: 0, as either there is no error or at least two errors
2.地球走路题
站在地球上任意一点, 向南走1m, 向东走1m,向北再走1m能回到原点的位置有几个?
A: infinite, as at some point near south pole, the girth can be 1m.
3.水桶灌水题
问现有3L跟5L的两个无刻度桶, 如何量出4L的刻度? (扩展: 貌似有几种方法, 哪种最
省水?)
A: fill 5L, pour to 3L, gather the first 2L, put the 3L water back to 5L, fill up 5L, and pour to 3L, gather another 2L. In this way, only 7L water is used.
4.秤球题
问现有21个球和一个天平, 如何用最少次数找出21球中的一个比其他轻的球? (此题我
见过的就有9球, 12球等等, 我自己被考的是21球.)
A: will have post on this kind of problem separately.
5.九点连线题
如图有以下九点方阵, 问如何用四条直线将其联起, 而且要四条直线头尾相接(一气呵
成~~)
* * *
* * *
* * *
Hint: consider the following:
* * * *
* * *
* * *
*
6.分COOKIE题
有一堆OREO饼干, 和一单列人, 每一个人走到这个饼干堆面前拿走此堆饼干总数的1/2
和一个1/2块饼干, 问开始饼干数量为多少的时候, 第四个人正好拿完.(还有, 开始为
多少时, 第十个人正好拿完等等)
A: Consider from the last person:
Let Ci be the cookie numbers before ith person take his portion,
C4 = 1
C3 = 3
C2 = 7
C1 = 15
Linking two arrays
Q: given
A1,A2,....Am
B1,B2,....Bn
All of them are positive integers.
find a way to link B to A so that the sum of absolute difference of each B and its assigned A is minimized. prove your method is right.
Two case (1) m=n (2) m>n
A: (1) m = n
a. sort A and B in increasing order, so that A1'<=A2'<=...<=Am', and B1'<=B2'<=...<=Bn';
b. link B1' to A1', B2' to A2', ..., and Bn' to Am';
(2) m>n
?
A1,A2,....Am
B1,B2,....Bn
All of them are positive integers.
find a way to link B to A so that the sum of absolute difference of each B and its assigned A is minimized. prove your method is right.
Two case (1) m=n (2) m>n
A: (1) m = n
a. sort A and B in increasing order, so that A1'<=A2'<=...<=Am', and B1'<=B2'<=...<=Bn';
b. link B1' to A1', B2' to A2', ..., and Bn' to Am';
(2) m>n
?
Card dealing question
Q: In how many ways can a pack of 52 cards be dealt to 13 players, 4 to each, so that one player has a card from each suit but no one else has cards from more than one suit?
A: Three steps:
1. pick one player, pick one card from each suit
==>13^5
2. put 12 remaining players into 4 different suits to make three players per suit
==> 12!/(9!*3!) * 9!/(6!*3!) * 6!/(3!*3!) = 12!/(3!)^4
3. put 12 remaining cards in each suit to 3 players, separately
==> (12!/*8!*4!) * 8!/(4!*4!))^4 = (12!)^4 / (4!)^12
so final answer is: (13!)^5 / (4!)^12 / (3!)^4
A: Three steps:
1. pick one player, pick one card from each suit
==>13^5
2. put 12 remaining players into 4 different suits to make three players per suit
==> 12!/(9!*3!) * 9!/(6!*3!) * 6!/(3!*3!) = 12!/(3!)^4
3. put 12 remaining cards in each suit to 3 players, separately
==> (12!/*8!*4!) * 8!/(4!*4!))^4 = (12!)^4 / (4!)^12
so final answer is: (13!)^5 / (4!)^12 / (3!)^4
Subscribe to:
Posts (Atom)