Waste less time on Facebook — follow Brilliant.
×

Towers problem

I was asked this question 2 years ago and I forgot how to to solve it.

There are N towers. The towers target each other via lasers, and a tower can choose how many it will target. Prove that at least 2 towers are targeting the same amount of towers.

Note by Jayce Cesista
3 years, 9 months ago

No vote yet
3 votes

Comments

Sort by:

Top Newest

A tower can target at most \( n-1 \) towers because it cannot target itself.However there are \( n \) towers so there are at least 2 towers targeting the same amount of towers. Tan Li Xuan · 3 years, 9 months ago

Log in to reply

What if N=1? Daniel Leong · 3 years, 9 months ago

Log in to reply

ah, thanks for the answers! Jayce Cesista · 3 years, 9 months ago

Log in to reply

A tower must target at least one other tower hence let the \(1\)st tower attack \(1\) tower, the\(2\)nd \(2\)towers and so on. ( If they don't then one \(2\) of them attack the same number of towers.) Continuing like this we get that the \(n\)th tower attacks \(n + 1\) towers which is a contradiction since there are only \(n\) towers. Hence \(2\) towers must attack the same number of towers. This is application of the Pigeon Hole Principle. You can read about it in the Techniques tab below the page :) Yash Talekar · 3 years, 9 months ago

Log in to reply

@Yash Talekar Nvm I made a mistake the N th tower attacks only n towers by this logic. Yash Talekar · 3 years, 9 months ago

Log in to reply

@Yash Talekar Further the contradiction proof still holds though as a tower cannot target itself. Yash Talekar · 3 years, 9 months ago

Log in to reply

Hint 1: Pigeon-hole principle(PHP)

Hint 2: There are n pigeons

Hint 3: Can you ever have a tower targeting 0 and tower targeting n-1 at the same time?

Hint 4: There are n-1 holes

Hint 5: PHP your way through it Matthew Fan · 3 years, 9 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...