Well,

I am back from my short break, however, will go for another short break in a week’s time. But meanwhile lets get back to business.

Title of this post may be a bit misleading as I am not referring to ring as they appear in number theory. Deepanjan gave me this puzzle yesterday and I could come up with a very simple solution where as his solution was a bit involved.

**Problem : **Integers from 1 to n are arranged in a circle in some random permutation. Prove that there exist a set of k consecutiveĀ integers on the circle sum of which would be at least k(n+1)/2.

**Solution : **Set of k consecutive integers can be uniquely specified by the start position and the direction ( clockwise, or counter clockwise ). We will call it a k-box. Because they are arranged in a circular fashion there are n positions. We will assume clockwise direction. For each of these n position compute sum of its corresponding k-boxes. Sum of all these k-boxes would be kn(n+1)/2. The reason is that . and each number will appear in k different k-boxes.

So on average, each k-box makes a contribution of k(n+1)/2. So there exist at least one k-box which makes contribution of at least k(n+1)/2.

Or, in other words. If none of the k-box can make contribution of at least k(n+1)/2 then the total of all k-boxes would be strictly less than kn(n+1)/2 which is a contradiction.

— Saurabh Joshi

### Like this:

Like Loading...

*Related*

Tags: math, theorem

This entry was posted on July 2, 2008 at 10:46 am and is filed under math, theorem. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply