Imo 2009 q6

The International Mathematical Olympiad (IMO) consists of a set of six problems, to be solved in two sessions of four and a half hours each. Traditionally, the last problem (Problem 6) is significantly harder than the others. Problem 6 of the 2009 IMO, which was given out on July 16, reads as follows:

Problem 6. Let [math]\displaystyle{ a_1, a_2, \ldots, a_n }[/math] be distinct positive integers and let M be a set of [math]\displaystyle{ n-1 }[/math] positive integers not containing [math]\displaystyle{ s = a_1 +a_2 +\ldots+a_n }[/math]. A grasshopper is to jump along the real axis, starting at the point 0 and making n jumps to the right with lengths [math]\displaystyle{ a_1, a_2, \ldots , a_n }[/math] in some order. Prove that the order can be chosen in such a way that the grasshopper never lands on any point in M.

A collaborative effort to study this problem was formed here, and continued here. Some analysis of the effort is contained here.

This page is a repository for any text related to this project, including but not limited to proofs of this problem. (One is also welcome to place here open problems and questions, conjectures, and anything else of relevance to the problem.)

Notation

Elements of M will be referred to as "landmines".

We say that an integer m can be safely reached in k steps if there exist distinct [math]\displaystyle{ b_1,\ldots,b_k \in \{a_1,\ldots,a_n\} }[/math] such that [math]\displaystyle{ m = b_1+\ldots+b_k }[/math] and if none of the partial sums [math]\displaystyle{ b_1+\ldots+b_i }[/math] for [math]\displaystyle{ 1 \leq i \leq k }[/math] is a landmine. Thus, our objective is to show that one can safely reach [math]\displaystyle{ a_1+\ldots+a_n }[/math] in n steps.

In proof 2 I have used 'mines'. I refer to the possibilities for the grasshopper as leaps, and to the actual components of a path through the minefield as jumps. So the longest leap can be the first or second or third jump (etc). I refer to an unmined space as a 'clear space'. Please feel free to suggest better terms/edit for consistency.

Proof #1

We induct on n, assuming that [math]\displaystyle{ n \geq 3 }[/math] and that the claim has already been proven for smaller n. We order [math]\displaystyle{ a_1 \lt a_2 \lt \ldots \lt a_n }[/math].

