Brain teasers have a strange power. For many they evoke nothing more than a mild and transient sense of curiosity. But for a certain subset of people they create an irresistible intellectual temptation which even needs to actively be avoided at times as not to completely derail conversations and take over whole afternoons.

For better or worse, I am in the camp of people who are highly susceptible to brain teasers. I just love them too much. More than once in my lifetime I had to ask a friend not to tell me about a particular brain teaser they had heard about because I knew it would inevitably take over my mind and send me down an almost hypnotic spiral of thoughts whose only escape would be finding the solution.

While brain teasers can admittedly turn into ridiculously powerful distractions for some of us, they are not necessarily a waste of time. They have high recreational value and help the mind to enter a playful and creative state. They serve as mental gymnastics to directly train logical thinking skills, and logical thinking is arguably one of the most powerful transferable skills that exists. And last but not least, brain teasers are canonically used nowadays in job interviews at some of the worlds top employers (Google, Facebook, Microsoft, prestigious hedge funds, …).

Brain teaser (ruthless machine learning researchers fighting over GPUs):

Five machine learning researchers, lets call them R1, R2, R3, R4 and R5, are given 100 GPUs by their institute which they are supposed to split up amongst each other. The bureaucratic rules of their institute demand that they split up the GPUs according to a particular system.

R1 needs to come up with a proposal about how to split up the GPUs amongst all five researchers. After that, there is a vote. If a strict majority (strictly more than 50%) votes for the proposal of R1, then things are settled. However, if there is no strict majority, then R1 gets thrown out of the window. The next one to make a proposal for how to split up the GPUs amongst the remaining four researchers is then R2, and the same rules apply. This continues until someone comes up with a proposal that is supported by a strict majority of researchers or until everyone but R5 has been thrown out of the window.

We assume that each researcher is perfectly logical and wants to maximise nothing but his/her respective number of GPUs while avoiding to be thrown out of the window. Furthermore, we assume that we are dealing with a bunch of particularly ruthless researchers and if they can throw someone out of the window without having a disadvantage, they will do so.

Assume that you are R1. How do you propose to split up the GPUs?

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

Solution:

If you are R1, then you should propose to keep 97 GPUs for yourself, while giving one GPU to R3 and two GPUs to either R4 or R5 (it does not matter whether you choose R4 or R5). To see why this is the best strategy, think about the problem inductively.

If there is only one researcher, R1, he will obviously take all 100 GPUs.

If there are two researchers, R1 and R2, then R2 will vote against R1, no matter what, and will get R1 thrown out of the window and subsequently take all 100 GPUs.

If there are three researchers, R1, R2, R3, then R1 will claim all the 100 GPUs for himself and will have the support of R2 in doing so and thus a majority. Because if R2 would vote against R1, then so would R3, which would get R1 thrown out of the window. In the next round R3 would then throw R2 out of the window which R2 naturally wants to avoid. Therefore R2 needs to support R1.

If there are four researchers, R1, R2, R3, R4, then R1 needs to convince at least two other researchers to vote for him or he will get thrown out of the window. He can do so by keeping 98 GPUs and giving one GPU to R3 and one GPU to R4. Then R4 and R3 will support the proposal of R1, because if they would get him thrown out of the window instead, the remaining group would revert back to the case of three researchers and then R3 and R4 would get nothing.

Finally, if there are five researchers, R1, R2, R3, R4, R5, then R1 can get away with keeping 97 GPUs while giving one GPU to R3 and two GPUs to either R4 or R5. This is because if the group throws R1 out of the window, then the rest of them would revert back to the case of four researchers and then R4 and R5 would only get one GPU each while R3 would get nothing.

Hope you had fun!