Prove or Counterexample problem

[FelixHelix]

Hi - My first post here and was looking for some help with this problem.
Not sure where to start so hope some pointers would get me going/thinking!

Q:
Suppose that there is a party with n ≥ 2 people and that each person gives presents to one or more people at the party (but no more than one present to any single person). Are the following true or false? Give a proof or a counterexample as appropriate:

a) There are at least two people at the party who receive the same number of presents.
b) There are at least two people at the party who give the same number of presents.
c) It is not possible to have a party where everybody gives more presents than they receive.

Thanks for the advice in advance,

Felix

 

[chiro]

Hey FelixHelix and welcome to the forums.

Usually on these forums we ask that the poster show any work as well as the thought process that they are having. We don't just do questions outright for people, but we will give hints to people and do our best to move people forward when they are stuck.

If you don't have anything worked out on paper (in terms of mathematics) it might help us to tell us what thoughts and ideas you have on trying to show whether a particular question is true or false.

 

[FelixHelix]

I've spent sometime looking at these and think I can show that statement a) is false, b) is true and c) is true but not sure how to explain. However I'm unsure of the mathematics to show this. Any help would be great.

Here's what I've done:

a) There are at least two people at the party who receive the same number of presents.

A counterexample of this is if 3 guests are at the party P1, P2 & P3. If P1 gives P2 a gift, and P2 gives P1 a gift. When P3 gives P2 a gift then they have 1, 2 & 0 gifts each respectively - Which counters the statement.

b) There are at least two people at the party who give the same number of presents.

There are n guests at the party. The number of gifts given is >= 1 and <= n-1. so at least two guests must give the same number gifts.

c) It is not possible to have a party where everybody gives more presents than they receive.

if I try with a few examples I can never make everyone give more than they receive... Not sure how to explain it though.

Thanks in advance of any advice.

Felix

 

[Math-ew]

Felix, have you made any progress?

 

[FelixHelix]

Only what I wrote in my last post... Any ideas?

 

[FelixHelix]

Yeah, u can receive between [0,n-1] gifts and give between [1,n-1] gifts. Not sure how to prove the statement though...

 

[willem2]

c) seems really obvious. If you really want to prove it, you can prove it for arbitrary n, and then use induction on the number of presents given. (what happens to the number of presents given, and received if you add one more present?)

 

[FelixHelix]

Well it increases by one. But I don't see how you'd use induction as the every guest choses the number of gifts they give upto a limit

 

[Math-ew]

I think a better strategy might be by contradiction. Assume the statement is false, and draw out a scenario where every person has given more gifts than they received, and show it to be impossible in the end.

 

[willem2]

Well it increases by one. But I don't see how you'd use induction as the every guest choses the number of gifts they give upto a limit

If it's true for an unlimited number of presents, It will be true for a limitied number as well. You don't need any of the conditions given to prove that the number of received presents is equal to the number of given presents, so the base case for induction can be no presents given or received.