The puzzle thread

nownow's picture
Rank: Baboon | 116

NOTE: If you have seen a problem before, please don't solve it.

This is a thread for posting logic/probability ques, to help people prep for trading interviews. If you have an interesting question that you have heard or thought of, post it to give people practice. I'll post at least one per week.

Difficulty (1-5, 5 being hardest). If it is labeled 6...you should probably move on.

Question #1 (2)
You have a bag with 5 red balls, 3 blue balls. You pull balls out of the hat one at a time. If you get a blue ball, you put it back. If you get a red ball, you remove it. How many draws will you make in expectation until all RED balls have been removed.

SOLUTION: qtrade

Question #2 (4)
You have a digital clock which either displays a time A:BC:DE or AB:CD:EF, depending on the hour. Sometimes, the time displayed will be a palindrome. What is the shortest distance between two consecutive palindrome times? The longest distance between consecutive?

SOLUTION: First half, by zbb. Second half by marketimpact (prior exposure).

Question #3 (1)
Using all of the numbers 12 4 2 and 1, and addition/multiplication/subtraction/division, create a logical expression that equals 24.

SOLVED by Eddie. Note there are multiple solutions.

Question #4 (2)
Using all of the numbers 8 8 3 and 3, and addition/multiplication/subtraction/division, create a logical expression that equals 24.

SOLUTION: edtkh

Question #5 (2)
A couple have children until they have a son. Assume no twins are born. In expectation, how many children do they have?

SOLUTION: edtkh

Question #6 (3)
How many trailing zeros does 1000! have.

SOLUTION: LTV

Question #7 (3)
A spider starts at one corner of a cube. Each second, he randomly chooses one of the edges he is adjacent to and walks along it. What's the expected number of seconds before the spider reaches the furthest corner from his starting point.

SOLUTION: qtrade

Question #8 (5):
A spider starts at one corner of a cube. Each second, he randomly chooses one of the edges he is adjacent to and walks along it. What's the expected number of seconds before the spider reaches a corner that is the furthest corner from ANY corner that the spider has been to so far.

SOLUTION: vectorkid

Question #9 (5):
You start with a well shuffled deck (26 black cards, 26 red) and X dollars. Cards are turned face up one by one. Before every card is turned face up, you may bet any fraction of your money on the color of the card about to be turned over - you double your bet if you win, lose it otherwise. What is the maximum return you can guarantee.

SOLUTION: marketimpact (Note: previous exposure)

Question #10 (2)
Solve for x when x^x^x^x^.... = 3, where ^ is means to the power of, and the expression is nested and infinite.

SOLUTION: qtrade

Questions 11-16 (Difficulty 5)
These questions involve games:

Game A: You roll an n sided die, If the result is 1, you may re-roll or take the result. On the re-roll, you may re-roll a 2 or less, then a 3 or less, ect. On the nth re-roll, you may re-roll n or less (any result). Each re-roll is optional.

Game B: You roll an n sided die, and may re-roll an n or less (any result) or take the result. Subsequently, you may re-roll an n-1 or less, then n-2, ect. On the nth re-roll you may re-roll a 1 only. Each re-roll is optional.

11. For what n is the ratio of the expected value of game A to the mean result of one die roll ((n+1)/2) greatest.

12. For what n is the ratio of the expected value of game A to the maximum result of the die (n) the greatest.

13. For what n is the ratio of the expected value of game B to the mean result of one die roll ((n+1)/2) greatest.

14. For what n is the ratio of the expected value of game B to the maximum result of the die (n) the greatest.

15. For what n is E(A)*E(B)/n greatest.

16 For what n is E(A)*E(B)/(n+1) greatest.

