Two teams with identical payroll
Asked at Optiver, Jane Street
A firm has 10 employees. Their salaries are distinct whole numbers (say, in thousands of dollars), and every salary is at most 100. You'd like to find two different groups of employees whose salaries add up to the exact same total.
Prove that such a pair of groups always exists, for any set of ten distinct salaries under the cap. Then sharpen it: show you can even find two groups with no employees in common.
Your answer
This one is open-ended. Work it through, then check your reasoning against the full solution.