A riddle or two, if you will

[Jerrek]

Microsoft has a very long tradition of asking one to solve a puzzle or two during an interview. They pride themselves of hiring the top 10% of the top 10% of people. Here are two riddles. I'll return tomorrow night, my time (in 24 hours) with the answers. Don't Google or cheat!

For those that dare, or for those that like to exercise the mind, here they are:

-1-
Counting in base 10 is relatively simple. 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, etc.
Counting in base 2 is also relatively simple. 0, 1, 10, 11, 100, 101, 110, 111, etc.

Count in base -2 (that is negative two) to the equivalent of 6.



-2-
Two containers are each filled with 100 balls. One container has 100 white balls, and the other 100 black balls. A man will randomly pick a container, and randomly draw a ball. If he draws a white ball, you live. If he pulls a black ball, you die.

You can shuffle the balls in any way you want. You must use all 200 balls. You can use any combination you want. Shuffle the balls in a way to maximize your chances of living.

[Jon M]

-2-

Seems a bit too obvious.. but does "shuffling" allow us to empty the two containers and half fill each one with black balls.. then fill the remaining halves with white balls?

[Nemesis]

LOL, exactly my thinking

[Nemesis]

Hmmmm

http://en.wikipedia.org/wiki/Negabin..._in_negabinary

Based on that, a M$ interview could take a LONG time .....

[Mr_love_monkey]

Originally Posted by Jerrek

-2-
Two containers are each filled with 100 balls. One container has 100 white balls, and the other 100 black balls. A man will randomly pick a container, and randomly draw a ball. If he draws a white ball, you live. If he pulls a black ball, you die.

You can shuffle the balls in any way you want. You must use all 200 balls. You can use any combination you want. Shuffle the balls in a way to maximize your chances of living.

Dunno if I'm missing something here... but wouldn't you just leave them as they are? - if you have to use all the balls, and it's split 100 white / 100 black then no matter what you would still have a 50/50 chance of getting a white one (or a black one) - so you might as well leave them how they are and have a few minutes to relax before they kill you

[Stu038]

I'm usually wrong on this sort of thing but I think number 2 is a trick question.

With equal numbers of both colours spread between two containers, surely you aren't gonna be able to change the odds any better than 50/50.

As for the counting lark I have enough problems with normal binary without working in negatives

[Jon M]

Don't forget that we're dealing with balls not liquid.. if we put 50% black balls in each container... then put 50% white in each container .. they won't mix together, so the white ones should be at the top and therefore more likely to be picked.

[Rob]

Originally Posted by s1lv3r

Don't forget that we're dealing with balls not liquid.. if we put 50% black balls in each container... then put 50% white in each container .. they won't mix together, so the white ones should be at the top and therefore more likely to be picked.

Dunno about that theory. If I was picking the balls, I'd be tempted to reach to the bottom of the container, just as you hope someone might delve into a bucket when picking out raffle tickets or whatever. Why should they pick from the top?

I think the point is that the ball picking is supposed to be completely random. Somehow you must remove that random chance. That is making my little brain hurt.

[Rob]

Originally Posted by Nemesis

Hmmmm

http://en.wikipedia.org/wiki/Negabin..._in_negabinary

Based on that, a M$ interview could take a LONG time .....

Far too complex for my liking - Don't think I'll be applying for a M$ job in a hurry, unless it's as a cleaner

[BBKing]

No googling used at all here.

Bases - I've drawn up a table to see what the patterns of bases are, and it seems that an inherent property of any base system is that you have to have the same number of distinct symbols as the base number. Viz in binary (base 2) you have two symbols, 0 and 1, in base 10 you have 10 (digits from 0 to 9), in hex (base 16) you have 16 (digits 0 to 9, letters A to F).

From that it follows that base 1 you're allowed 1 symbol (the 0), which means the only way to count is to use multiple 0s (0. 00, 000) which are usually regarded as the same value. How you'd count with a total of -2 digits my brain can't cope with.

Balls - this is easy. Since the odds of picking each container are the same, if you can manipulate the odds of survival on each container you have a chance, as the total survival odds is proportional to the sum of the survival odds on each container.

It's fairly easy to have odds of 100% that if you pick container A, you survive. Just put only white balls in it.

