
Algebra PreAlgebra and Basic Algebra Math Forum 
 LinkBack  Thread Tools  Display Modes 
September 10th, 2009, 11:44 PM  #1 
Newbie Joined: Aug 2009 Posts: 3 Thanks: 0  the pigeon hole principle
it is known that among any group of three students in a class two of them are friends. the total number of students is 25. prove that there is a student who has at least 12 friends thnx a gazillion jc.xd PS: can you show the entire process thnx 
September 11th, 2009, 12:49 AM  #2 
Senior Member Joined: Jan 2009 From: Japan Posts: 192 Thanks: 0  Re: the pigeon hole principle
Choose 2 people from the group who are not friends, call them A and B. Then there are 23 people left to be chosen. Each person remaining must be friends with either A or B or both. Then: friends of A + friends of B >= 23. Apply the pigeonhole principle. (If all people are friends, you have your answer there, of course.) 

Tags 
hole, pigeon, principle 
Search tags for this page 
it is known that among any group of three students in a class, two of them are friends. the total number of students is 25. prove that there is a student who has at least 12 friends.,it is known that among any group of three students in a class,maths pigeonhole principle
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Modular Arithmetic & Pigeon Hole  Jet1045  Number Theory  14  January 24th, 2013 05:21 AM 
Prove by the pigeon hole principle  stranger  Applied Math  7  February 2nd, 2012 04:43 PM 
Pigeon Hole problem  numbercruncher  Elementary Math  8  January 25th, 2012 07:36 PM 
Pigeon Hole Principle  guru123  Algebra  3  October 6th, 2011 07:40 AM 
pigeon hole problem  frankyfol  Algebra  0  July 3rd, 2009 01:14 AM 