Observe that if one can pass k or more mines safely in k steps for some [math]\displaystyle{ k \geq 1 }[/math], then we are done by induction hypothesis (removing the steps [math]\displaystyle{ b_1,\ldots,b_k }[/math] from [math]\displaystyle{ a_1,\ldots,a_n }[/math], and shifting the remaining mines leftwards by [math]\displaystyle{ b_1+\ldots+b_k }[/math], reducing n by k, and adding dummy mines if necessary. Thus we may assume that it is not possible to pass k or more mines safely in k steps for any [math]\displaystyle{ k \geq 1 }[/math]. We will refer to this assumption as Assumption A.

For each [math]\displaystyle{ 1 \leq j \leq n }[/math], let [math]\displaystyle{ S_j }[/math] denote the set of integers formed by summing j distinct elements from [math]\displaystyle{ a_1,\ldots,a_n }[/math]. Thus for instance [math]\displaystyle{ S_1 = \{a_1,\ldots,a_n\} }[/math], [math]\displaystyle{ S_2 = \{a_i+a_{i'}: 1 \leq i \lt i' \leq n }[/math], and [math]\displaystyle{ S_n = \{a_1+\ldots+a_n\} }[/math].

We say that the grasshopper is immune to order j for some [math]\displaystyle{ 1 \leq j \leq n }[/math] if for every distinct [math]\displaystyle{ b_1,\ldots,b_{j'} }[/math] in [math]\displaystyle{ \{a_1,\ldots,a_n\} }[/math] with [math]\displaystyle{ 1 \leq j' \leq j }[/math] and [math]\displaystyle{ b_1+\ldots+b_{j'} \not \in M }[/math], the grasshopper can safely reach [math]\displaystyle{ b_1+\ldots+b_{j'} }[/math] in j' steps, using a permutation of [math]\displaystyle{ b_1,\ldots,b_{j'} }[/math]. In particular this implies that every integer in [math]\displaystyle{ S_j \backslash M }[/math] can be safely reached in j steps. Clearly the grasshopper is immune to order 1; it will suffice to show that the grasshopper is immune to order n.

We use induction. Let [math]\displaystyle{ 1 \leq j \lt n }[/math], and suppose that the grasshopper is already known to be immune to order j. We now show that it is immune to order j+1.

First suppose that [math]\displaystyle{ M \cap S_j }[/math] has cardinality at most j. Then the claim is easy, because to reach [math]\displaystyle{ b_1+\ldots+b_{j+1} \in S_{j+1} \backslash M }[/math] in j+1 steps using a permutation of [math]\displaystyle{ b_1+\ldots+b_{j+1} }[/math], there are j+1 points in [math]\displaystyle{ S_j }[/math] that one could potentially use. At most j of these lie in M, so there is one that does not lie in M. By induction hypothesis, the grasshopper can reach that point safely in j steps, and can thus reach the original point in j+1 steps, as required.

Now suppose instead that [math]\displaystyle{ M \cap S_j }[/math] has cardinality at least j+1. Then, by Assumption A, we cannot pass [math]\displaystyle{ M \cap S_j }[/math] safely in j+1 or fewer steps. In particular, we cannot safely reach [math]\displaystyle{ a_i+a_{n-j+1}+\ldots+a_n }[/math] in j+1 steps for any [math]\displaystyle{ 1 \leq i \leq n-j }[/math].

Let I be the set of all [math]\displaystyle{ 1\le i\le n-j }[/math] such that [math]\displaystyle{ a_i+a_{n-j+1}+\dots+a_n }[/math] is not in M. Since [math]\displaystyle{ M \cap S_j }[/math] already uses up at least j+1 of the points in M, I cannot be empty. For each i in I, [math]\displaystyle{ a_i+a_{n-j+1}+\ldots+a_{n-1} }[/math] must lie in M, otherwise, we could safely reach [math]\displaystyle{ a_i+a_{n-j+1}+\ldots+a_{n} }[/math] in j+1 steps by the induction hypothesis. Similarly, if i is the greatest element of I, [math]\displaystyle{ a_i+a_{n-j+1}+\ldots+a_n - a_m }[/math] must lie in M for any m equal to either i or n-j+1,...,n-1. But this forces M to contain n distinct elements, a contradiction. Specifically the n distinct elements are as follows:

1. [math]\displaystyle{ a_i+a_{n-j+1}+\ldots+a_{n} }[/math] for [math]\displaystyle{ i\ {\not\in}\ I }[/math] ;
2. [math]\displaystyle{ a_i+a_{n-j+1}+\ldots+a_{n-1} }[/math] for [math]\displaystyle{ i\in I }[/math] ; and
3. for the biggest [math]\displaystyle{ i\in I }[/math], the numbers [math]\displaystyle{ a_i+a_{n-j+1}+\ldots+a_{n}-a_{m} }[/math].

Proof #2

This is a version of Brumm’s proof with inspiration from Curioso. It is another induction, assuming we can deal with n-1 mines in n leaps, and extending to the case with n mines and n+1 leaps. This is an attempt at a write-up with minimal technicality - it is therefore a little wordy. The basic strategy is to try to make the longest leap and see what might go wrong. It turns out that there are two things.

First, we might not jump any mines at all (but perhaps landing on a mine), so our inductive hypothesis has to deal with too many mines. In fact we can deal with all but one of the mines. We start from the far end and trace a path backwards, keeping the longest leap in reserve, and knowing that all the mines are in the range of the remaining leaps, because we didn't jump any with the longest leap. We can arrange for the mine we can't pass to be the one the one closest to the beginning and then swap in the longest leap to make sure we can jump this one as well.

Second, we might land on a mine and jump some too. The mines we jump might get in the way of shorter leaps. It turns out that we can always find two leaps, with the longest leap as the second jump, taking us beyond at least two mines and the induction goes through.

PROOF

We can trivially negotiate zero mines with one leap (the case n=1).

We assume that, provided the last place is clear, that we can deal with (n-1) or fewer mines in n leaps, and we want to show that we can deal with n mines in (n+1) leaps.

We try to make the longest leap.

Case 1: If the longest leap carries us to a clear space (no mine) and jumps at least one mine, we are left with n leaps and at most (n-1) mines, which we can do by hypothesis.

Case 2: If the longest leap carries us to a clear space, but doesn’t jump a mine, we work from the other end of the minefield. If we remove the mine closest to the beginning we have (n-1) mines left, and we know that we can negotiate all of these with the n leaps other than the largest (we ignore the blank spaces covered by the largest leap at the beginning).

Case 2.1: If this arrangement also avoids the mine we removed, we are done.

Case 2.2: If it doesn’t – working from the far end – take the leap which lands on this mine, and replace it by the longest leap, which is longer, and therefore jumps us clear of the mine. There are no mines closer to the beginning than this, so we use any remaining leaps to take us to the beginning and we have a path through.

Case 3: If the longest leap lands on a mine but doesn’t jump any mines, this is similar to case 2.2 – this mine is the closest one to the beginning. We can find a path from the far end which lands only on this mine (by hypothesis - jumping the remaining n-1 mines with n leaps). We look at the leap which takes us there, and swap it with the longest leap to jump clear of it, while the swapped leap takes us to the beginning, and we have our path.

Case 4: In this case the longest leap lands on a mine and jumps one or more mines. Following brumm’s notation, assume the longest leap jumps f of the mines, with f at least 1. We have accounted for f+1 mines (including the one we landed on). So there are (n-f-1) mines out of range of the longest leap. Observe that there are n other possible leaps from the beginning, all different and shorter than the longest leap, and there are at most f mines in this range to hit, so there are at least (n-f) possible initial leaps which don’t hit a mine. For each of those (n-f) possible first leaps, try following with the longest leap, which definitely takes us beyond the first f+1 mines. This gives us (n-f) double jumps of different lengths, but there are just (n-f-1) mines we might hit, so one of these double jumps lands clear. This double jump passes at least two mines. So the remaining (n-1) jumps are available to negotiate at most (n-2) mines, and we are done.

Proof #3

A variant of Proof #2, with fewer cases (2!) and a bit more formally presented.

Generalisation

Given a starting point [math]\displaystyle{ a_{0} }[/math], [math]\displaystyle{ n }[/math] distinct positive integers, [math]\displaystyle{ A={a_{1},a_{2},...,a_{n}} }[/math] and [math]\displaystyle{ k }[/math] values [math]\displaystyle{ M={m_{1},m_{2},...,m_{k}} }[/math] with [math]\displaystyle{ k\lt n }[/math], where [math]\displaystyle{ a_{0}\notin M }[/math] and [math]\displaystyle{ \sum_{i=0}^{n}a_{i}\notin M }[/math], then there is an ordering, [math]\displaystyle{ \phi }[/math], on [math]\displaystyle{ A }[/math], such that [math]\displaystyle{ a_{0}+\sum_{i=1}^{j}a_{\phi(i)}\notin M }[/math] for any [math]\displaystyle{ j }[/math] between [math]\displaystyle{ 1 }[/math] and [math]\displaystyle{ n }[/math].

Base Case

If [math]\displaystyle{ n=1 }[/math] then [math]\displaystyle{ k=0 }[/math], and [math]\displaystyle{ M }[/math] is the empty set and theorem is trivially true.

Inductive Step

When [math]\displaystyle{ n\gt 1 }[/math], then either [math]\displaystyle{ k=0 }[/math], [math]\displaystyle{ M }[/math] is the empty set, and hypothesis is trivially true, or [math]\displaystyle{ k\gt 0 }[/math]. Assume hypothesis is true for all [math]\displaystyle{ n'\lt n }[/math], and [math]\displaystyle{ k'\lt k }[/math]. Label A so that [math]\displaystyle{ a_{n}=max(A) }[/math], and M so that [math]\displaystyle{ m_{1}=min(M) }[/math].

Case 1

Assume: [math]\displaystyle{ a_{0}+a_{n}\leq m_{1} }[/math] or [math]\displaystyle{ a_{0}+a_{n}\notin M }[/math]

In this case [math]\displaystyle{ a_{0}+a_{n}\notin M\setminus\{m_{1}\} }[/math], so by the inductive hypothesis, it is possible to find an ordering for [math]\displaystyle{ A'=A\setminus\{a_{n}\} }[/math], [math]\displaystyle{ M'=M\setminus\{m_{1}\} }[/math], [math]\displaystyle{ a'_{0}=a_{0}+a_{n} }[/math]. Call that ordering [math]\displaystyle{ \phi' }[/math].

Consider the mapping [math]\displaystyle{ \phi(1)=n }[/math], and [math]\displaystyle{ \phi(x)=\phi'(x-1) }[/math] when [math]\displaystyle{ x\geq2 }[/math]. Then we have that [math]\displaystyle{ a'_{0}+\sum_{i=1}^{j}a_{\phi'(i)}\notin M' }[/math] for [math]\displaystyle{ 1\leq j\leq n-1 }[/math], which is the same as [math]\displaystyle{ a_{0}+a_{n}+\sum_{i=2}^{j}a_{\phi(i)}\notin M\setminus\{m_{1}\} }[/math] for [math]\displaystyle{ 2\leq j\leq n }[/math], and since [math]\displaystyle{ a_{0}+a_{n}\notin M\setminus\{m_{1}\} }[/math] and [math]\displaystyle{ a_{\phi(1)}=a_{n} }[/math], we have [math]\displaystyle{ a_{0}+\sum_{i=1}^{j}a_{\phi(i)}\notin M\setminus\{m_{1}\} }[/math] for [math]\displaystyle{ 1\leq j\leq n }[/math].

Next consider the partial sums, [math]\displaystyle{ s_{j}=a_{0}+\sum_{i=1}^{j}a_{\phi(i)} }[/math]. Since [math]\displaystyle{ a_{\phi(i)} }[/math] is a positive integer, [math]\displaystyle{ s_{j}\lt s_{j+1} }[/math], so there exists some [math]\displaystyle{ \gamma\in\{0\ldots n\} }[/math] such that [math]\displaystyle{ s_{j}\leq m_{1} }[/math] when [math]\displaystyle{ j\lt \gamma }[/math], and [math]\displaystyle{ m_{1}\lt s_{j} }[/math] when [math]\displaystyle{ \gamma\leq j }[/math].

Now consider the reordering

[math]\displaystyle{ \rho(x)=\begin{cases} \phi(x+1) & 1\leq x\lt \gamma\\ \phi(1) & x=\gamma\\ \phi(x) & \gamma\lt x \end{cases} }[/math]

and the corresponding partial sums [math]\displaystyle{ s'_{j}=a_{0}+\sum_{i=1}^{j}a_{\rho(i)} }[/math].

Consider [math]\displaystyle{ j\lt \gamma }[/math]. Then [math]\displaystyle{ s'_{j}=s_{j}-a_{\phi(1)}+a_{\rho(j)}=s_{j}-a_{n}+a_{\phi(j+1)} }[/math]. And since [math]\displaystyle{ a_{n}=max(A) }[/math], we have [math]\displaystyle{ s'_{j}\lt s_{j}\leq m_{1} }[/math], and hence [math]\displaystyle{ s'_{j}\notin M }[/math].

Further, for [math]\displaystyle{ \gamma\leq j }[/math], we have [math]\displaystyle{ s'_{j}=s_{j} }[/math], and since [math]\displaystyle{ m_{1}\lt s_{j} }[/math] and [math]\displaystyle{ s_{j}\notin M\setminus\{m_{1}\} }[/math], we have [math]\displaystyle{ s'_{j}\notin M }[/math] in all cases, and our ordering, [math]\displaystyle{ \rho }[/math] suffices.

Case 2

Assume: [math]\displaystyle{ m_{1}\lt a_{0}+a_{n} }[/math] and [math]\displaystyle{ a_{0}+a_{n}\in M }[/math]

In this case we first observe that [math]\displaystyle{ m_{1} }[/math] and [math]\displaystyle{ a_{0}+a_{n} }[/math] are distinct members of [math]\displaystyle{ M }[/math], and thus [math]\displaystyle{ k\geq2 }[/math] and [math]\displaystyle{ n\geq3 }[/math].

We consider [math]\displaystyle{ n-1 }[/math] pigeon holes labelled [math]\displaystyle{ 1\leq i\lt n }[/math], assigning each element [math]\displaystyle{ m\in M }[/math] to a pigeon hole if either [math]\displaystyle{ m=a_{0}+a_{i} }[/math] or [math]\displaystyle{ m=a_{0}+a_{i}+a_{n} }[/math]. Since each [math]\displaystyle{ a_{i} }[/math] is distinct and positive and [math]\displaystyle{ a_{i}\lt a_{n} }[/math], no[math]\displaystyle{ m }[/math] can be assigned to two different pigeon holes, and furthermore, since [math]\displaystyle{ a_{0}+a_{n}\in M }[/math] only the remaining [math]\displaystyle{ k-1 }[/math] members of [math]\displaystyle{ M }[/math] can be assigned to a pigeon-hole.

But since [math]\displaystyle{ k\lt n }[/math], [math]\displaystyle{ k-1\lt n-1 }[/math], and at least one pigeon-hole must be empty, so call it [math]\displaystyle{ x }[/math]. This means [math]\displaystyle{ a_{0}+a_{x} }[/math] and [math]\displaystyle{ a_{0}+a_{x}+a_{n} }[/math] are not members of [math]\displaystyle{ M }[/math], and by the inductive hypothesis, we can find an ordering [math]\displaystyle{ \phi' }[/math] for [math]\displaystyle{ A'=A\setminus\{a_{x},a_{n}\} }[/math], [math]\displaystyle{ M'=M\setminus\{m_{1},a_{0}+a_{n}\} }[/math], [math]\displaystyle{ a'_{0}=a_{0}+a_{x}+a_{n} }[/math], and establish an ordering that satisfies the requirements:

[math]\displaystyle{ \phi(j)=\begin{cases} x & j=1\\ n & j=2\\ \phi'(j-2) & j\gt 2 \end{cases} }[/math]

Proof #4

There is a dual form of Bramm’s proof. It is based on the fact that we can subtract everything from the sum of the a_i’s and get a copy of the same problem. Roughly what happens is that you can replace max a with target-max a and let f be the number of mines betweem target-max a and target. I think that most proofs of this result have a dual associated with them.

Here is case one of the dual: Target-Max a is a mine and f is greater 0. In that case, out of the target-a_i that are not max a (n numbers), at least n-f are not mined (when taken as a first jump). Consider the n double jumps (target–max a_i != max a, target-max a, target). At least n-f of those are not mined on the last jump. The number of mines in (0 target -max a) is the number of mines (n) less f less the one for target -max a, yielding n-f-1 which is less than n-f. Thus by counting argument, at least one of the double jumps does not hit a mine on both jumps. This double jump takes two jumps and jumps over f+1 >=2 mines, yielding a problem with n-2 mines and n-1 remaining jumps, which is solved by induction.

Here is case two of the dual: Target-max a is not a mine and f>0. Take max a as last jump, yielding problem with n remaining jumps and n-f<n mines, which is solved by induction.

Here is case three of the dual: Target- max a is a mine and f=0. Let max M be the largest mine in M. Construct M’=M\{max M}. Jump target-max a to target as the last jump and solve the n-problem with the remaining a_i and M’ Let a_x be the last jump of this solution. Exchange max a and a_x (i.e. jump a_x last and max a before that). target -(max a+a_x) is no mine (guaranteed by solution), target-a_x is no mine (because target-a_x is greater than target-max a == max M as above). There are no mines in the rest. We have completed solution for n+1.

Here is the final case of the dual: Target-max a is not a mine and f=0. As in case 3, construct M’, jump max a last and solve for the remaining a_i and M’. If this solution hits max M in step k, construct a new solution by exchanging step k-1 and the last step (i.e. target-max a). There are no mines after max M, thus the mine is avoided and no new mines are hit. We have completed solution for n+1

Proof #5

We order the steps as [math]\displaystyle{ a_1 \lt a_2 \lt \ldots \lt a_n }[/math] and the mines as [math]\displaystyle{ b_1 \lt b_2 \lt \ldots \lt b_{n-1} }[/math].

We remove the largest mine [math]\displaystyle{ b_{n-1} }[/math]and the largest step [math]\displaystyle{ a_n }[/math] and try to apply induction. We look at the sum [math]\displaystyle{ t':=\sum_{1\le i\le n-1} a_i }[/math]. Two things can happen:

1. [math]\displaystyle{ t' }[/math] is not among the first n-2 mines. Then we use the induction hypothesis and get some ordering of the numbers. If we hit the largest mine [math]\displaystyle{ b_{n} }[/math] somehow with that ordering we swap the last step for the largest step [math]\displaystyle{ a_n }[/math] and skip over the largest mine. Then we just continue until we are done. If we do not hit [math]\displaystyle{ b_n }[/math]. we are done anyway.

2. [math]\displaystyle{ t' }[/math] is a mine and there is one or more mines greater than [math]\displaystyle{ t' }[/math]. Then what remains is case one of the dual proof which we solve as follows:

Let [math]\displaystyle{ t:=\sum_{1\le i\le n} a_i }[/math]. Then out of the [math]\displaystyle{ 2(n-1) }[/math] numbers [math]\displaystyle{ t-a_i,t-a_i-a_n,1\le i\le n-1 }[/math] there are at most n-2 mines (because [math]\displaystyle{ t'=t-a_n }[/math] is a mine and not among those numbers). Therefore there is a [math]\displaystyle{ 1\le i\le n-1 }[/math] such that [math]\displaystyle{ t-a_i,t-a_i-a_n }[/math] are no mines. The double jump [math]\displaystyle{ t-a_i-a_n,t-a_i,t }[/math] takes two jumps and jumps over at least two mines, yielding a problem with at most [math]\displaystyle{ n-3 }[/math] mines and [math]\displaystyle{ n-2 }[/math] remaining jumps, which is solved by induction.

Proof #6

The proof 5 doesn't seem correct. The first step is not qualified for induction: How can it make sure b_1,..., b_{n-2} < a_1 + ... + a_{n-1}?

(Insert proof here)

By mathematical induction, needless to say about n = 2. Let's consider case n.

Given a set B = {b_1, ..., b_{n-1}}, whose member is between 0 and A_1 + ... + A_n.

A point in B is called "blocker" if it is a sum of some of A_1, ..., A_n (no duplicates). This kind of points will block the grasshopper.

Assume grasshopper can jump to point A_1 + A_2 + ... + A_k (k >= 1) with maximum k (for convenience, we use A_1, ..., A_k. If not the case, we can always rename them). if k = n, then done.

So, we can assume k < n.

Without loss of generality, we assume A_{k+1} < A_{k+2} < ... < A_n

Let's consider a group of points:

A_2, A_3, ..., A_k, A_{k+1}; Let p_1 = A_2 + A_3 + ... + A_k + A_{k+1}; A_1, A_3, ..., A_{k-1}, A_{k+1}; Let p_2 = A_1 + A_3 + .... + A_{k-1} + A_{k+1}; ... A_1, A_2, ..., A_{k_1}, A_{k+1}; Let p_k = A_1 + A_2 + .... + A_{k-1} + A_{k+1}; A_1, A_2, ..., A_{k-1}, A_k; Let p_{k+1} = A_1 + A_2 + ... + A_{k-1} + A_k;

Actually, they are k combination of {A_1, ...., A_k, A_{k+1}}, for example, when k = 3, the group will be: A_2, A_3, A_4; A_1, A_3, A_4; A_1, A_2, A_4; A_1, A_2, A_3;

Notice that k is the maximum the grasshopper can go, so the following points are all blockers off the point p_(k+1):

p_{k+1} + A_{k+1}, ...., p_{k+1} + A_n

which are n-k different blockers.

Obviously, p_1, p_2, ..., p_k, p_{k+1} + A_{k+1}, ...., p_{k+1} + A_n are mutually distinct and p_1, p_2, ..., p_k all smaller than p_{k+1} + A_i, where i >= k + 1. The total number of the above points is n. If p_i ( 1 <= i <=k) is not blocker, then there are at most k - 1 blockers smaller than p_i. By our induction, p_i can be reachable by the grasshopper.

We define another set C = {p_{k+1} + A_{k+1}, ...., p_{k+1} + A_n}. This set will be expanded in the following way:

If p_i is not a blocker (where 1 <= i <= k), then we add p_i + A_{k+2}, ..., p_i + A_n to set C.

If there are m such p_i (non-blockers) from p_1, ..., p_k. Then we can easily know set C will have at least n - k + m different values. Can all these different values be blockers? (A) If Yes, we know there are k - m blockers from p_1, ..., p_k. In this case, we will have n -k + m + k -m = n blcokers, which contracdicts the condition. (B) If No, so we can go further from one of m non-blockers, which contradicts k is the maximum assumption.

Comment on Proof #6

Which are the details behind the following claim near the end? "Then we can easily know set C will have at least n - k + m different values." Also, how are we sure that all these n - k + m numbers are different from all the k - m blockers from p_1, ..., p_k?

Kai Neergård