# 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
4 years, 8 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

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.

- 4 years, 8 months ago

What if N=1?

- 4 years, 8 months ago

- 4 years, 8 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 :)

- 4 years, 8 months ago

Nvm I made a mistake the N th tower attacks only n towers by this logic.

- 4 years, 8 months ago

Further the contradiction proof still holds though as a tower cannot target itself.

- 4 years, 8 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

- 4 years, 8 months ago