Classic math puzzles for job interviews

http://www.scribd.com/vacuum?url=http://pdos.csail.mit.edu/~petar/mathjob.pdf

by pc • 18 years ago

32 18 18 years ago

scribd.com

Zeromus• 18 years ago

Ok, I fail and don't get the job, I get it... but where are the answers!

redorb• 18 years ago

on the mouse one, could you not mix wines?

100 bottles, divide into 2 groups, feed mouse...

Separate poisoned bottles into 2 groups feed mouse..

basically 100,50,25,12,6,3,1 ... 6 mice needed.

martianpenguin• 18 years ago

There is only 1 day. Wouldn't you just separate the bottles evenly across all the mice?

paulgb2• 18 years ago

That way you could serve 900 bottles. Can you serve more?

Hint: Look at the number of possible outcomes. In this case, each of the 10 mice can either live or die. That gives us 2^10 = 1024 possible outcomes. We can only encounter 1000 possible initial configurations of bottles. Is there a way to set it up so that each of the 1000 possible outcomes maps to an initial configuration?

kurtosis• 18 years ago

These problems are a lot of fun and in most cases there are interesting general lessons in their solutions, but the way the interview system seems to work is that every year there's a new book or sheet of puzzles that everyone memorizes and then pretends to have never seen before when asked during an interview.

bayleo• 18 years ago

Yeah, these puzzles are too unique and are in many cases well known problems/paradoxes that candidates are likely to know. Interviewers might be better served by asking a generic, LSAT-style logic game or a somewhat simple but time consuming math problem (maybe polynomial factorization).

paulgb2• 18 years ago

#5 is impossible. Martin Gardner has a nice proof of this: observe that each domino must cover a black and a white square, no matter how you orient it. When you remove two opposite squares, you remove two squares of the same colour. Imagine you have put 30 of the dominoes on the board, then two squares remain uncovered. These squares must be the same colour (by the above rules), so there is no way the last domino can cover them both.

abossy• 18 years ago

Wow, I am surprised #13 is listed as a 1-star problem.

I was told a story about this problem by a professor while in class. Supposedly, Edgser Djisktra couldn't sleep one night due to jet lag. He was currently going through a phase in which was exercising the power of thought, practicing thought-exercises such as these without a pencil and paper. While in bed that night, awake due to jet lag, he solved this problem. The professor told us that none of us were smart enough to solve this problem. Hardly seems worthy of one star. :)

Tichy3• 18 years ago

I haven't solved it yet, but it seems to be solvable by sheer diligence? Is there a faster solution? I think in an interview I would ask to write a computer program that solves it. Wait - I guess now I have to try that :-(

Edit: which programming language has good support for primes? I thought I saw one recently, but can't find it now.

ChaitanyaSai• 18 years ago

Using the Goldbach Conjecture makes it easier.

Tichy3• 18 years ago

Update: OK, now I wrote the program, and in hindsight it was overkill. Just check the candidates for x+y starting from below, and the right solution appears pretty quickly (there are 24 candidates for x+y, but it is not necessary to check them all).

jatemack• 18 years ago

Need answers? Email the PDF creator.

"Due to popular demand: I will write up and give out the solution to any problem in return for an interesting new problem. This will serve as a good growing force for the collection of problems."

http://pdos.csail.mit.edu/~petar/misc.html

billroberts• 18 years ago

In what kind of job interview would asking any of these help you select an employee?

nickb• 18 years ago

Professional puzzle solver job interview!

In all seriousness, if you start getting these questions during the interview, you should realize that these people don't know how to hire and you should move away.

gocards44• 18 years ago

You do the mice as binary and then read them like 0's and 1's if they die or don't die

Tichy3• 18 years ago

I don't see how the square could be partitioned, maybe I am reading it wrong? My informal counter proof by contradiction (decrypt with rot13.com):

fvapr gur cnegvgvba vf svavgr, gurer vf n fdhner Z jvgu gur fubegrfg fvqr. Abj pbafvqre gur fdhnerf nybat gur gbc fvqr bs gur havg fdhner. Gur fznyyrfg fdhner nzbat gurz unf n fvqr yratgu < 0.5, yrg'f pnyy vg F1. Abj pbafvqre ebj bs fdhnerf pbirevat gur obggbz fvqr bs F1. Gurer unf gb or n fznyyrfg fdhner nzbat gurz, jvgu yratgu < 0.5* fvqr_yratgu_bs(F1) = 0.25. Yrg gung fznyyrfg fdhner or F2. Abj pbafvqre gur ebj bs fdhnerf ng gur obggbz bs gung fdhner. Gurer unf gb or n fznyyrfg fdhner F3 nzbat gurz jvgu fvqr yratgu < 0.5*0.25 = cbjre(0.5,3). Naq fb ba - gurer vf nyjnlf n arkg ebj bs fdhnerf, nf gur fznyyrf fdhner va gur ebj pna abg gbhpu gur obggbz fvqr bs gur havg fdhner. Urapr V pna tb ba yvxr gung vasvavgryl, orpnhfr yvz cbj(0.5,a) = 0 riraghnyyl V'yy svaq n fdhner gung vf fznyyre guna Z, pbagenqvpgvba.

Classic math puzzles for job interviews

Related Stories