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.

No vote yet

3 votes

×

Problem Loading...

Note Loading...

Set Loading...

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

TopNewestA 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.

Log in to reply

What if N=1?

Log in to reply

ah, thanks for the answers!

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 :)

Log in to reply

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

Log in to reply

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

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

Log in to reply