Let S be a set of six positive integers who maximum is at most 14.

Question

Let $\mathcal S$ be a set of six positive integers who maximum is at most 14. Show that the sums of the elements in all the nonempty subsets of $\mathcal S$ cannot all be distinct

For each non-empty subset, $\mathcal A$ of $\mathcal S$ the sum of the elements in $\mathcal A$ denoted as $S_\mathcal A$ satisfies $$1\leq S_\mathcal A \leq 9 + 10 + \cdots + 14 = 69$$ and there are $2^6−1=63$ non-empty subsets.

How do you know that the sums start from $9$ and goes to $14$? $(9+10+...+14= 69)$. Why can't it start from $1$?

Answer 1

Assume that $\max S=12.$ Then the sum of the elements of any subset os $S$ is bounded from above by $$12+11+10+9+8+7=57.$$ Since there are $63$ non-empty subsets of $S$ there are two subsets which the sum of elements is the same.

Assume that $\max S=13.$ Then the sum of the elements os $S$ is bounded by $$13+12+11+10+9+8=63.$$ Since $13+8=12+9=11+10$ we get that if $S=\{8,9,10,11,12,13\}$ there are subsets of $S$ $(\{8,13\},\{9,12\},\{10,11\})$ whose elements sum the same. In other case $\max S=13$ and the sum of the elements of $S$ is $<63.$ Repeating the argument with the existenc of $63$ non-empty subsets we are done.

Assume $\max S=14.$ If $S=\{9,10,11,12,13,14\}$ we are done (because $10+13=11+12$). So the maximum of the sum is $68.$ Assume the worst scenario: $\{12,13,14\}\subset S.$ Then $11\notin S.$ (In other case $11+14=12+13$.) It could be $\{10,12,13,14\}\subset S.$ So $9\notin S$ because $13+9=10+12.$ For the same reason $8\notin S$ because $8+14=10+12.$ So the sum of the elements of $S$ is at most $$14+13+12+10+7+6=61.$$

Now assume $13\notin S.$ The the sum of the elements of $S$ is $64.$ The worst scnecario here is $\{10,11,12,14\}\subset S.$ For the same reason as above it is $9\notin S$ (in other case $9+12=10+11$.) So the sum of elements of $S$ is at most $7+8+10+11+12+14=64.$ But if $S=\{7,8,10,11,12,14\}$ then $7+11=10+8.$ So $7\notin S.$ In a similar way $S\ne \{6,8,10,11,12,14\}.$ So the sum of the elements of $S$ is $<63.$

Since the sum of the numbers of $s$ is smaller than the number of non-emptysets "Pingeonhole principle again".

Answer 2

Suppose $S$ contains two equal elements. Then the subsets of $S$ comprising only these elements have equal sums, so the sums are not all distinct.

Now suppose $S$ does not contain two equal elements, i.e. the elements of $S$ are all distinct.

Let $x$ be the smallest element of $S$.

Then the smallest possible value of $S_A$ is $x$.

And the largest possible value of $S_A$ is $x+10+11+12+13+14=x+60$.

Since $x<S_A<x+60$, there are $61$ possible values of $S_A$.

And since there are $2^6-1=63$ non-empty subsets, these cannot all have distinct sums since there are only $61$ possible values available for the sum.

Answer 3

import Java.util.Scanner; public static void main(String [] args){ Scanner userInput=new Scanner(System.in); int numberOfPigeons=0; int numberOfPigeonholes=0; System.out.println("Please enter the number of pigeons: "); numberOfPigeons=userInput.nextInt(); System.out.println("Please enter the number of pigeonholes: ); numberOfPigeonholes=userInput.nextInt(); if(checkValidity(numberOfPigeons,numberOfPigeonholes)==true) System.out.println("The statement is correct"); else System.err.println("The statement is not correct");

} public static boolean checkValidity(int numberOfPigeons,int numberOfPigeonholes){ if(numberOfPigeons<=numberOfPigeonholes){ return false; } else return true; }