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
4 years ago

No vote yet
3 votes

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 1

paragraph 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} \)

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 - 4 years ago

Log in to reply

What if N=1?

Daniel Leong - 4 years ago

Log in to reply

ah, thanks for the answers!

Jayce Cesista - 4 years 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 - 4 years ago

Log in to reply

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

Yash Talekar - 4 years ago

Log in to reply

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

Yash Talekar - 4 years 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 - 4 years ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...