Solution: Splitting the Pirate Loot

Solution

Let’s denote $v_1 + v_2 + ··· + v_i$ as sum$(i)$. Splitting the set of $n$ items evenly into three parts is possible only if their total value is divisible by three, i.e., sum$(n) = 3V$, where $V$ is an integer. Then, we need to partition $n$ numbers into three parts where the sum of numbers in each part is equal to $V$. Instead of partitioning all $n$ items, let’s try to solve a smaller problem of partitioning the first $i$ items into parts of value $s_1, s_2,$ and $sum(i) − s_1 − s_2$. We define $split(i,s_1,s_2) =$ true if such partition is possible (and false, otherwise) and note that the pirates can fairly split the loot only if $split(n,V,V)=$ true.

Stop and think:

Given the first five items

$$\boxed{3}\boxed{6}\boxed{4}\boxed{1}\boxed{9}$$

$split(5,4,13) =$ true.

Find all other values $split(5,s1,s2)$ equal to true.

Imagine that you have already constructed the binary two-dimensional array $split(i−1,s_1,s_2)$ ...