Il problema ciclista-pedone

Il problema ciclista-pedone si ripropone di trovare uno schema ottimale per cui un gruppo di persone con una quantità inferiore di biciclette arrivi a destinazione nel minor tempo possibile. Vengono inizialmente introdotte le definizioni di matrice k-uniforme e di schema ottimale; si noterà quindi che la matrice associata ad uno schema ottimale è necessariamente k-uniforme. In seguito si daranno le definizioni di mappa di assegnazione delle biciclette e di parola canonica; si dimostrerà che in uno schema ottimale le mappe di assegnazione così come le parole canoniche rispettano alcune importanti proprietà. Si parlerà poi di alcuni schemi ottimali ottenuti da particolari permutazioni delle righe e delle colonne di una matrice k-uniforme. Infine si considererà il percorso come un circuito in modo che la partenza coincida con l'arrivo. Si definiranno lo schema e la matrice ciclici e si dimostreranno alcune proprietà che non valgono per i generici schemi ottimali. Si noterà che l'invertibilità di una matrice ciclica è strettamente legata al massimo comune divisore tra il numero dei viaggiatori e il numero delle biciclette: la matrice in questione è non singolare quando il numero dei viaggiatori e quello delle biciclette sono coprimi.