&& means and
| means such that
x^x^x^... = x^(x^(x^(...

Question #17 (3):
Find the set {x1,...,xn | x1+x2+...xn = 16 && n>=1 && xi >=0}, for which x1x2...*xn is maximized.

SOLUTION: monkeysama

Question #18 (4):
Generalize the previous result for x1+...xn = k. At the very least give an asymptotic solution.

SOLUTION: jhconnel

Question #19 (5):
Find the set {x1,...,xn | x1+x2+...xn = 16 && n>=1 && xi >=0}, for which x1^x2^...^xn is maximized.

Question #20 (6):
Generalize the previous result for x1+...xn = k. At the very least give an asymptotic solution.

Question #21 (4):
A generalization of #7. Let the spider be in a corner of a regular polyhedron with n sides. What is the expected number of seconds until the spider reaches the furthest corner.

Question #22 (6):
A generalization of #8. Let the spider be in a corner of a regular polyhedron with n sides. What is the expected number of seconds until the spider reaches a corner which is the furthest from a corner than the spider has already been to.

Question #23 (3):
Find the smallest positive x such that x mod k = k-1, for all 2<=k<=10. Mod means, remainder after dividing. For example, 9 mod 2 = 1.

SOLUTION: jhconnel

Question #24 (2):
What is the angle formed by the hands of the clock when it is 1:45?

SOLUTION: Thisdude

Question #25 (4):
Find the set {x1,...,xn | x1^x2^...^xn = 16 && n>=1 && xi >=0}, for which x1x2...*xn is maximized.

Question #26 (5):
Find the set {x1,...,xn | x1^x2^...^xn = k && n>=1 && xi >=0}, for which x1x2...*xn is maximized.

Question #27 (3):
Order every person in the world from youngest to oldest, accurate right down to the microsecond. Assume there are N people in the world, where N ~ 6.3-6.4 billion. Randomly assign every person in the world one of the integers between 1 and N (only assign each number once!), and call this number xi for the ith youngest person. What is the probability that for at least one 1 <= i <= N, xi = i.

SOLUTION: vectorkid

Question #28 (2):
Show that the sum of all numbers with 9 digits or less is divisible by 9.

SOLUTION: zbb

Question #29 (4):
You start with a well shuffled deck (26 black cards, 26 red) and X dollars. Cards are turned face up one by one. Every time a black card is turned up, you earn $1. Every time a red card is turned, you lose $1. What is your strategy for playing the game? How much would you pay to play this game?

Question #30 (4):
You have a dartboard that is 16 inches in diameter. The dartboard consists of 4 bands which are each 2 inches in width. In addition, each of these bands is divided into 20 equally sized segments. Everyone who is playing is very drunk, so they have an equal probability of hitting any place on the dartboard. How many darts must be thrown until the probability that each segment has been hit is at least 1/2.

Question #31 (2):
Roll two 6-sided die. What is the expected value of the product?

SOLUTION: jhconnel

Question #32 (2):
Roll two 6-sided die. What is the most likely product?

SOLUTION: jhconnel

Question #33 (2):
Roll two 6-sided die. Pick a number. If the product of the die roles is equal to your number, you win that much in cold hard cash. What number should you pick.

SOLUTION: jhconnel

Question #34 (2):
Roll j copies of an n-sided die. What is the expected value of the product?

SOLUTION: jhconnel

Question #35 (4):
Roll j copies of an n-sided die. What is the most likely product?

Question #36 (5):
Roll j copies of an n-sided die. Pick a number. If the product of the die roles is equal to your number, you win that much in cold hard cash. What number should you pick.

Question #37 (3):
Find {x1,...,x7 | for at least one i, xi > 0 && xi are integers && x1...x7 = x1+....+x7}.

Question #38 (3):
Find {x1,...,x7 | for at least one i, xi > 0 && xi are integers && xi^...^xj = x1+....+x7}, where i,...,j is an ordering of 1,...,7.

Question #39 (3):
Find {x1,...,x7 | for at least one i, xi > 0 && xi are integers && xi^...^xj = x1....x7}, where i,...,j is an ordering of 1,...,7.

Question #40 (5)
A spider starts at one corner of a cube. Each second, he randomly chooses one of the edges he is adjacent to and walks along it. What's the expected number of seconds before the spider has visited every corner of the cube.

Question #41 (6):
A generalization of #40. Let the spider be in a corner of a regular polyhedron with n sides. What is the expected number of seconds until the spider has visited every corner.

Question #42 (4):
What is the expected number of times an n-sided die must be rolled before two numbers repeat?

Question #43 (4):
A n-sided die is rolled until a number is repeated. What is the most likely number of die rolls?

Question #44 (4):
A n-sided die is rolled until all n numbers have appeared. What is the expected number of die rolls?

Question #45 (4):
A n-sided die is rolled until all n numbers have appeared. What is the most likely number of die rolls?

Question #46 (5):
A n-sided die is rolled until a number is repeated. Before the die is rolled, you may pick any number j. If the first repetition occurs in the jth roll, you win j dollars. What j should you pick.

Question #47 (5):
A n-sided die is rolled until a number is repeated. When a number is first repeated, you win j dollars where j is the number of rolls that have occurred. What is the expected value of your reward.

Question #48 (5):
A n-sided die is rolled until all n numbers have come up. Before the die is rolled, you may pick any number j. If the last number comes up on the jth roll, you win j dollars. What j should you pick.

Question #49 (5):
A n-sided die is rolled until all n numbers have come up. Once all numbers have come up, you win j dollars where j is the number of rolls of the die. What is the expected value of your reward.

Question #50 (4):
You have an n-sided die (n>=1). You must roll the die n times, and take the lowest value. What choice of n maximizes the result.

Comments (108)

Nov 9, 2010

LOL. I'll take the easy one:

3 (412)/(21)=24

Nov 9, 2010
Edmundo Braverman:

LOL. I'll take the easy one:

3 (412)/(21)=24

This reminds me of that "24" game we played in middle school.. You could also do (12 - 4)*(2+1)

Nov 9, 2010

6 211

If I haven't been tricked:

if you count upwards, every ten numbers has
a no ending in 5
a no ending in 2

multiply these, and it'll and it'll create a number ending in 0

every ten also has a number ending in 0

except, 9 of those will end in two 0s
and one in three

therefore, each ten that you cunt will add two more 0s, but for the exceptions

there are 100 tens in 1000

plus nine and two more for the "exceptions"

Nov 9, 2010
zbb:

#6 211

If I haven't been tricked:

if you count upwards, every ten numbers has
a no ending in 5
a no ending in 2

multiply these, and it'll and it'll create a number ending in 0

every ten also has a number ending in 0

except, 9 of those will end in two 0s
and one in three

therefore, each ten that you cunt will add two more 0s, but for the exceptions

there are 100 tens in 1000

plus nine and two more for the "exceptions"

nope, sorry.

Nov 9, 2010
thisdude:
zbb:

#6 211

If I haven't been tricked:

if you count upwards, every ten numbers has
a no ending in 5
a no ending in 2

multiply these, and it'll and it'll create a number ending in 0

every ten also has a number ending in 0

except, 9 of those will end in two 0s
and one in three

therefore, each ten that you cunt will add two more 0s, but for the exceptions

there are 100 tens in 1000

plus nine and two more for the "exceptions"

nope, sorry.

Number of factors that are multiples of 10. Since for every multiple of (5)^n (where n is a Natural number) there should be a corresponding even number multiple to make the product a multiple 10, the number of factors that are multiples of (5)^n should give me the answer. 1000/5 + 1000/25 + 1000/125 + 1000/625= 200+40+8+1.

249 trailing 0s.

Learn More

Boost your resume and land a finance job by passing the FINRA SIE. 264 pages & 1981 smart flashcards written by a former 8X top Fidelity instructor. Try it for 0 bananas here.

Nov 9, 2010

I never said I was smart. I give up... for now at least

Nov 9, 2010

Question #2 (4)
You have a digital clock which either displays a time A:BC:DE or AB:CD:EF, depending on the hour. Sometimes, the time displayed will be a palindrome. What is the shortest distance between two palindrome times? The longest distance?

Assumptions if the format is A:BC:DE there is still a 0 where A would be in the character time.

Shortest:
12:00:21 from 11:55:11 etc. = 5:10
unless we can use
01:00:10 from 12:55:21 = 4:49

Longest:
12:55:21 to 10:00:01 = 9:04:40
unless we can use
05:55:50 to 10:00:01 = 4:04:11

Nov 9, 2010
Magua:

Question #2 (4)
You have a digital clock which either displays a time A:BC:DE or AB:CD:EF, depending on the hour. Sometimes, the time displayed will be a palindrome. What is the shortest distance between two palindrome times? The longest distance?

Assumptions if the format is A:BC:DE there is still a 0 where A would be in the character time.

Shortest:
12:00:21 from 11:55:11 etc. = 5:10
unless we can use
01:00:10 from 12:55:21 = 4:49

Longest:
12:55:21 to 10:00:01 = 9:04:40
unless we can use
05:55:50 to 10:00:01 = 4:04:11

Wrong, note these are consecutive times so that might change your answer for the longest. Your shortest is definitely wrong. Also, to clarify, 05:55:50 is NOT palidromic since it will display as 5:55:50. Also, 0:30:30 still displays the 0.

Nov 9, 2010

Isn't the shortest
9:59:59 to 10:00:01?

Nov 9, 2010
zbb:

Isn't the shortest
9:59:59 to 10:00:01?

Correct, now find the longest. :D

Nov 9, 2010

9 Let's hope I don't get this wrong

We're talking about guarantee

So, if by fluke chance the first 26 are of the same suit, the rest will be of the other
You can double your money 26x

Which would be 2^26-1 return

Nov 9, 2010

But at the point of entering the game
Off the top of my head
It would be 100%

Nov 9, 2010

2 If the answer's not 11 minutes, it would have to be longer

I'd love to do a little more, but I gotta get going

Nov 9, 2010

5: This is akin to the coin flip question where you estimate the expected returns of flipping a coin k times until you land a head. The expected return in this case is essentially the mean of the geometric progression which yields 1/0.5=2.

3: Another solution = 12/2/1*4=24

Nov 9, 2010
edtkh:

#5: This is akin to the coin flip question where you estimate the expected returns of flipping a coin k times until you land a head. The expected return in this case is essentially the mean of the geometric progression which yields 1/0.5=2.

3: Another solution = 12/2/1*4=24

Your #5 is correct. Congrats.

Nov 9, 2010

you go to a top tier ivy league school and have tons of connections. however, your personality sucks and none of the firms want you and give you dismal acceptance rates.

what is the probability of success?

for extra points, what is the formula to determine the above question when you are given a 'boost' or an in or offered help?

for further extra credit, what is the probability of success when you delete all your threads?

Nov 9, 2010

@ Zbb #9 is wrong and #2 is longer than 11 minutes.

Nov 9, 2010

4: 8/(3-(8/3)) = 24.

PS: I wouldn't put this at difficulty level 2.

Nov 9, 2010
edtkh:

#4: 8/(3-(8/3)) = 24.

PS: I wouldn't put this at difficulty level 2.

That's correct. They are all difficult questions (well except Eddies) by layman standards. But the spread is necessary since some of the 4s and 5s are REALLY hard. #1 is pretty difficult, for example, but it is still a 2 compared to the 3s,4s,5s in my estimation.

It is difficult for me to judge how hard the 1000! question is, because I had seen the 100! factorial question so 1000! was an easy extension. I found the 8 8 3 3 question pretty straightforward.

Nov 9, 2010

The trailing 0's for the 1000! question is certainly way beyond a 3 in my book. As a matter of fact, believe it or not, I have yet to get a correct answer from the candidates I have thrown that question to.

To be fair though, I personally don't think that's as important (nevermind if it's hard; the crux really is that most people fail to see the pattern or identify the root of the problem from which one should use to tackle the question) to the job itself as simple probability questions like #5.

Nov 9, 2010
edtkh:

The trailing 0's for the 1000! question is certainly way beyond a 3 in my book. As a matter of fact, believe it or not, I have yet to get a correct answer from the candidates I have thrown that question to.

To be fair though, I personally don't think that's as important (nevermind if it's hard; the crux really is that most people fail to see the pattern or identify the root of the problem from which one should use to tackle the question) to the job itself as simple probability questions like #5.

Well, nobody has solved a 4 or a 5 yet. We only have a partial solution for one of the 4s. So who is to say that the 4s or 5s aren't harder than the 1000! question?

Nov 9, 2010
thisdude:
edtkh:

The trailing 0's for the 1000! question is certainly way beyond a 3 in my book. As a matter of fact, believe it or not, I have yet to get a correct answer from the candidates I have thrown that question to.

To be fair though, I personally don't think that's as important (nevermind if it's hard; the crux really is that most people fail to see the pattern or identify the root of the problem from which one should use to tackle the question) to the job itself as simple probability questions like #5.

Well, nobody has solved a 4 or a 5 yet. We only have a partial solution for one of the 4s. So who is to say that the 4s or 5s aren't harder than the 1000! question?

It's only a fair assessment if you know how many candidates have attempted each question. I solved a 2 before solving the 1. ;)

Nov 9, 2010

What is the angle formed by the hands of the clock when it is 1:45?

Nov 9, 2010
Erebus:

What is the angle formed by the hands of the clock when it is 1:45?

The difference between 270 degrees and (360/12)*1.75 degrees is 142.5 degrees

Nov 9, 2010

Question 9:

My solution is: you can make 2X at the most. I believe the key word here is "guaranteed" which I take to be "riskless." And I am assuming that I am picking my strategy before the game begins.

I would wait until the last card in the deck, by which time I know the color with 100% certainty. Then I bet it all.

Nov 9, 2010
ivoteforthatguy:

Question 9:

My solution is: you can make 2X at the most. I believe the key word here is "guaranteed" which I take to be "riskless." And I am assuming that I am picking my strategy before the game begins.

I would wait until the last card in the deck, by which time I know the color with 100% certainty. Then I bet it all.

That's a nice strategy, and yes you double. But that's not the correct answer, there's a better guaranteed result.

Nov 9, 2010

Q9: this can't be done by hand and requires coding:

  • start of with one dollar
  • let D(b,r) be the best you can get with b black and r red cards
  • boundaries:
    D(0,r) = 2^r //bet all each time and double up
    D(b,0) = 2^b
  • situation is symmetrical:
    D(x, y) = D(y,x)
  • and always bet on the color with the most cards remained
  • so if r >= b
  • x is fraction of money to gamble
    D(r,b) = max_x min{ won bet, lost bet}
    = max_x min { (1+x) D(r-1,b) , (1-x) D(r, b-1) }
  • i.e.
    first not-obvious value T(2,1)
    get T(1,1) = 2
    and then T(2,1) = max min { (1+x)2, (1-x)4}

and the min is maximized when the lines intersect at x = 1/3 => T(2,1) = 8/3

"I came, I saw, I networked"

Nov 9, 2010

For q9: Maybe I am getting tangled in semantics, but I was looking for the guaranteed return. After the first card is dealt, you immediately have information about the odds in the next draw and you make a Kelly bet. But making any Kelly bet up until the last card is a risky strategy.

If I had to solve this on my feet, I would make a probabilistic argument. Assuming that I had to pick my strategy before the game begins, I could say: if I wait until two cards were left in the deck, there is a .5 chance that it's same-color and .5 that it's mixed. If it's mixed, I have a strategy to win 2X risk-free (i.e., wait a card). If it's same, I have a strategy to win 4X. So the EV is 3X. I can go on inductively and go above 3X, etc.

Nov 9, 2010
marketimpact:

Q9: this can't be done by hand and requires coding:

  • start of with one dollar
  • let D(b,r) be the best you can get with b black and r red cards
  • boundaries:
    D(0,r) = 2^r //bet all each time and double up
    D(b,0) = 2^b
  • situation is symmetrical:
    D(x, y) = D(y,x)
  • and always bet on the color with the most cards remained
  • so if r >= b
  • x is fraction of money to gamble
    D(r,b) = max_x min{ won bet, lost bet}
    = max_x min { (1+x) D(r-1,b) , (1-x) D(r, b-1) }
  • i.e.
    first not-obvious value T(2,1)
    get T(1,1) = 2
    and then T(2,1) = max min { (1+x)2, (1-x)4}

and the min is maximized when the lines intersect at x = 1/3 => T(2,1) = 8/3

You have the right approach. It's pretty easy to get the exact answer with excel, which the monkeys on this board should know how to use.

Nov 9, 2010
thisdude:

You have the right approach. It's pretty easy to get the exact answer with excel, which the monkeys on this board should know how to use.

I get 9.08133

"I came, I saw, I networked"

Nov 9, 2010

1. Expected turns: 11.85 = 8/5 + 7/4 + 6/3 + 5/2 + 4/1. Think of throwing dice.

7. You need 10 seconds. Use conditional expectations and the fact the cube only has 4 distinct corners.

10. exp(log(3)/3) - to see it take log() on both sides

Nov 9, 2010
qtrade:

#1. Expected turns: 11.85 = 8/5 + 7/4 + 6/3 + 5/2 + 4/1. Think of throwing dice.

7. You need 10 seconds. Use conditional expectations and the fact the cube only has 4 distinct corners.

10. exp(log(3)/3) - to see it take log() on both sides

All correct. Good job.

Nov 9, 2010

24: 135 degrees... oops, just saw thisdude already got it...

A good friend will come and bail you out of jail...but a true friend will be sitting next to you saying, "Damn...that was fun!"

Nov 9, 2010
LetsGoSailing:

#24: 135 degrees... oops, just saw thisdude already got it...

Also that's wrong.

Nov 9, 2010

19 (3,3,3,3,3,1), maybe

Nov 9, 2010
physconomist:

#19 (3,3,3,3,3,1), maybe

Nope. Note: I never said they had to be integers.

Nov 9, 2010

17. All the x should be equal to 16/n. To see this take log(x1x2 ... * xn) and consider what happens when you perturb any of the x in the sum of log(x).

18. same as 17 - replace 16 with k.

Nov 9, 2010
qtrade:

#17. All the x should be equal to 16/n. To see this take log(x1x2 ... * xn) and consider what happens when you perturb any of the x in the sum of log(x).

18. same as 17 - replace 16 with k.

The wording on that was confusing. You CHOOSE n. I'll edit to clarify.

Nov 9, 2010
qtrade:

#17. All the x should be equal to 16/n. To see this take log(x1x2 ... * xn) and consider what happens when you perturb any of the x in the sum of log(x).

18. same as 17 - replace 16 with k.

if this is the case (and I believe it is), and (16/n)*n =16 must be true, then the maximum is (16/n)^n for n a whole number. Which I get at (16/6)^6 = 359.5939643347

Nov 9, 2010
monkeysama:
qtrade:

#17. All the x should be equal to 16/n. To see this take log(x1x2 ... * xn) and consider what happens when you perturb any of the x in the sum of log(x).

18. same as 17 - replace 16 with k.

if this is the case (and I believe it is), and (16/n)*n =16 must be true, then the maximum is (16/n)^n for n a whole number. Which I get at (16/6)^6 = 359.5939643347

That solves #17.

Nov 9, 2010

17 A: 2^8. The proof is left as an exercise for the reader.

Nov 9, 2010
monkeysama:

#17 A: 2^8. The proof is left as an exercise for the reader.

This is very incorrect, monkey.

Nov 9, 2010
thisdude:
monkeysama:

#17 A: 2^8. The proof is left as an exercise for the reader.

This is very incorrect, monkey.

yeah, 33332*2 is bigger.

Nov 9, 2010

OOOoohhhh....now he tells me. Ok.

Nov 9, 2010

Huzzah!

Nov 9, 2010

8. 32 seconds?

Metal. Music. Life. www.headofmetal.com

Nov 9, 2010
Pfalzer:

#8. 32 seconds?

You must be misreading the question. The answer for #8 should be less than or equal to the answer for #7, which was 10. #8 is not asking how long until all corners have been traversed.

Nov 9, 2010

18.

You have to maximize (k/n)^n. Taking the derivative you get (ln(k/n)-1)(k/n)^n setting this equal to 0, ln(k/n) = 1 so n = k/e. So the max for a given k equals e^(k/e), minding rounding errors if you want n to be an integer.

Nov 9, 2010
jhconnel:

#18.

You have to maximize (k/n)^n. Taking the derivative you get (ln(k/n)-1)(k/n)^n setting this equal to 0, ln(k/n) = 1 so n = k/e. So the max for a given k equals e^(k/e), minding rounding errors if you want n to be an integer.

I'll accept this. The correct solution is:

k/e+1 >= n >= k/e - 1. Find all integers in this range, and test which one produces a higher value. This is because n must be an integer, and k/e is not an integer.

Nov 9, 2010

I'm halfway done on the first spider problem and have expressed his random walk as a series. Now I just have to dicker with it.

Nov 9, 2010

28 I'm sure there are innumerable ways to solve. Mine is somewhat crude:

EVERY string of nine consecutive integers is divisible by 9

x + (x+1) + (x+2) ... (x+8)
= 9x + 36

Therefore, the sum of two or more of these 9-integer strings back-to-back must also be divisible by 9

There are 999,999,999 integers with 9 digits or less
That means a whole number of these 9-integer strings (111,111,111 of them) consecutively, starting with 1+2...+9

each of them are divisible by 9, as is their sum

Nov 9, 2010
zbb:

#28 I'm sure there are innumerable ways to solve. Mine is somewhat crude:

EVERY string of nine consecutive integers is divisible by 9

x + (x+1) + (x+2) ... (x+8)
= 9x + 36

Therefore, the sum of two or more of these 9-integer strings back-to-back must also be divisible by 9

There are 999,999,999 integers with 9 digits or less
That means a whole number of these 9-integer strings (111,111,111 of them) consecutively, starting with 1+2...+9

each of them are divisible by 9, as is their sum

Correct, although technically there are 1,000,000,000 positive integers with 9 digits or less. Good job.

Nov 9, 2010

23: 2520

31: 12.25

32: 6,12 both pr = 1/9

33. 30, E[cash] = 1.667

Nov 9, 2010
jhconnel:

#23: 2520

31: 12.25

32: 6,12 both pr = 1/9

33. 30, E[cash] = 1.667

23 is wrong, the others are correct. Good job on 31-33.

Nov 9, 2010

20 is so hard that it's difficulty rating out of 5 is 6 factorial, factorial

Nov 9, 2010

Sorry meant 2521

Nov 9, 2010
jhconnel:

Sorry meant 2521

Are you sure about that?

Nov 9, 2010

wait does question 40 have to do with the eigenvalue of the transition matrix?

Nov 9, 2010
acljnle0:

wait does question 40 have to do with the eigenvalue of the transition matrix?

I don't give hints. I only clarify definitions (e.g. integer or not).

Nov 9, 2010

8 - 81/14 seconds.

My explanation may be hard to follow, so draw a picture of cube if that's the case.

There are 4 distinct pairs of opposite corners. When you've been to one of the corners of every pair, you have either gone in a square or in a x-y-z plane (with origin as the fourth corner). Once you've gone in a square, solve x = 1+2/3x to get x = 3 expected seconds until you hit a "furthest corner from any corner you've been to." Similarly, once you've gone in a x-y-z plane, solve x = 1 + 1/3(1 + x) to get x = 2 expected seconds.

When you've been to one of the corners of three distinct pairs (i.e. the 3 corners form vertices of an isosceles right triangle), you are either on the right angle vertex or one of the two 45 degree vertex. Let u be the expected number of seconds when you're on a 45 degree vertex and v be the expected number of seconds when you're on the 90 degree vertex. Then solve u = 1 + 1/3v + 1/3(3) and v = 1 + 2/3u + 1/3(2) to get u = 23/7 and v = 81/21. Note the 3 and 2 comes from above paragraph.

Suppose you've gone to one of the corners of two distinct pairs. Then solve x = 1 + 2/3(23/7) + 1/3x to get x=67/14. Hence, answer is 1 + 67/14 = 81/14.

Nov 9, 2010
vectorkid:

#8 - 81/14 seconds.

My explanation may be hard to follow, so draw a picture of cube if that's the case.

There are 4 distinct pairs of opposite corners. When you've been to one of the corners of every pair, you have either gone in a square or in a x-y-z plane (with origin as the fourth corner). Once you've gone in a square, solve x = 1+2/3x to get x = 3 expected seconds until you hit a "furthest corner from any corner you've been to." Similarly, once you've gone in a x-y-z plane, solve x = 1 + 1/3(1 + x) to get x = 2 expected seconds.

When you've been to one of the corners of three distinct pairs (i.e. the 3 corners form vertices of an isosceles right triangle), you are either on the right angle vertex or one of the two 45 degree vertex. Let u be the expected number of seconds when you're on a 45 degree vertex and v be the expected number of seconds when you're on the 90 degree vertex. Then solve u = 1 + 1/3v + 1/3(3) and v = 1 + 2/3u + 1/3(2) to get u = 23/7 and v = 81/21. Note the 3 and 2 comes from above paragraph.

Suppose you've gone to one of the corners of two distinct pairs. Then solve x = 1 + 2/3(23/7) + 1/3x to get x=67/14. Hence, answer is 1 + 67/14 = 81/14.

I don't think that's right because your final answer isn't a factor of three (or have the denominator a factor of 3).

Nov 10, 2010
vectorkid:

#8 - 81/14 seconds.

My explanation may be hard to follow, so draw a picture of cube if that's the case.

There are 4 distinct pairs of opposite corners. When you've been to one of the corners of every pair, you have either gone in a square or in a x-y-z plane (with origin as the fourth corner). Once you've gone in a square, solve x = 1+2/3x to get x = 3 expected seconds until you hit a "furthest corner from any corner you've been to." Similarly, once you've gone in a x-y-z plane, solve x = 1 + 1/3(1 + x) to get x = 2 expected seconds.

When you've been to one of the corners of three distinct pairs (i.e. the 3 corners form vertices of an isosceles right triangle), you are either on the right angle vertex or one of the two 45 degree vertex. Let u be the expected number of seconds when you're on a 45 degree vertex and v be the expected number of seconds when you're on the 90 degree vertex. Then solve u = 1 + 1/3v + 1/3(3) and v = 1 + 2/3u + 1/3(2) to get u = 23/7 and v = 81/21. Note the 3 and 2 comes from above paragraph.

Suppose you've gone to one of the corners of two distinct pairs. Then solve x = 1 + 2/3(23/7) + 1/3x to get x=67/14. Hence, answer is 1 + 67/14 = 81/14.

This is the right approach, but you have errors so it is incorrect. You're close.

Nov 9, 2010

Sorry read the problem wrong #23 : 2519

34: ((n+1)/2)^j

Nov 9, 2010
jhconnel:

Sorry read the problem wrong #23 : 2519

34: ((n+1)/2)^j

Good job.

Nov 9, 2010

Why is #33 6 or 12. You're expected to win 1/9 (12) if you pick 12, but you're expected to win 2/36 (30) if you pick 30, which is a greater EV.

Nov 9, 2010
vectorkid:

Why is #33 6 or 12. You're expected to win 1/9 (12) if you pick 12, but you're expected to win 2/36 (30) if you pick 30, which is a greater EV.

33 IS 30, I think you misread the solutions.

Nov 9, 2010

28 - another way to solve:

Recall 1 + 2 + ... + n = n(n+1)/2. Let n = 999,999,999. 2 divides 1,000,000,000 and 9 divides 999,999,999.

Nov 9, 2010

27: Every number 1-N will be assigned
so probability that none match up is
(n-1)/n * (n-2)/n ...* 1/n = (n-1)(n-2)...(1)/(n^n)= (n-1)!/(n^n)

The answer is 1-that...which is basically just 1.

Nov 9, 2010
breakinginnew:

27: Every number 1-N will be assigned
so probability that none match up is
(n-1)/n * (n-2)/n ...* 1/n = (n-1)(n-2)...(1)/(n^n)= (n-1)!/(n^n)

The answer is 1-that...which is basically just 1.

naw, that's not right.

Nov 10, 2010

27: 1-1/e

1 - P(nobody is assigned the correct x_i) = 1 - (1-1/n)^n = 1- 1/e as n goes to infinity. Recall from compounded interest (1+r/n)^n = e^r as n goes to infinity.

Nov 10, 2010
vectorkid:

#27: 1-1/e

1 - P(nobody is assigned the correct x_i) = 1 - (1-1/n)^n = 1- 1/e as n goes to infinity. Recall from compounded interest (1+r/n)^n = e^r as n goes to infinity.

good job.

Nov 10, 2010

Problem #40
From what I remember of Markov chains:

So say we label the corners of the cube 1-8. In the example I am trying, the "bottom" of the cube is labeled 1-4 in clockwise fashion, and the top corners 5-8. i.e. 1 is connected to 2,4,5, 2 is connected to 1,3,6 etc.

What we have then is a 8x8 transition matrix ("T") that looks like this:

0 0.3333 0 0.3333 0.3333 0 0 0
0.3333 0 0.3333 0 0 0.3333 0 0
0 0.3333 0 0.3333 0 0 0.3333 0
0.3333 0 0.3333 0 0 0 0 0.3333
0.3333 0 0 0 0 0.3333 0 0.3333
0 0.3333 0 0 0.3333 0 0.3333 0
0 0 0.3333 0 0 0.3333 0 0.3333
0 0 0 0.3333 0.3333 0 0.3333 0

The long-term average of this transition matrix (associated with the eigenvalue 1) is a column vector of sqrt(2)/4.

Expected time would be a e (canonical row vector)(I-T)^-1z, with z a column vector full of ones.

Due to singularity issues, I get something like 7.2058*10^16.

Nov 10, 2010
acljnle0:

Problem #40
From what I remember of Markov chains:

So say we label the corners of the cube 1-8. In the example I am trying, the "bottom" of the cube is labeled 1-4 in clockwise fashion, and the top corners 5-8. i.e. 1 is connected to 2,4,5, 2 is connected to 1,3,6 etc.

What we have then is a 8x8 transition matrix ("T") that looks like this:

0 0.3333 0 0.3333 0.3333 0 0 0
0.3333 0 0.3333 0 0 0.3333 0 0
0 0.3333 0 0.3333 0 0 0.3333 0
0.3333 0 0.3333 0 0 0 0 0.3333
0.3333 0 0 0 0 0.3333 0 0.3333
0 0.3333 0 0 0.3333 0 0.3333 0
0 0 0.3333 0 0 0.3333 0 0.3333
0 0 0 0.3333 0.3333 0 0.3333 0

The long-term average of this transition matrix (associated with the eigenvalue 1) is a column vector of sqrt(2)/4.

Expected time would be a e (canonical row vector)(I-T)^-1z, with z a column vector full of ones.

Due to singularity issues, I get something like 7.2058*10^16.

The answer is orders of magnitude smaller than that, as you alluded to.

Nov 10, 2010

Question 2:

15:55:51 to 20:00:02

"I came, I saw, I networked"

Nov 10, 2010
marketimpact:

Question 2:

15:55:51 to 20:00:02

good job. no prior exposure?

Nov 10, 2010

8: 89/14

Oh my god that error took me forever to find. This is what I get for not using a calculator...

Nov 10, 2010
vectorkid:

#8: 89/14

Oh my god that error took me forever to find. This is what I get for not using a calculator...

You're going to love me for this...you're still wrong.

Nov 10, 2010

Wait nvm I'm still wrong.

Nov 10, 2010
vectorkid:

Wait nvm I'm still wrong.

Actually, 81/14 was correct. I made an error in my arithmetic, actually. Your first answer was right. Sorry about that. Good solution.

Nov 10, 2010

oh fucking hell realized what I did wrong

This problem is a variation on the more famous question of the expected time of a monkey randomly hitting a typewriter at the rate of one letter a second with keys of letters a through z only spelling "abracadabra"

Nov 10, 2010
acljnle0:

oh fucking hell realized what I did wrong

This problem is a variation on the more famous question of the expected time of a monkey randomly hitting a typewriter at the rate of one letter a second with keys of letters a through z only spelling "abracadabra"

This is a bad analogy. The letters of the typewriter are independent. If the monkey types an "e", any letter can follow. In contrast, if the spider goes to vertex j, there are only three vertexes he can leave to.

Nov 10, 2010

Spider question answer is 10.

Nov 10, 2010

Oh okay. Hurray now I can sleep in peace.

Thanks for these teasers btw. They are quite helpful.

Nov 10, 2010
vectorkid:

Oh okay. Hurray now I can sleep in peace.

Thanks for these teasers btw. They are quite helpful.

Yeah I did some stupid arithmetic error and had 104/14. So when you posted 84/14 I was like "OH he made a mistake". But yeah, my error.

Nov 10, 2010

How is this spider problem different than the one you posted? I still think this solution of 10 is the right answer.

An ant and a blind spider are on opposite corners of a cube. The ant is stationary and the spider moves at random from one corner to another along the edges only. What is the expected number of turns before the spider reaches the ant? Optional: Also solve for a square, octahedron, icosahedron, and dodecahedron.
Answer
Problem 4 Answer
The answer is 10.

If the spider started at a corner diagonally on the same face as the ant the answer would be 9, and if the spider started at an adjacent corner the answer would be 7.

Here are answers for other figures:

Square: 4
Octahedron: 6
Dodecahedron: 35
Icosahedon: 15

Michael Shackleford, A.S.A.

Solution
Let x=number of turns to reach ant from starting point.
Let y=number of turns to reach ant from diagonal corner on same face as ant.
Let z=number of turns to reach ant from an adjacent corner to ant.

After one turn the spider will be on a diagonal corner of a common face as the ant. So the mean number of turns from the x position is one more than the mean number from the y position:

E(x)=1+E(y).

Once at a y position there is a 2/3 chance it will then move to a z position, and a 1/3 chance back to an x position:

E(y)=(2/3)(1+E(z))+(1/3)(1+E(x)).

If the spider arrives at a z position there is a 1/3 chance it will move to the ant, and a 2/3 chance it will move back to a y position:

E(z)=(1/3)1+(2/3)(1+E(y)).

With these three equations and three unknowns it is not difficult to solve for E(x), E(y), and E(z).

Michael Shackleford, A.S.A.

Nov 10, 2010
monkeysama:

How is this spider problem different than the one you posted? I still think this solution of 10 is the right answer.

An ant and a blind spider are on opposite corners of a cube. The ant is stationary and the spider moves at random from one corner to another along the edges only. What is the expected number of turns before the spider reaches the ant? Optional: Also solve for a square, octahedron, icosahedron, and dodecahedron.
Answer
Problem 4 Answer
The answer is 10.

If the spider started at a corner diagonally on the same face as the ant the answer would be 9, and if the spider started at an adjacent corner the answer would be 7.

Here are answers for other figures:

Square: 4
Octahedron: 6
Dodecahedron: 35
Icosahedon: 15

Michael Shackleford, A.S.A.

Solution
Let x=number of turns to reach ant from starting point.
Let y=number of turns to reach ant from diagonal corner on same face as ant.
Let z=number of turns to reach ant from an adjacent corner to ant.

After one turn the spider will be on a diagonal corner of a common face as the ant. So the mean number of turns from the x position is one more than the mean number from the y position:

E(x)=1+E(y).

Once at a y position there is a 2/3 chance it will then move to a z position, and a 1/3 chance back to an x position:

E(y)=(2/3)(1+E(z))+(1/3)(1+E(x)).

If the spider arrives at a z position there is a 1/3 chance it will move to the ant, and a 2/3 chance it will move back to a y position:

E(z)=(1/3)1+(2/3)(1+E(y)).

With these three equations and three unknowns it is not difficult to solve for E(x), E(y), and E(z).

Michael Shackleford, A.S.A.

10 is correct for #7. The spider question is well known, but I have a lot of variations on it...#8,#40,#41. Vectorkid was solving #8, which is significantly harder than #7.

Nov 10, 2010

Added ten more questions. So far 20/50 have been solved. I'll probably slow down significantly until a greater proportion have been answered.

Nov 11, 2010

I think you can do 40 with a Markov chain. I have a state for every possible arrangement of every possible number of corners you've visited. So that's ( 8c1 + ... + 8c8) = 255 states (although some states are unreachable). Figuring out the transitions is messy though because to save space I'm not keeping track of the actual corner you're on. I'd like to think there's an easier way.

Nov 11, 2010
loveandpop:

I think you can do 40 with a Markov chain. I have a state for every possible arrangement of every possible number of corners you've visited. So that's ( 8c1 + ... + 8c8) = 255 states (although some states are unreachable). Figuring out the transitions is messy though because to save space I'm not keeping track of the actual corner you're on. I'd like to think there's an easier way.

There's a simpler way. The solutions for the previous spider-in-a-cube questions should be helpful.

Nov 11, 2010

Do not have any ideas on Qs 11-16. Is it possible to get the close form of the expected values (E(A) and E(B))?

Nov 11, 2010
danmu:

Do not have any ideas on Qs 11-16. Is it possible to get the close form of the expected values (E(A) and E(B))?

Yes

Nov 11, 2010
thisdude:
danmu:

Do not have any ideas on Qs 11-16. Is it possible to get the close form of the expected values (E(A) and E(B))?

Yes

Thanks. Keep thinking......

Nov 11, 2010

Hi, thisdude. I get confused~ What is the difference between Game A and Game B?

It seems that for Game B, you just have n chances to re roll an n sided die, and you can stop any time and take the result.

What about Game A?

The result you gave
"E(A(1)) = 1.
E(A(2)) = 2.5+.5(.52+.252+.251) = 2 - .1251 = 1.875" also works for Game B, does it?

Nov 12, 2010
danmu:

Hi, thisdude. I get confused~ What is the difference between Game A and Game B?

It seems that for Game B, you just have n chances to re roll an n sided die, and you can stop any time and take the result.

What about Game A?

The result you gave
"E(A(1)) = 1.
E(A(2)) = 2.5+.5(.52+.252+.251) = 2 - .1251 = 1.875" also works for Game B, does it?

No, game b is the reverse. They have the same expectations for 1 and 2, that's all.

Nov 12, 2010

Still don't understand the rules of Game A and Game B:( I have asked several people around me, they don't get it either.
Now my understanding is,
Game A: for an n sided die, you may roll a maximum of n times. For the i-th roll, you may get 1,2,3,..,i. For example, when n=3, the first roll you can only get 1, then you may choose whether to re roll or not (of course you will re roll). On the 2nd roll, you may get a 1 or a 2. Then the 3rd roll, you may get a 3 or less. For different n, there are different optimal strategies, which tells when to stop. (e.g. when the i-th roll gets a result larger then x(i), then stop)

Game B: the difference between Game A and B is that for the i-th roll, the possible results are 1,2,3,...,n-i+1.

Am I right? If not, can you explain it? Thanks~

Nov 13, 2010
danmu:

Still don't understand the rules of Game A and Game B:( I have asked several people around me, they don't get it either.
Now my understanding is,
Game A: for an n sided die, you may roll a maximum of n times. For the i-th roll, you may get 1,2,3,..,i. For example, when n=3, the first roll you can only get 1, then you may choose whether to re roll or not (of course you will re roll). On the 2nd roll, you may get a 1 or a 2. Then the 3rd roll, you may get a 3 or less. For different n, there are different optimal strategies, which tells when to stop. (e.g. when the i-th roll gets a result larger then x(i), then stop)

Game B: the difference between Game A and B is that for the i-th roll, the possible results are 1,2,3,...,n-i+1.

Am I right? If not, can you explain it? Thanks~

Let me use n=10.

Game A. roll a ten-sided die. You may re-roll ONLY a 1. On the re-roll, you may re-roll ONLY a 2 or less. Ect. Maximum of 11 rolls.

Game B. roll a ten-sided die. You may re-roll a 10 or less (any result). Then you may re-roll a 9 or less. Ect. Maximum of 11 rolls.

Nov 15, 2010
Comment
Nov 16, 2010
Comment
Nov 24, 2010
Comment
Nov 24, 2010
Comment
Nov 24, 2010