My Math Forum  

Go Back   My Math Forum > High School Math Forum > Algebra

Algebra Pre-Algebra and Basic Algebra Math Forum

LinkBack Thread Tools Display Modes
September 10th, 2009, 11:44 PM   #1
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

PS: can you show the entire process thnx
jc.xd is offline  
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.)
cmusick is offline  

  My Math Forum > High School Math Forum > Algebra

hole, pigeon, principle

Search tags for this page
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

Copyright © 2019 My Math Forum. All rights reserved.