Minimum number of links he would need to cut?

In summary, the son of a wealthy bullion merchant has to rent a place with a shop and apartment. His landlady requests a weekly payment of one link of his 123-link gold chain, with the number of links increasing each week. To rent the place for 123 weeks, the son would need to cut a minimum of 4 links from his gold chain.
  • #1
19,412
9,962
The son of a rich bullion merchant left home on the death of his father. All he had with him was a gold chain that consisted of 123 links. He rented a place in the city center with a shop at the lower level and an apartment at the upper level. He was required to pay every week one link of the gold chain as rent for the place.

The landlady told him that she wanted one link of the gold chain at the end of one week, two gold links at the end of two weeks, three gold links at the end of three weeks and so on.

The son realized that he had to cut the links of the gold chain to pay the weekly rent. If the son wished to rent the place for 123 weeks, what would be the minimum number of links he would need to cut?
 
Physics news on Phys.org
  • #2
4 Links
 
  • #3
Matt earns a point.
 

1. What is the minimum number of links that need to be cut to separate a connected graph into two disconnected graphs?

The minimum number of links that need to be cut to separate a connected graph into two disconnected graphs is equal to the number of edges in the smallest cut set.

2. How do you determine the minimum number of links to cut in a connected graph?

The minimum number of links to cut in a connected graph can be determined using various algorithms, such as the max-flow min-cut theorem or the Karger-Stein algorithm.

3. Can the minimum number of links to cut vary depending on the size or complexity of the graph?

Yes, the minimum number of links to cut can vary depending on the size and complexity of the graph. In general, larger and more complex graphs will require a larger number of links to be cut to separate them into two disconnected graphs.

4. Is the minimum number of links to cut always unique for a given connected graph?

No, the minimum number of links to cut may not always be unique for a given connected graph. In some cases, there may be multiple ways to cut the graph and achieve the same result of two disconnected graphs.

5. How does the minimum number of links to cut relate to the connectivity of a graph?

The minimum number of links to cut is directly related to the connectivity of a graph. A graph with high connectivity will typically require a larger number of links to be cut to disconnect it, while a graph with low connectivity may only require a few links to be cut.

Similar threads

  • General Discussion
Replies
13
Views
4K
Replies
12
Views
870
  • General Discussion
Replies
11
Views
1K
Replies
8
Views
2K
  • General Discussion
Replies
10
Views
4K
  • General Discussion
Replies
2
Views
1K
  • General Discussion
Replies
28
Views
7K
  • General Discussion
Replies
6
Views
804
  • General Discussion
Replies
20
Views
3K
Replies
2
Views
1K
Back
Top