2
$\begingroup$

Background

This is not a homework problem, but I am reading through a discrete mathematics book since I am trying to formalize my background in computer science. I came across the following.

Problem

Suppose the integers from $1$ to $n$ are arranged in some order around a circle, and let $k$ be an integer with $1 ≤ k ≤ n$. Show that there must exist a sequence of k adjacent numbers in the arrangement whose sum is at least $$ \frac{k(n+1)}{2} $$

Pseudo proof

Based on the formula of an arithmetic series, let us consider any k such that, at least initially our choice for $k < n$. Thus, we can enumerate through the first $k - 1$ objects and select $n$ to make sure we have $k$ adjacent numbers. In other words, this particular choices gives us $a_1 = 1$ and $a_n = n$ so that we have $$ S_n = \frac{n(a_1 + a_n)}{2} = \frac{k(n+1)}{2}$$.

I contend that we know this is at least the above since I chose all $ k - 1 $ consecutive numbers below $ k $ and the maximum in the set $ n$. I can choose whatever I want, so it stands to reason that larger numbers will be larger than the sum above and thus represents a lower bound. This concludes my pseudo proof.

Issue

Just one. How could I prove this with the pigeonhole principle?

I have some beef with my above logic. First, the chapter in my book is about the pigeonhole principle. Which is easy to understand, but I am not quite sure how to apply that property to solve the above problem. The second is the proof is a little handwavy by appealing to intuition. I think this would suffice on a napkin during cocktails, ahem, but not stand up to rigorous standards.

$\endgroup$

1 Answer 1

1
$\begingroup$

It is actually simple.

Let the arrangement be $a_1,a_2,...,a_n$ where each $a_i$ correspond to the $i$th element in the circle clockwisely.

Consider all the $k$ consecutive elements clockwisely, that is, the set of $(a_1,a_2,...,a_k),(a_2,a_3,...,a_k,a_{k+1}),(a_3,a_4,...,a_{k+2})...(a_{n-k+1},a_{n-k+2},...,a_n)...(a_n,a_1,a_2,...,a_{k-1})$.

There are totally $n$ groups and if we sum them all up, each element is added $k$ times and we get $ka_1+ka_2+...+ka_n=k(a_1+a_2+...+a_n)=k\large{n(n+1)\over2}$.

Hence there exist at least one set of $k$ consecutive number greater or equal to the average: $\large{{k{n(n+1)\over2}}\over n}={k(n+1)\over 2}$.

$\endgroup$
7
  • $\begingroup$ This is an extremely simple and straightforward proof. If I may ask, what made you consider the $q-1$ groups idea? I think it is rather clever you derived $kq + r = kq-k+k +r = (q-1)k + k + r$. Also, it seems the pigeon hole principle is that the remainder group is $k+r$ right? $\endgroup$
    – GeekyOmega
    Nov 13, 2015 at 4:22
  • $\begingroup$ I am sorry but I just realized the proof is actually wrong as I did not consider the case where the $k+r$ element group is the group with large sum, I will delete it temporarily and re-open it if I manage to fix the error, please un-accept the answer for now. $\endgroup$
    – cr001
    Nov 13, 2015 at 5:01
  • $\begingroup$ Sorry for all the viewers, I provided a new answer via editing (as my previous answer was wrong) so the previous comments will not make any sense. And since it is accepted I cannot delete and post a new answer. $\endgroup$
    – cr001
    Nov 13, 2015 at 5:19
  • 1
    $\begingroup$ @hlyates The previous answer was wrong even though you did not realize it neither did I when I posted the answer. The current version should be the correct proof and sorry for all the inconvenience. $\endgroup$
    – cr001
    Nov 13, 2015 at 5:21
  • $\begingroup$ Sorry. I just got on here. I think the proof above makes a lot more sense to me intuitively. Can you please give a brief counter example which invalidated your first proof? Thanks again for your efforts. $\endgroup$
    – GeekyOmega
    Nov 13, 2015 at 19:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .