Discrete Math Problem

  • #1

Homework Statement



Suppose n > 1 people are positioned in a feld, so that each has a unique nearest neighbour. Suppose further that each person has a ball that is thrown at the nearest neighbour. A survivor is a person that is not hit by a ball. Prove that if n is odd, then there is at least one person surviving.

Homework Equations





The Attempt at a Solution



I try to prove by mathematical induction.
When n = 3
Let P1, P2, P3 be the 3 people and d12, d23, d13 be the distance between P1 and P2, P2 and P3, P1 and P3 respectively
Then I consider the different cases such as d12 < d23 and d13 > d12........etc
Under each situation, I can successfully prove that there is one person surviving.

After that, I assume the statement is true for n = 2k + 1
However, I have no idea of how to continue the proof
 

Answers and Replies

  • #2
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
4,551
586
If there are 2k+1 people, it might help to consider a subset of 2k-1 of them and use your inductive hypothesis
 

Related Threads on Discrete Math Problem

  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
2
Views
964
Replies
7
Views
5K
Replies
2
Views
2K
  • Last Post
Replies
4
Views
795
Replies
4
Views
1K
  • Last Post
Replies
2
Views
1K
Top