A combinatorics problem on connecting the cities

  • Context: High School 
  • Thread starter Thread starter Vineeth T
  • Start date Start date
  • Tags Tags
    Combinatorics
Click For Summary

Discussion Overview

The discussion revolves around a combinatorial problem involving the connection of fifteen cities, where each city is required to have exactly one road leading to five other cities. Participants explore the implications of this requirement on the total number of roads needed.

Discussion Character

  • Debate/contested

Main Points Raised

  • One participant calculates the total number of road ends as 5*15=75, suggesting that this number being odd implies that the construction of such roads is impossible.
  • Another participant reiterates the calculation and seeks clarification on why the odd total indicates impossibility.
  • A further explanation is provided, stating that since each road connects two cities, the total number of road ends must be even, and thus having 75 road ends presents a contradiction.

Areas of Agreement / Disagreement

Participants generally agree on the calculation leading to the conclusion that the total number of road ends is odd, but the discussion remains unresolved regarding the implications of this finding.

Contextual Notes

The discussion does not address potential assumptions about the nature of the roads or the connections between cities, nor does it explore alternative interpretations of the problem.

Vineeth T
Messages
31
Reaction score
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:
Physics news on Phys.org
5*15=75 which is not an even number. So it is impossible.
 
Rogerio said:
5*15=75 which is not an even number. So it is impossible.
Hi! Rogerio
Can you explain me clearly why is it impossible?
 
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.
 

Similar threads

  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 19 ·
Replies
19
Views
4K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 3 ·
Replies
3
Views
2K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 5 ·
Replies
5
Views
2K
  • · Replies 2 ·
Replies
2
Views
1K
  • · Replies 22 ·
Replies
22
Views
3K
  • · Replies 9 ·
Replies
9
Views
2K
  • · Replies 5 ·
Replies
5
Views
3K