Skip to main content

King's Maths School

Challenge 475: Party Picker

How many mathematicians can I choose at this party?

I am friends with 100 mathematicians. Unfortunately many of them are not friends - in fact, each of the mathematicians has exactly 2 enemies among the 100.

Two important points:

(1) A mathematician cannot be their own enemy.

(2) Being an enemy is symmetric - if A is B's enemy, then B is also A's enemy.

I am throwing a party, and I decide to invite as many of the mathematicians as possible without inviting any pairs of enemies.

(a) What is the largest number of mathematicians I could invite? 

(b) What is the smallest number of mathematicians I could invite?

(c) Rigorously justify your answers to (a) and (b)!

Submit your solution

Please do send in your solution to this problem to weeklymaths@kcl.ac.uk You can scan or photograph your written work, or type your solutions. If this is your first weekly maths challenge solution, please include your year group and the name of the school you attend. We'll be happy to provide feedback on your solution, assuming that you are in year 11 or below. If you are older than this, we hope you enjoy trying the problems and reviewing your solutions against those we publish on the website.