×

# 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

Sort by:

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. · 3 years, 9 months ago

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

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

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 :) · 3 years, 9 months ago

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

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

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 · 3 years, 9 months ago