2
$\begingroup$

One hundred integers are written around a circle, and it is known that their sum is $1$. We will call a subset of several successive numbers a "chain". Find the number of chains whose members have a positive sum.

I had no idea how to approach the problem, so I considered some small sets.

Consider a circle with four elements $2, -1, 1, -1$ (arranged clockwise) at positions $0, 1, 2, 3$ respectively. Clearly, this has four chains: $[0, 1], [0, 1, 2]$ (moving clockwise) and $[0, 3], [0, 3, 2]$ (moving anti-clockwise).

Now consider another circle with four elements $2, -2, -1, 2$ (arranged clockwise) at positions $0, 1, 2, 3$ respectively. This has three chains $[3, 0, 1], [3, 0]$ (moving clockwise) and $[0, 3, 2]$ (moving anticlockwise).

I don't understand this. Won't the answer be ambiguous?

$\endgroup$
12
  • 1
    $\begingroup$ One thing that might help is that no matter how you split the circle in half (any collection of 50 and 50 will do), one half will have a positive sum and the other half will not. $\endgroup$ – Cameron Williams Jun 26 '13 at 4:43
  • 1
    $\begingroup$ @CameronWilliams We can do better than that. It doesn't matter how many elements are in either set. $\endgroup$ – Calvin Lin Jun 26 '13 at 4:43
  • $\begingroup$ @CalvinLin you're right. I was just giving OP an idea to break away from the wrong thought processes. $\endgroup$ – Cameron Williams Jun 26 '13 at 4:45
  • 1
    $\begingroup$ You’re undercounting. Your first circle has the following seven chains (I give strings of numbers, not the positions): $2$; $2,-1$; $2,-1,1$; $2,-1,1,-1$; $1$; $1,-1,2$; and $-1,2$. Your second has these seven: $2$; $2,-2,-1,2$; $-1,2$; $-1,2,2$; $2$; $2,2$; and $2,2,-2$. $\endgroup$ – Brian M. Scott Jun 26 '13 at 4:54
  • $\begingroup$ OP, you have to clarify what a chain means. @BrianM.Scott A lot of it depends on what the definition of a chain is. I think that OP considers a singleton to not be a chain. $\endgroup$ – Calvin Lin Jun 26 '13 at 4:55
2
$\begingroup$

Note: The question depends on your definition of a chain. If you take it to not include singletons and the full circle (as suggested by your count), then your answer will be dependent on the values you chose.

Hint: If a chain of integers have a positive sum, then the opposite set of integers have a non-positive sum.

However, the opposite set of integers may not necessarily form a chain. When does it not form a chain? This will explain why you have a discrepancy in your answer.

Hint: There are $n(n-2)$ chains in total, because the full circle is not a chain.


If we include singletons and the full circle as a chain, then the 1st hint still holds (when does the opposite net not form a chain?). There are $n(n-1) + 1$ chains (where the +1 counts the full circle just once), and hence the number of positive chains is $\frac{n(n-1)}{2} + 1$, which agrees with Brian's calculations.

$\endgroup$
2
  • 1
    $\begingroup$ Why do you say that the full circle is not a chain? $\endgroup$ – Cameron Williams Jun 26 '13 at 4:53
  • $\begingroup$ @CameronWilliams This is just based on how OP is counting. I.e. OP never included any full circle, or any singletons. This is why I changed the value. If he changes his definition (esp in light of Brian's comment), I'd update accordingly. $\endgroup$ – Calvin Lin Jun 26 '13 at 4:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.