A combinatorics problem on connecting the cities

  • Thread starter Vineeth T
  • Start date
  • #1
31
0
Fifteen cities are planned to be connected in such a way that each city has precisely one road leading to each of five other cities.How many such roads are to be constructed?

This question was asked in a talent test conducted in our school.
 
Last edited:

Answers and Replies

  • #2
403
1
5*15=75 which is not an even number. So it is impossible.
 
  • #3
31
0
5*15=75 which is not an even number. So it is impossible.
Hi! Rogerio
Can you explain me clearly why is it impossible?
 
  • #4
35,509
11,965
Assuming that a road always leads from one city to another city, each city has 5 road ends connected to this city, so we have a total of exactly 75 road ends.
Every road has 2 ends - the total number of road ends has to be even. 75 is not even.
 

Related Threads on A combinatorics problem on connecting the cities

  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
4
Views
896
  • Last Post
Replies
6
Views
3K
  • Last Post
Replies
11
Views
802
  • Last Post
Replies
8
Views
2K
Replies
8
Views
3K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
3
Views
6K
  • Last Post
Replies
2
Views
3K
Top