Je propose ce double critère (pour que ça marche):
R(2n/2k)>=n-(k-1)*[n/k]<=k-1.
où R() est reste de division et []partie entière.

Pour faire le plus simple possible:

GGG.....GGG.....GGG....GGG.....

Si G est minoritaire dans l'intervalle 2k, il occupe k-1 emplacements dans chaque intervalle, D en occupant k+1 (on a tout intérêt à mettre le plus de G possibles dans 2k). 
Le nombre d'intervalles distincts est [2n/2k]. Le nombre de G qu'on peut mettre est donc (k-1)*[2n/2k]. Mais il faudra bien mettre tous les G, au nombre de n.
Le restant des G à placer à la fin est donc n-(k-1)*[2n/2k]. Et il faut les placer dans le reste de la division R(2n/2k). Mais ce R étant <2k, on ne peut donc  placer que au plus (k-1) G.

D'où
R(2n/2k)>=n-(k-1)[2n/2k]<=k-1.

@nodgim : Ok, tu as raisonné comme moi. Tu ne distingues pas trop les conditions nécessaires et suffisantes, mais l'essentiel est là.

@gwen : c'est valable pour k=1 ? Et pour k=5 et n=11 par exemple ?

Gwen, tes exemples ne sont pas bons :

par exemple pour k=1 et n=2, sur (1 2 1) ça foire dès le premier intervalle.

Idem pour tous les autres exemples.

Bravo à nodgim, le seul à avoir trouvé !

Je reprends son critère et son raisonnement, un peu réarrangé à ma sauce.

On note $q$ et $r$ le quotient et le reste dans la division de $n$ par $k$.

Le critère est le suivant :

Il est possible de disposer les $2n$ chaussures les unes à côté des autres sans qu'il existe un intervalle de $2k$ chaussures contenant autant de chaussures gauches que de droites si et seulement si :
[TeX]r \geq q[/latex]   et   [latex]k \geq q+r+1[/latex]


Démonstration :

1) C'est une condition nécessaire :

Supposons que $2n$ chaussures ont été disposées les unes à côté des autres sans qu'il existe un intervalle de $2k$ chaussures contenant autant de chaussures gauches que de droites. On numérote alors les chaussures d'une extrémité à l'autre, de $1$ à $2n$ et l'on note $G [i,j]$ le nombre de chaussures gauches parmi les chaussures dont le numéro est dans l'intervalle $[i;j]$.

Quitte à échanger les chaussures gauches et droites, on peut supposer que $G[1,2k]\leq k-1$.

On montre alors par récurrence que $G[1+i,2k+i]\leq k-1$, et ce $\forall i \in [0,2n-2k]$.

En effet, $G[1+i+1,2k+i+1] \leq G[1+i,2k+i]+1[/TeX] et [latex]G[1+i+1,2k+i+1]\neq k$.


Rappelons pour la suite que $n=kq+r$ avec $0\leq r <k$.
$$G[2kq+1,2n] = G[1,2n] - G[1,2kq] = n - \sum_{i=1}^{q} G[(i-1)2k+1,i2k] \geq n-q(k-1)$$
donc $G[2kq+1,2n] \geq r+q$

Or $G[2kq+1,2n] \leq 2n-2kq = 2r$ ce qui donne $2r \geq r+q$ et donc $r \geq q$.

D'autre part $G[2kq+1,2n] \leq k-1$ ce qui donne $k-1 \geq r+q$ et donc $k \geq q+r+1$.

2) C'est une condition suffisante :

Supposons que $r \geq q$   et   $k \geq q+r+1$

On réalise alors la suite de chaussures suivante :
$$\left(G^{k-1}D^{k+1}\right)^{q-1}G^{k-1}D^{k+1+r-q}G^{q+r}$$
Cette suite convient car :

le nombre de chaussures gauches est :
$$(k-1)q+(q+r)=kq+r=n$$
le nombre de chaussures droites est :
$$(k+1)(q-1)+(k+1+r-q)=(k+1)q-q+r=kq+r=n$$
le dernier groupe de G compte moins de $k-1$ chaussures :
$$k \geq q+r+1[/latex] donc [latex]k-1 \geq q+r$$
le dernier groupe de D compte plus de $k+1$ chaussures :
$$r \geq q[/latex] donc [latex]k+1+r-q \geq k+1$$
CQFD


Application Numérique :

Dans l'exemple initial donné par Sasorii avec $n=15$, il y a d'autres longueurs d'intervalles pour lesquelles il est impossible de réaliser une suite de chaussures satisfaisant les conditions imposées.

Il est possible de remplacer $k=5$ par n'importe quel entier $k$ de l'ensemble $\lbrace{1;2;3;4;5;7;8\rbrace}$.