Choosing half of prefix and suffix for three lists 
Consider three lists: $(1,2,\dots,n)$, $(a_1,a_2,\dots,a_n)$, and $(b_1,b_2,\dots,b_n)$, where the second and third lists are permutations of the first.
Does there exist a constant $c$ such that for any $n$ and for any second and third lists, 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 any list of any length $k\in[1,n]$, at least $k/2$ of those elements are in $A$?

When there are only two lists, this is true as shown here, even with $c=2$. However, it seems unlikely that the coloring technique used in the solution can be applied here.
 A: Here is the Dirichlet proof of the $C\log n$ bound. I'll do it for 3 lists, though it works for any number of them. Again, this post is to set the level of "triviality", not to solve the problem.
I'll be thinking of the $\pm$ reformulation. Split each of 3 lists into groups of $k$ (say, $k=10000$) subsequent positions. Consider all possible combinations of $0,1$ of length $n$ and for each such combination compute the sum in each group. Since there are $2^n$ combinations and only $(k+1)^{3n/k}\le 2^{n/2}$ possible sum values, there are at least $2^{n/2}$ combinations with certain particular sums. Among them there are $2$ combinations differing in at least $0.01n$ positions (again just by the sheer count: the number of combinations differing from a given one in fewer than $0.01n$ positions is well below $2^{n/2}$). Subtracting, we get a sequence of $\pm 1$ and $0$ with every group of $k$ summing to $0$ and, therefore, all partial sums bounded by $k$. The problem is that we still have $0$'s. However they are at most $0.99n$ and we can start the argument all over looking only at the corresponding positions. If $C(n)$ is the best bound one can achieve for lists of length $n$, this gives the recursion $C(n)\le k+C(0.99n)$, whose solution is logarithmic in $n$.
Edit Pi66 asked me to add the Steinitz type proof, so here goes. Once you generalize it properly, it becomes even easier than the Dirichlet one (my original version was more complicated).
Let us generalize immediately and request that each $\varepsilon_j$ should be one of the endpoints of an interval $I_j$ of length $1$ containing $0$. Again, split the series into groups of $6$. Set all $\epsilon_j=0$ to start with. Now keep the sums over all groups $0$. That is $3\frac n6=\frac n2$ equations. So, as long as we have at least $\frac n2+1$ free variables, we can find a non-trivial solution of the corresponding system and add it with some coefficient to bring one more variable to an endpoint  of the corresponding interval. Thus, we can get $n/2$ of them where they should be. Now freeze those and look at what we need to do with the rest. The admissible intervals for them have shifted, but otherwise we have the same problem we started with only with $n/2$ numbers. This yields the recursion $C(n)\le 6+C(n/2)$. The rest is just the same as before.
Final edit Ravi Boppana attracted my attention to this paper, which shows that the trivial $\log n$ bound is, actually, the best possible. Quite amazing, isn't it?
