Numbers on a circle - Minimum sum of consecutive differences
Source: Asked to me by Anuj Jain (MFE Grad Student at Baruch College in New York, EE IITB 2010 Alumnus)
Problem:
Place the numbers 1, 2, ... 9 around a circle in the positions x_1, x_2, ..., x_9 so that the sum of difference between consecutive terms defined by
Sum over | x_{ i+1 } - x_{ i } | for i = 1, 2, ..., 9 is minimized (Note: x_10 is x_1).
Also count the number of such arrangements where the "sum of difference between consecutive terms" is minimum.
Update (December 13, 2011):
Solution: Partial Solution posted by Chiraag Juvekar (IITB EE Fifth year undergraduate, To be McKinsey Business Analyst) in comments! Complete solution posted by Rudradev Basak (IITD CSE Senior Undergraduate) and Gaurav Sinha (chera, IITK 1996 Graduate, Indian Revenue Service) in comments!
Update (June 22, 2014):
Very generic solution posted by Aashay Harlalka (IITB EE 2014, Two Roads Quantitative Analyst) in comments!
Problem:
Place the numbers 1, 2, ... 9 around a circle in the positions x_1, x_2, ..., x_9 so that the sum of difference between consecutive terms defined by
Sum over | x_{ i+1 } - x_{ i } | for i = 1, 2, ..., 9 is minimized (Note: x_10 is x_1).
Also count the number of such arrangements where the "sum of difference between consecutive terms" is minimum.
Update (December 13, 2011):
Solution: Partial Solution posted by Chiraag Juvekar (IITB EE Fifth year undergraduate, To be McKinsey Business Analyst) in comments! Complete solution posted by Rudradev Basak (IITD CSE Senior Undergraduate) and Gaurav Sinha (chera, IITK 1996 Graduate, Indian Revenue Service) in comments!
Update (June 22, 2014):
Very generic solution posted by Aashay Harlalka (IITB EE 2014, Two Roads Quantitative Analyst) in comments!
Minimum is 16.
ReplyDeleteProof:
If we write out the final sum, we see each number appears twice. The sign it appears with can change. If it is greater than both neighbours then it is +ve 2 times, if it is smaller than both neighbors then it is -ve 2 times, else it sums up to 0.
We can show that for every number that contributes 2 positive factors there must be another number that contributes 2 negative factors. (For the 18 comparisons, with reversed orders included total greater = total lessers, thus by a parity argument we can show the above)
Thus we may have k numbers with both neighbors greater and k numbers with both neighbors smaller.
We now prove an additional property that if we arrange both these lists in descending order than the numbers in the first list are greater than their counterparts in the second list.
Consider the largest number in the second list both its neighbors are larger than it. If neither of them are in the first list then their outer neighbors must be larger as well. This cannot go on ad-infinitum. Thus we will get a larger number in the first list. Repeat this with the second largest number taking care to cross out a new number in the first list every time.
Thus we can see that the net sum is going to be 2*(non-negative number)
Optimum is when that non-negative number is 16. That is k=1 and the lists are {9} and {1} respectively.
I think the following works -
ReplyDeleteLet x1 = 1. Let some xi = 9. There are two paths from x1 to xi. The minimal difference along either path must be atleast 8 because you start from 1 and end at 9. So the minimum sum around the circle is 16.
The simplest arrangement that gives this is 1,2,3,...,9. But the above also tells us how to find such arrangements. Keeping x1=1, just pick any subset out of {2,...,8} for the left path, and everything else is forced. So there are 2^7 = 128 such arrangements.
However the numbers are placed, note that we encounter a sum of at least 8 when going from 1 to 9 and another sum of at least 8 when going from 9 to 1. Hence 16 is the least possible sum.
ReplyDeleteAlso to achieve this total sum of 16, we need to have a continuously increasing sequence when going from 1 to 9, and a continuously decreasing sequence when going from 9 to 1 (Sample sequence : 1,3,4,6,9,8,7,5,2).
Each of the 7 numbers {2,3,4,5,6,7,8} has 2 choices (place either in 1 to 9 part or 9 to 1 part). Beyond that there is no more degree of freedom, other than allowing rotations. Hence number of ways is 128*9.
First, note that the "Sum over | x_{ i+1 } - x_{ i } | for i = 1, 2, ..., 9" (hereafter, denoted as S) comprises exactly 18 terms of which:
ReplyDelete(A) exactly nine of them have a +ve sign, and the other nine have a -ve sign
(B) each of the numbers 1,2,...,9 appears exactly twice.
Because we wish to maximize S, we attempt to have as many of the large numbers 9,8,... with a positive sign and as many of the small numbers 1,2,... with a negative sign.
The best possible scenario, of course, would be if 9,9,8,8,7,7,6,6,5 appeared with a positive sign and 1,1,2,2,3,3,4,4,5 appeared with a negative sign. The sum in this case would be 40.
The fact that this is indeed an attainable score S can be verified by construction. For example, 5,1,6,2,7,3,8,4,9 would do.
For the largest possible sum S = 40 to be realizable, no two elements of X = {1,2,3,4} should appear consecutively. Similarly, no two elements of Y = {6,7,8,9} should appear consecutively.
The number of such possible arrangements can be counted as follows:
(i) Firstly, 5 can be placed in any of the 9 places.
(ii) Now, WLOG, x_1 = 5. Then, the remaining eight places can be divided into two groups comprising of alternate elements A and B, giving rise to 5,A,B,A,B,A,B,A,B configuration. One of set X or set Y can be allocated to A, and the other to B. So, 2 possible choices arise.
(iii) Within both A and B, the members of X and Y can be permuted amongst themselves in 4! different ways each.
So, total number of ways is 9*2*4!*4! = 10368.
Remark: The solution is easily generalizable to arbitrary n.
The maximum possible sum will then be 2*[n/2]*([n/2]+1).
The second part needs to be dealt with separately for odd and even n. The total number of ways to achieve this will be
n*2*[n/2]!*[n/2]! if n is odd and
n*((n-2)/2)!*(n/2)! if n is even.
the problem can be thought of as traversing a closed path on a number line covering the points 1,2,3,...,n covering each number exactly once and returning to the starting point.
ReplyDeletewe want to minimize the total length of path. it can be visualized that minimum length is 2(n-1).
assume the path starts at point 1, i.e. x_1=1. now u have to reach point n and return monotonicaly. the number of ways of halting at intermediate points while traversing from 1 to n ,is 2^(n-2). On return from n to 1 , u cover left-out points.
For each path there are n starting points,
so, total number of arrangements
= n * 2^(n-2)
Oops! I read the problem wrongly. I have maximized, instead of minimizing the quantity.
ReplyDelete@Santosh.. A small mistake in your argument.. I am sure you will realise that by reading other comments!
ReplyDelete@Chiraag.. Thanks for the rigorous solution of the first part of the problem..
@Rudradev, @Chera.. Thanks for the correct solution
I am writing solution for general n.
ReplyDeleteAns : 2(n-1)
Solution :
Lemma : Given positive distinct integer a,b,n such that n > max(a,b)
then, |n-a| + |n-b| >= |a-b| +2
Proof : without loss of generality , consider a>b => 2n - 2a >=2 which is true as n>a and a,n are integers.
Let Sk denote sequence of k numbers in circle. (any sequence)
and Sum (Sk) denote Sum over | x_{ i+1 } - x_{ i } | for i = 1 to k
If we insert (K+1)th number in Sk at any place, then sum will be increased at least by 2
Sum (S(k+1)) >= Sum (Sk) + 2 (using above lemma)
This is valid for every sequence.
Since, S2 = 2
So, Sn >= 2(n-1)
Also, the sequence 1,2,3,4...,n has sum 2(n-1)
So, minimum is 2(n-1)
Cheers!
Perfect. Good solution. Thanks
Delete