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 [latex]q[/latex] et [latex]r[/latex] le quotient et le reste dans la division de [latex]n[/latex] par [latex]k[/latex].

Le critère est le suivant :

Il est possible de disposer les [latex]2n[/latex] chaussures les unes à côté des autres sans qu'il existe un intervalle de [latex]2k[/latex] 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 [latex]2n[/latex] chaussures ont été disposées les unes à côté des autres sans qu'il existe un intervalle de [latex]2k[/latex] chaussures contenant autant de chaussures gauches que de droites. On numérote alors les chaussures d'une extrémité à l'autre, de [latex]1[/latex] à [latex]2n[/latex] et l'on note [latex]G [i,j][/latex] le nombre de chaussures gauches parmi les chaussures dont le numéro est dans l'intervalle [latex][i;j][/latex].

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

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

En effet, [latex]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[/latex].


Rappelons pour la suite que [latex]n=kq+r[/latex] avec [latex]0\leq r <k[/latex].
[TeX]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)[/TeX]
donc [latex]G[2kq+1,2n] \geq r+q[/latex]

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

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

2) C'est une condition suffisante :

Supposons que [latex]r \geq q[/latex]   et   [latex]k \geq q+r+1[/latex]

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

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


Application Numérique :

Dans l'exemple initial donné par Sasorii avec [latex]n=15[/latex], 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 [latex]k=5[/latex] par n'importe quel entier [latex]k[/latex] de l'ensemble [latex]\lbrace{1;2;3;4;5;7;8\rbrace}[/latex].