3 ms·

I once applied for a job and got an email questionnaire back. On of the questions was, "Given 9 balls, one of which is heavier than he others, what is the mini

by russell 17y ago

I once applied for a job and got an email questionnaire back. On of the questions was, "Given 9 balls, one of which is heavier than he others, what is the minimum number of weighings to find the heavy ball? Write an algorithm." I wrote back, "I have a question for you. What is the maximum number of balls from which you could find the heavy one in 5 weighings? If you know the answer to that one, then you know I know the answer to your problem." Needless to say I didn't get the interview. Must have been written off as a smart-ass.

jodrellblank 17y ago
If I walk up to the line and pick one ball at random and it is the heaviest by pure luck, that demonstrates it can be done in zero weighings - more than 10% of the time, even - so if your number was higher than zero it's not really a 'minimum'. If you put all the balls on a stretched rubber sheet and picked the one with the deepest depression, would that be one weighing, nine weighings or no weighings?
- camccann 17y ago
  Questions of that type often state that your only means of weighing the objects is a balance scale, i.e., you can put balls 1 and 2 on one side and balls 3 and 4 on the other to see which pair is heavier, and that's "one weighing". I'm guessing that's what russell's question is, at any rate.
- dmoney 17y ago
  I think it's implied that you want to know whether or not the ball you've picked is the heavy one. What's not clear is whether "weighing" is a unary operation returning the weight of the ball, or a binary operation returning the heavier of two balls.
eru 17y ago
> "I have a question for you. What is the maximum number of balls from which you could find the heavy one in 5 weighings? If you know the answer to that one, then you know I know the answer to your problem." I don't get it. What does that answer tell me? (Unless the answer I calculated for your problem was not the right answer, and the right answer would tell me something.)

by russell 17y ago

jodrellblank 17y ago

If I walk up to the line and pick one ball at random and it is the heaviest by pure luck, that demonstrates it can be done in zero weighings - more than 10% of the time, even - so if your number was higher than zero it's not really a 'minimum'. If you put all the balls on a stretched rubber sheet and picked the one with the deepest depression, would that be one weighing, nine weighings or no weighings?

camccann 17y ago
Questions of that type often state that your only means of weighing the objects is a balance scale, i.e., you can put balls 1 and 2 on one side and balls 3 and 4 on the other to see which pair is heavier, and that's "one weighing". I'm guessing that's what russell's question is, at any rate.
dmoney 17y ago
I think it's implied that you want to know whether or not the ball you've picked is the heavy one. What's not clear is whether "weighing" is a unary operation returning the weight of the ball, or a binary operation returning the heavier of two balls.

eru 17y ago

> "I have a question for you. What is the maximum number of balls from which you could find the heavy one in 5 weighings? If you know the answer to that one, then you know I know the answer to your problem." I don't get it. What does that answer tell me? (Unless the answer I calculated for your problem was not the right answer, and the right answer would tell me something.)