Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
CSC 240 Homework Assignment 6
due Thursday March 2
Problem 1. Two adventurers are in the business of recovering treasure chests. Each treasure
chest contains some natural number of gold coins. A fair division of an even number of treasure
chests is one in which each adventurer gets the same number of treasure chests and the same total
number of gold coins.
For example, a fair division of four treasure chests C1, C2, C3, C4 containing 3, 1, 2, 2 gold coins,
respectively, could be achieved by giving one adventurer C1, C2 and the other C3, C4. On the other
hand, there is no fair division of four treasure chests C1, C2, C3, C4 containing 0, 1, 51, 100 gold
coins, respectively.
In general, determining whether a fair division exists is an NP -complete problem, but their friend
the computer scientist has devised an algorithm which efficiently solves the problem for instances
in which the number of treasure chests is not too large.
One time the adventurers recovered an odd number (greater than 1) of treasure chests. They
decide to give one of the treasure chests to the computer scientist as a token of appreciation, as
long as the computer scientist can achieve a fair division of the remaining treasure chests.
The computer scientist observed that no matter which treasure chest they were given, a fair
division can be achieved. Use the well-ordering principle to prove that all of the treasure chests
must contain the same number of gold coins.
Problem 2. Let m,n ∈ Z+.
(a) Suppose F is a collection of subsets of N such that the intersection of any m of them is a
subset of {k ∈ N : k ≤ n}. Prove that F is countable.
(b) For any ` ∈ N, let S` be the collection of all subsets of N which have exactly ` elements.
Prove that S` is countable.
(c) Suppose F is a collection of subsets of N such that the intersection of any m of them contains
at most n elements. Prove that F is countable.