Few companies ask the below brain teaser to the candidates during the interview.
Seven pirates of different ages have a treasure of 100 gold coins.
On their ship, they decide to split the coins using this scheme: The oldest pirate proposes how to share the coins, and all pirates (including the oldest) vote for or against it.
If 50% or more of the pirates vote for it, then the coins will be shared that way. Otherwise, the pirate proposing the scheme will be thrown overboard, and the process is repeated with the pirates that remain.
As pirates tend to be a bloodthirsty bunch, if a pirate would get the same number of coins if he voted for or against a proposal, he will vote against so that the pirate who proposed the plan will be thrown overboard.
Assuming that all 7 pirates are intelligent, rational, greedy, and do not wish to die, (and are rather good at math for pirates) what will happen?
But what if it is a coding challenge:
N pirates of different ages have a treasure of 100 gold coins.
On their ship, they decide to split the coins using this scheme:
The oldest pirate proposes how to share the coins, and all pirates (including the oldest) vote for or against it.
If 50% or more of the pirates vote for it, then the coins will be shared that way. Otherwise, the pirate proposing the scheme will be thrown overboard, and the process is repeated with the pirates that remain.
As pirates tend to be a bloodthirsty bunch, if a pirate would get the same number of coins if he voted for or against a proposal, he will vote against so that the pirate who proposed the plan will be thrown overboard.
Assuming that all N pirates are intelligent, rational, greedy, and do not wish to die, (and are rather good at math for pirates) what will happen? (Provided condition: N<50)
Write a program that provides coins distribution such that the maximum number of coins that the oldest pirate might get.
The puzzles from my book “Brain Teasers with Coding For Data Scientist” are published on this link. Also, don’t forget to check my puzzle books “Brain Teasers with Coding For Data Scientist 2: 9 New Computational Puzzles” and “Puzzles with Coding: Puzzles for Everyone” and “Computational Puzzles To Flex Your Brain: 50 original puzzles to sharpen computing mind and mathematical skills” at Amazon. For purchasing my books or related queries, feel free to contact me. In these books, you will find interesting brain teasers those are suitable for coders as well as non-coders. Coding solutions are also provided with Python code. So, grab a copy of those books and jump into the world of fascinating and exciting brain teasers.
Solution:
Let’s take N=5 for example.
Let us name the pirates (from oldest to youngest): ‘A’, ‘B’, ‘C’, ‘D’ and ‘E’.
Working backwards:
If N=2 (‘D’ & ‘E’ only)
2 Pirates: ‘D’ splits the coins 100 : 0 (giving himself all the gold). His vote (50%) is enough to ensure the deal.
If N=3 (‘C’, ‘D’ & ‘E’)
3 Pirates: ‘C’ splits the coins 99 : 0 : 1. ‘E’ will accept this deal (getting just 1 coin), because he knows that if he rejects the deal there will be only two pirates left, and he gets nothing.
If N=4 (‘B’, ‘C’, ‘D’ & ‘E’)
4 Pirates: ‘B’ splits the coins 99 : 0 : 1 : 0. By the same reasoning as before, ‘D’ will support this deal. ‘B’ would not waste a spare coin on ‘C’, because ‘C’ knows that if he rejects the proposal, he will pocket 99 coins once ‘B’ is thrown overboard. ‘B’ would also not give a coin to ‘E’, because ‘E’ knows that if he rejects the proposal, he will receive a coin from ‘C’ in the next round anyway.
If N=5 (‘A’, ‘B’, ‘C’, ‘D’ & ‘E’)
5 Pirates: ‘A’ splits the coins 98 : 0 : 1 : 0 : 1. By offering a gold coin to ‘C’ (who would otherwise get nothing) he is assured of a deal.
(Note: In the final deal ‘A’ would not give a coin to ‘B’, who knows he can pocket 99 coins if he votes against ‘A’s proposal and ‘A’ goes overboard. Likewise, ‘A’ would not give a coin to ‘D’, because ‘D’ knows that if he votes against the proposal, ‘A’ will be voted overboard and ‘B’ will propose to offer ‘D’ the same single coin as ‘A’. All else equal, ‘D’ would rather see ‘A’ go overboard and collect his one coin from ‘B’.)
Working forwards:
What if, 6 pirates(‘A’, ‘B’, ‘C’, ‘D’, ‘E’ & ‘F’)
If N=6
The oldest pirate splits the coins 98 : 0 : 1 : 0 : 1 : 0
What if, 7 pirates(‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’ & ‘G’)
If N=7
The oldest pirate splits the coins 97 : 0 : 1 : 0 : 1 : 0 : 1
Thus, if N is odd number than the youngest one gets 0 gold coin else he gets 1 gold coin.
If N is odd then
The oldest pirate splits the coins (100-((N-1)/2) ) : 0 : 1 :0 … : 0 : 1
If N is even then
The oldest pirate splits the coins (100-((N-1)/2) ) : 0 : 1 :0 … : 1 : 0
Coding Solution:
import math
#You can add a check for no_of_pirates <50
no_of_pirates = int(input('Enter number of pirates:'))
print("Oldest to youngest pirate coins distribution")
if (no_of_pirates % 2 == 0):
oldest_pirate_coins = 100 - ((no_of_pirates - 1) / 2)
print(no_of_pirates, 'number (oldest) pirate gets', math.ceil(oldest_pirate_coins), 'coins')
for i in range(no_of_pirates-1,0,-1):
if(i % 2):
print(i,'number pirate gets','0 Coin')
else:
print(i,'number pirate gets','1 Coin')
else:
oldest_pirate_coins = 100 - ((no_of_pirates - 1) / 2)
print(no_of_pirates, 'number (oldest) pirate gets', math.ceil(oldest_pirate_coins), 'coins')
for i in range(no_of_pirates - 1, 0, -1):
if (i % 2):
print(i,'number pirate gets', '1 Coin')
else:
print(i,'number pirate gets','0 Coin')
Note : (Keeping non-coder readers in mind, code optimization is not fully utilized.)
Test Output 1:
Enter number of pirates:7
Oldest to youngest pirate coins distribution
7 number (oldest) pirate gets 97 coins
6 number pirate gets 0 Coin
5 number pirate gets 1 Coin
4 number pirate gets 0 Coin
3 number pirate gets 1 Coin
2 number pirate gets 0 Coin
1 number pirate gets 1 Coin
Test Output 2:
Enter number of pirates:30
Oldest to youngest pirate coins distribution
30 number (oldest) pirate gets 86 coins
29 number pirate gets 0 Coin
28 number pirate gets 1 Coin
27 number pirate gets 0 Coin
26 number pirate gets 1 Coin
25 number pirate gets 0 Coin
24 number pirate gets 1 Coin
23 number pirate gets 0 Coin
22 number pirate gets 1 Coin
21 number pirate gets 0 Coin
20 number pirate gets 1 Coin
19 number pirate gets 0 Coin
18 number pirate gets 1 Coin
17 number pirate gets 0 Coin
16 number pirate gets 1 Coin
15 number pirate gets 0 Coin
14 number pirate gets 1 Coin
13 number pirate gets 0 Coin
12 number pirate gets 1 Coin
11 number pirate gets 0 Coin
10 number pirate gets 1 Coin
9 number pirate gets 0 Coin
8 number pirate gets 1 Coin
7 number pirate gets 0 Coin
6 number pirate gets 1 Coin
5 number pirate gets 0 Coin
4 number pirate gets 1 Coin
3 number pirate gets 0 Coin
2 number pirate gets 1 Coin
1 number pirate gets 0 Coin
