Suppose for a set $S$ of 7 people, $f(s)=$ the birthday date of the person for each person in $S$. For example if their birthday is May 17th then $f(s)=17$. Now for every subset $T \subset S$ let $g(T)$ be the sum of all $f(s)$ with $s \in T$. Is the function $g$ ever an injection? In other words, prove whether or not two distinct subsets of $S$ will always have the same $g$ value.
This was a bonus problem on the final exam of an introductory proofs class I took last year, and it has been bothering me ever since then because no solution was ever posted. I think this would be reasonably simple to check with a computer using brute force, but that was besides the point of the class.
A similar problem where $S$ is instead a set of 8 people is trivial to prove using the Pigeonhole Principle. In that case, the codomain of $g$ will have $8 \cdot 31 =248$ elements while $\mathcal{P}(S)$ will have $2^8 = 256$ elements, so therefore $g$ is not injective.
Clearly this same strategy does not apply to a group of 7 people, but is there another way of approaching this problem in order to prove whether or not $g$ is injective?
My first thought was that even though $2^7 = 128 < 217=31 \cdot{7}$, there could maybe be some way to analytically reduce the 217 possible sums until there are less than 128? It seems intuitively like there should exist an $S$ where $g$ is injective, but without using brute force I couldn't produce one.
Well you can't have two people with the same birthday. That reduces the sum at the top end to $25+26+27+28+29+30+31=196$ and this accounts for one sum.
The sums of six dates are at most $26+27+28+29+30+31=171$ and there are just seven sums which miss out one birthday.
The sums of five dates are likewise at most $27+28+29+30+31=145$ and there are $21$ sums which miss out two birthdays. The least of these must be at most $145-20=125$.
We have accounted here for $1+7+21=29$ sums, and I think you will find it easy to show that in the end there is not enough space for all the sums to be different. I'll leave you to complete the process, which is simple arithmetic.
The reason for this is that because you need big numbers to reach the highest attainable sums, the highest sums are relatively sparse. And if you reduce the size of the numbers to avoid sparsity, you reduce the highest total and therefore the space for making different sums.
I had some thoughts about a potentially neater method, and maybe someone else will share an insight I've missed.