Drôle de conception de ce qu'est le "rangement"... disons que dans cette notion est bien souvent comprise la notion d'efficacité et "d'optimisation"...

Alors, pour la méthode générale (k tiroirs, 2^n cravates):


On pose i=0

1/ Etape 1:
Précondition: tous les tiroirs ont un nombre de cravates divisible par 2^i.
On prend les tiroirs dont le nombre de cravates ne soit pas divisible par 2^(i+1).

Affirmation: Il y en a un nombre pair.

Preuve: Supposons que l'on en ait un nombre impair (disons 2p+1). Soit T le nombre total de cravates.
On pose T / 2^i = T'
Pour chaque tiroir, si on divise le nombre de cravates par 2^i, on obtient (2p+1) résultats impairs et k-(2p+1) résultats pairs.
La somme de tous ces nombres est donc impaire, elle vaut par ailleurs T', donc T' n'est pas divisible par 2^(i+1), ce qui est absurde.

Postcondition: on a pris un nombre pair de tiroir.



2/ Etape 2:
Précondition: on considère un nombre pair de tiroirs ayant un nombre de cravates divisible par 2^i mais pas 2^(i+1).
On groupe ces tiroirs en paires, pour chaque paire de tiroirs ayant respectivement a et b cravates, avec par exemple a>b, on déplace b cravates de l'un vers l'autre.

Affirmation: Les deux tiroirs comportent un nombre de de cravates divisible par 2^(i+1).

Preuve: On pose:
a/2^i = 2a'+1
b/2^i = 2b'+1
On a:
a-b = (2a'+2b') * 2^i = (a'+b') * 2^(i+1)
2b = (4b'+2) * 2^i = (2b'+1) * 2^(i+1)

Postcondition: tous nos tiroirs ont un nombre de cravates divisible par 2^(i+1).
Soit i+1=n et on a alors terminé, soit on recommence à l'étape 1 avec i+1 au lieu de i, la précondition de l'étape 1 étant bien respectée.


Nombre total maximal d'étapes: on aurait au pire k/2 paires à traiter dans l'étape 2, à répéter n fois. Autrement dit, au maximum de nk/2 opérations sont nécessaires.


Concernant le tiroir de destination, vu qu'un tiroir devient vide quand on verse ses cravates dans un tiroir de même contenance, alors on pourrait tout à fait inverser le role du vide et du plei. Vu que k-1 tiroirs finissent vides, le dernier peut-être n'importe lequel.



Petite application avec l'exemple des 64 cravates (qu'on va mettre dans le 1er tiroir tiens).
1  3  5  9 13 14 19 => on prend tout sauf 14.
2  2 10  4 26 14  6 => 3 opérations, on prend tout sauf 4
4  0 20  4 16  8 12 => 3 opérations, on prend tout sauf 8 et 16
8  0  8  0 16  8 24 => 2 opérations, on prend tout sauf 16
16  0  0  0 16 16 16 => 2 opérations
32  0  0  0  0 32  0 => 2 opérations
64  0  0  0  0  0  0 => 1 opération:

Total: 13 opérations (< à 6*7/2 = 21).