a. Show that in any set of n integers, there is a subset whose sum is divisible by n.
b. Show that for any integer n, there is an integer whos digits (in decimal representation) consist of only 0 and 1.
I don't think the first can be proved. However, in a set of 2n-1 integers, it can be proved that there is a subset whose sum is divisible by n.
2. This makes no sense to me. Something is missing.
a. To show that in any set of n integers, there is a subset whose sum is divisible by n, we can use the Pigeonhole Principle.
If n + 1 objects are placed into n pigeonholes, then there must be at least one pigeonhole containing at least two objects.
Now let's consider a set of n integers. We can assign each integer a residue class modulo n. In other words, we can divide each integer by n and look at the remainder. There are only n possible remainders: 0, 1, 2, ..., n-1.
If any one of these residues occurs more than once, we can take the integers corresponding to those residues and their sum will be divisible by n. This can be easily seen, as the difference between the sums of these integers will be a multiple of n.
If none of the residues occur more than once, then there are n distinct residues among the integers. In this case, we can consider the sum of all the integers. If this sum is divisible by n, we are done. Otherwise, we can consider the remainders when this sum is divided by n. Since there are only n possible remainders, and n distinct residues among the integers, there must exist at least one remainder which is equal to the sum of some subset of the integers. This subset will have a sum divisible by n.
b. To show that for any integer n, there is an integer whose digits (in decimal representation) consist only of 0 and 1, we can construct such an integer.
Consider the number formed by writing 1 followed by n zeros: 10^n.
If we divide this number by 9 (10^n / 9), the division will result in an integer value, since 10^n is divisible by 9. This is because 1 followed by n zeros is a power of 10, and 10^n is always divisible by 9.
Now, let's consider the decimal representation of the resulting integer, which is 111...1 (with n ones). We can see that this integer consists only of the digits 0 and 1.
Therefore, for any integer n, we have shown that there exists an integer whose digits consist only of 0 and 1, specifically by dividing 10^n by 9.