Count the Mega Cities.

Probability Level 3

The state of Maharashtra has 20 20 cities and some pairs of cities are connected by roads. A city is called a "Mega city" if it is directly connected to every city in Maharashtra. If altogether there are 100 100 roads in the state of Maharashtra, what is the largest possible number of "Mega cities"?

8 9 7 2 4 3 5 6

View wiki
Satyen Nabar by Satyen Nabar , 48, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Satyen Nabar
Feb 11, 2015

If there are M M Megacities, there are ( M 2 ) \binom{M}{2} roads that connect the cities to each other. Also each Megacity is connected to the other 20 − M 20 -M cities. So we have ( M 2 ) + M ( 20 − M ) \binom{M}{2} + M(20-M) distinct roads.

Now we have, 100 ≥ ( M 2 ) + M ( 20 − M ) 100 \geq \binom{M}{2} + M(20-M)

200 ≥ M ( 39 − M ) 200 \geq M(39-M)

The largest M M for which this works is 6 6 .

2 Helpful 0 Interesting 0 Brilliant 0 Confused

If there are M M Megacities, there are ( M 2 ) \binom{M}{2} roads that connect the cities to each other. Also each Megacity is connected to the other 20 − M 20 -M cities. So we have ( M 2 ) + M ( 20 − M ) \binom{M}{2} + M(20-M) distinct roads.

Now we have, 100 ≥ ( M 2 ) + M ( 20 − M ) 100 \geq \binom{M}{2} + M(20-M)

200 ≥ M ( 39 − M ) 200 \geq M(39-M)

The largest M M for which this works is 6 6 .

Sir, please copy this and repost your solution . Earlier it wasn't looking as good , sorry if I was intrusive .

⌣ ¨ \ddot\smile

A Former Brilliant Member - 6 years, 4 months ago

Log in to reply

Tx Azhaghu. Was short on time :)

Satyen Nabar - 6 years, 4 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...