1
$\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
$\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$
  • $\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$ – hlyates Nov 13 '15 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 '15 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 '15 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 '15 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$ – hlyates Nov 13 '15 at 19: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.