Prove that if there is 44$ bill and 10 people to split the bill, then at least two people paid the same amount of money.

Question

I'm learning how to do proofs and now trying to prove the following statement:

Suppose you are having dinner with nine friends and want to split the bill, which is $44. Everyone pays in dollar bills. Prove that at least two people in your group paid the same amount of money.

Unfortunately, I have no idea how to proceed. I though about cardinalities of a set which consists of people ($ \vert F\vert $) and a cardinality of a set consisting of payments ($ \vert P \vert $) that people did, so that $ \vert P \vert < \vert F\vert $, because at least two people pay the same amount of money. But it doesn't seem to help and I have no idea what else to try.

I'd be grateful for any hints you can provide.

Answer 1

Suppose no 2 paid the same; let the amounts paid be $p_1,p_2,..,p_{10}$ in increasing order. Then $p_1\ge 0,\; p_2\ge 1+p_1\ge 1,\; p_3\ge 1+p_2\ge 2,$ etc. So $p_1+p_2+p_3+...+p_{10}\ge 0+1+2+...+9=45.$ But the total is $44.$