Obviously if you put all 100 white balls in, this gets you nowhere, as the other box has 100 black balls in and thus a 100% chance of death if that B is picked. Thus the total survival odds are 50% (the same as the odds of picking container B.

If, however, you only put 1 white ball into A, you *still* have the 100% survival chance in the event that A is chosen, but you now have *much* less than 100% chance of death when B is chosen. In fact the odds are close to 75% that you will survive:

If A contains 1 white ball, total 1 ball
B must contain 99 white and 100 black, total 199 balls

Odds of choosing A
50%
Odds of pulling a white having chosen A
100% (1/1)

Odds of choosing B
50%
Odds of pulling a white having chosen B
~50% (99/199)

Total odds of survival are

Odds of choosing A, then pulling a white

50% * 100%

+

Odds of choosing B, then pulling a white

50% * 50%

which is
50% + 25%

or 75% (actually 74.87% since 99/199 is slightly less than 50%).

I don't think you can do better than this, if you add any black balls to A you lose your 100% survival odds, if you add any white balls to A you shift the 99/199 down to 98/198, 97/197 which are all < 99/199.

So the answer is, put one white ball in either container and the rest of the balls in the other.

[Jerrek]

Originally Posted by s1lv3r

Don't forget that we're dealing with balls not liquid.. if we put 50% black balls in each container... then put 50% white in each container .. they won't mix together, so the white ones should be at the top and therefore more likely to be picked.

No, I clearly said RANDOM. They will be randomly picked. Layering balls is not going to help you.

[Jerrek]

Originally Posted by BBKing

No googling used at all here.

Bases - I've drawn up a table to see what the patterns of bases are, and it seems that an inherent property of any base system is that you have to have the same number of distinct symbols as the base number. Viz in binary (base 2) you have two symbols, 0 and 1, in base 10 you have 10 (digits from 0 to 9), in hex (base 16) you have 16 (digits 0 to 9, letters A to F).

From that it follows that base 1 you're allowed 1 symbol (the 0), which means the only way to count is to use multiple 0s (0. 00, 000) which are usually regarded as the same value. How you'd count with a total of -2 digits my brain can't cope with.

Actually no, you use |base| digits. If your base is 2, you have |2| digits, which is 2. But for |-2|, that comes to 2 too! It is hard, yes.

Balls - this is easy. Since the odds of picking each container are the same, if you can manipulate the odds of survival on each container you have a chance, as the total survival odds is proportional to the sum of the survival odds on each container.

It's fairly easy to have odds of 100% that if you pick container A, you survive. Just put only white balls in it.

Obviously if you put all 100 white balls in, this gets you nowhere, as the other box has 100 black balls in and thus a 100% chance of death if that B is picked. Thus the total survival odds are 50% (the same as the odds of picking container B.

If, however, you only put 1 white ball into A, you *still* have the 100% survival chance in the event that A is chosen, but you now have *much* less than 100% chance of death when B is chosen. In fact the odds are close to 75% that you will survive:

If A contains 1 white ball, total 1 ball
B must contain 99 white and 100 black, total 199 balls

Odds of choosing A
50%
Odds of pulling a white having chosen A
100% (1/1)

Odds of choosing B
50%
Odds of pulling a white having chosen B
~50% (99/199)

Total odds of survival are

Odds of choosing A, then pulling a white

50% * 100%

+

Odds of choosing B, then pulling a white

50% * 50%

which is
50% + 25%

or 75% (actually 74.87% since 99/199 is slightly less than 50%).

I don't think you can do better than this, if you add any black balls to A you lose your 100% survival odds, if you add any white balls to A you shift the 99/199 down to 98/198, 97/197 which are all < 99/199.

So the answer is, put one white ball in either container and the rest of the balls in the other.

You got it!! Nice question for an interview, eh?

[danielf]

Originally Posted by BBKing

No googling used at all here.

<snip>

So the answer is, put one white ball in either container and the rest of the balls in the other.

Can't fault that. I'm impressed!

Originally Posted by Jerrek

No, I clearly said RANDOM. They will be randomly picked. Layering balls is not going to help you.

Could you have pulled a "Kobyashi Maru" on them and just point out that, strictly speaking, they are using the term "random" incorrectly in this context?

[BBKing]

The way I was doing it was wrong, you can't use induction to work from base 2 to base -2 as base 1,0 and -1 are meaningless. You have to think about another basic property of base something, such as that you can convert from one base to another by dividing by the base and taking the remainder as the next digit in the number to that base (but backwards, see below). That way you can hop happily from base 10 to base -2 without knowing anything about any pattern.

e.g. for base 10 to base 8, converting the number 100 gives you

100 / 8 = 12 remainder 4
12 / 8 = 1 remainder 4
1/12 = 0 remainder 1

so 100 in base 8 is 144 (1 * 64 + 4 * 8 + 4 * 1 or 64 + 32 + 4)

For base 2
100 /2 = 50 remainder 0
50 / 2 = 25 remainder 0
25 / 2 = 12 remainder 1
12 / 2 = 6 remainder 0
6 / 2 = 3 remainder 0
3 / 2 = 1 remainder 1
1 / 2 = 0 remainder 1

Answer 1100100 or 64 + 32 + 4 (again)

Useful trick. I leave base -2 as an exercise to the reader.

A modification on the balls. What's the best option for your survival if you *must* have at least 1 black ball and 1 white ball in each container?