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].
Accueil
