7
$\begingroup$

Consider two lists: $(1,2,\dots,n)$ and $(a_1,a_2,\dots,a_n)$, where the second list is a permutation of the first. Does there exist a constant $c$ such that for any $n$ and for any second list, we can choose a subset $A\subseteq\{1,2,\dots,n\}$ of size at most $n/2+c$ so that for any prefix and suffix of either list of any length $k\in[1,n]$, at least $k/2$ of those elements are in $A$?

The $n/2$ part is necessary: even if we just have the list $(1,2,\dots,n)$ and require the condition on the prefix, when taking $k=n$ we already need to include at least $n/2$ elements. If we only want the prefixes and suffixes of the first list, we can choose $A=\{1,3,5,\dots\}$ along with $n$ (if not already included), which comes to at most $n/2+1$ elements.

$\endgroup$
2
  • $\begingroup$ Probably $n$ is even, can you add that in your question? $\endgroup$
    – Jaideep Khare
    Apr 28, 2017 at 22:00
  • $\begingroup$ I see nothing against odd $n$. $\endgroup$
    – Smylic
    Apr 28, 2017 at 22:11

1 Answer 1

Reset to default
3
+50
$\begingroup$

This problem can be reformulated as "Given a permutation $\sigma$ of $\{1,\dots,n\}$, is it always possible to choose $a_j=\pm 1$ such that all partial sums $\sum_{j=1}^k a_j$ and $\sum_{j=1}^k a_{\sigma(j)}$ are bounded by some constant $C$". The answer is "Yes". Consider the graph in which the vertices are $1,\dots,n$ and edges are $1-2,3-4,5-6,\dots$ (white) and $\sigma(1)-\sigma(2), \sigma(3)-\sigma(4),\dots$ (yellow). If we manage to choose the signs so that every edge connects two vertices of different signs, we are done. However, the only chance to get a cycle in this graph is to alternate white and yellow edges, so all cycles are even, making our choice possible.

A more interesting question is what happens if instead of one, we have 5 permutations. I suspect the answer is still positive but, of course, this simple approach has to be modified to cover that case.

$\endgroup$
10
  • $\begingroup$ I don't see how we can only look at the partial sums of $\sum_j^n a_j$, and not $\sum_j^n a_{n-j}$ - the first seems like it would correspond to prefixes, the second would be postfixes perhaps? $$. $$ Likewise, such a $\pm 1$ labeling given by the graph doesn't directly give $A$ - as we can have $n$ labeled $-1$ with $1$ labeled $+1$ without consequence, yet this $A$ wont satisfy the claim. $\endgroup$
    – Artimis Fowl
    May 3, 2017 at 2:00
  • $\begingroup$ @ArtimisFowl 1) Since the total sum is nearly 0, the tail is essentially minus the head. 2) We have no chance to label $n$ -1's and just one 1. All edges should join vertices of different signs and the white edges alone tell you that the number of 1's is about $n/2$. $\endgroup$
    – fedja
    May 3, 2017 at 13:39
  • $\begingroup$ 1) For any $C$, pick $n=3C$, with $\sigma = (1, 2, \cdots, 3C)$. Then the labeling: $-1, -1, \cdots, -1, 1, 1, \cdots, 1, 1, \cdots 1$ - ie, $C$ "$-1$"s followed by $2C$ "$1$"'s, causes problems. This has every prefix bounded between $-C$ and $C$, but has a suffix which violates that bound, (by double!) despite meeting the other criteria. 2) I feel like you've overspecified - Pick $n=4$, $\sigma = (1,2,4,3)$. Then the graph has edges: $1 - 2, 3-4$ (white), $1-2, 3-4$ (yellow), and the labeling $1, -1, -1, 1$ is a valid bipartition. But it does not give a valid $A$ $\endgroup$
    – Artimis Fowl
    May 3, 2017 at 16:34
  • $\begingroup$ @ArtimisFowl 1) Every prefix means every prefix up to the full size $n$; 2) $A$ is obtained by taking all integers labeled 1 and adding, say, 3 elements at the beginning and the end of each of the two sequences. $\endgroup$
    – fedja
    May 3, 2017 at 19:25
  • 1
    $\begingroup$ @ToanQuangPham As I said, the set A is a bit larger than the set of $+1$'s: you should also add a few (3 is more than enough) extra elements from both ends of both sequences exactly to compensate for the effect you mentioned. $\endgroup$
    – fedja
    May 7, 2017 at 11:52

You must log in to answer this question.

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