Poliisit ja Rosvot - Ongelmanratkaisu

Eikö vankilapuolellakaan saa olla rosvojen ylivaltaa (oletetaan että rosvot vietäisiin suoraan vankilaan kun he toiselle puolelle saapuvat)? Silloin ei ole mahdollista: mietitään ensimmäistä soutua: ainoa mahdollisuus on PR. No entäs sitten takaisin soutu? Se ei voi olla kumpikaan, koska jos rosvo menee takaisin, tulee lähtöpuolelle kolme rosvoa vs. kaksi poliisia. Jos taas poliisi menee takaisin, jää toiselle puolelle rosvo itsekseen ja tämä rikkoo sääntöjä. Ja näkeehän tämän mahdottomuuden jo tarkastelemalla invarianttia

p1-r1 p2-r2,

missä p_i = poliisien määrä puolella i ja r_i vastaavasti rosvojen. Tämä arvo on siis vakiosti nolla, koska se on p1 p2 - (r1 r2) = 3-3 = 0. Mutta jos vaaditaan, että kummatkin summattavat pi-ri ovat epänegatiivisia, niin niiden on kummankin oltava nolla. Tällöin siirto puolelta toiselle on mahdollinen vain muodossa 1-1, joka on hyödytön, koska sen voi tehdä vain purjaamalla poliisia ja vankia puolelta toiselle eikä kaikkia näin saada mitenkään ylitse.

Jos taas vankilaanvienti on hetitapahtuva, niin sittenhän se on triviaalia vain poliisin käydä viemässä vangit yksi kerrallaan vankilaan ja lopuksi poliisit soutelee yksinään.

tarvitaan pitkä köysi joka sidotaan veneeseen. Kun ensimmäinen poliisi ja ensimmäinen rosvo ovat soutaneet joe ylitse niin vene vedetään tyhjänä takaisin lähtörantaan. soutaminen ja köydellä takaisinveto toistetaan kunnes kaikki poliisit ja rosvot ovat ylittäneet joen. .