Puzzle time - Medieval etiquette and rivers
-
In eighth century Europe, it was considered unseemly for a man to be in the presence of a married woman, unless her husband was there as well. This posed problems for three married couples who wished to cross a river, the only means being a rowboat that could carry at most two people.
Can they get to the other side without violating their social norms? If so, what's the minimum number of crossings needed?
-
:::
Let's designate the people M 0,W 0,M 1,W 1,M 2,W 2, whereby M x is married to W x.Here's a valid move sequence.
[M 0,W 0],[M 0],[W 1,W 2],[W 1],[M 2,M 0],[W 0,M 0],[M 1,M 0],[W 2],[W 1,W 0],[M 2],[W 2,M 2]
From what I can see, there are 192 different solutions. If you factor out permutations, 32 distinct solutions remain, 8 of which have length 11, 8 of which have length 13, and 16 of which have length 15. So, the minimum number of crossings is 11.
Would be a nice exercise to model and verify this in a class on verification of finite state systems. It would be easy to express the safety condition and the desired final state in LTL.
::: -
It is 11 under the ‘hard constraint’ where you can’t violate the taboos even in the moments of switching in and out of boats.
Under the ‘soft constraint’, where you only prevent taboo-violations on the shores and in the boat itself you can do 9.
-
Which reminds me of an important PSA. Don’t ever try to fuck in a canoe.
