Chain fragments -> Circular chain
Problem: There exists 4 chain fragments each with 3 links. Cost of opening a link is Copen and cost of closing a link is Cclose.
Objective is to combine these fragments to form a single circular chain with 12 links. Find a way to satisfy the objective while incurring minimum cost. Argue that the
solution is the best possible.
Observations
- Each link that is opened must be closed. Hence for for every opening cost there will also be the corresponding closing cost.
- Fragment with one link can connect with two other fragments for the least cost (just Copen+Cclose).
Solutions
- It is not possible to connect all fragments by just one or two link open-close operation. Here are the arguments:
- Using one link open-close operation, maximum fragments that can be connected to form a circle are:
- one fragment: open the link at one of the ends and close it over the link at the other end of the fragment.
- two fragments: one fragment has only one link, open this link and use it join the links at both ends of the other fragment.
- Using two link open-close operation, maximum fragments that can be connected to form a circle are:
- two fragments: open two links (from the same fragment or one from each fragment) at opposite ends and close it over the last link in the other fragment
- three fragments: one fragment has only two links, open these links and use them to join the other two fragments to form a circle.
- If any three fragments are arranged to
form a circle, then there will be 3 gaps. Since 3 gaps need to be closed, minimum cost incurred will be 3* (Copen+Cclose). It can be
achieved thus:
- 1) Open a link at one end of each fragment and closing it over a link in the neighbouring fragment.
- 2) Repeat this till there are no open ends.
But this does not result in target goal. Employing "Observation 2" requires the unused fourth fragmented to be split into individual links and
using them to close the gaps in the remaining three fragments. Thus the total cost will still be 3*(Copen+Cclose) and all links from
the four fragments are used to form the single circular chain.
- If all the four fragments are arranged to
form a circle, then there will be 4 gaps. Since 4 gaps need to be closed, minimum cost incurred will be 4* (Copen+Cclose). It can be
achieved thus:
- 1) Open a link at one end of each fragment and closing it over a link in the neighbouring fragment.
- 2) Repeat this till there are no open ends.
But this approach does not employ "Observation 2".
Solution 2 is the best possible. Every other operation sequence is costlier or does not lead to target goal.
Interesting Observations
- Related to the above problem is it's inverse: given a circular chain containing 12 links, and given the cost of opening and closing: Copen and Cclose, find a way to
break the chain into 4 fragments (each containing equal number of links) incurring least cost.
Solution: Cut every fourth link. Join the three individual links. The least cost is 3 * (Copen+Cclose)
- The chain fragmenting problem can be generalized: Given n fragments each having (n-1) links. The cost of opening a link is Copen. The cost of closing a link is Cclose. Find the least
inexpensive way to combine the fragments into a circular chain with n*(n-1) links.
Solution: The least inexpensive way to combine the fragments is to open all links in one of the fragments and use those open links
to close the n-1 gaps between the remaining n-1 fragments. The cost would be (n-1)*(Copen+Cclose). The correctness can be argued like
this:
Argument: Let there be another way of reaching the goal [single circular chain with n*(n-1) links] incurring the cost of x*(Copen+Cclose) with x < (n-1). Then the number of
open-close link operations involved in this approach is x (< n-1). Using x open-close link operations, the total number of fragments that can be connected to form a circle are:
- x fragments (each with n-1 links): open the link from one end of each fragment and connect it to the link on the next fragment
- x+1 fragments (each with n-1 links): open the links from one fragment and use those links to close the gaps between the remaining x-1 fragments
But the final circular chain will have x* (n-1) links or (x+1)*(n-1) links. The resulting link count is less than the target [n*(n-1)]. Hence the assumption that it is possible
to reach the goal incurring x open-close operation cost is incorrect.