Вот вы лучше скажите: основываясь на ваших условиях (не оговорено, на каком берегу сколько народу) - при каком кол-ве N людей, случайным образом распределённым по разным берегам, задача по поиску оптимального решения станет трансвычислительной? Вы же понимаете, что даже изменения вводных, подобные вашим - не делают задачу по поиску оптимального решения (и доказательству, что найденное решение - оптимальное при любой N) более простой? И помните: проблема P=NP, не стоит искать алгоритм по известному решению задачи на простых вводных. Так что сути проблемы по поиску оптимального решения ваши допущения о неполной формализации ТЗ - не меняют, ни на йоту.
Ох блин, не завидую вашим заказчикам. Им и на основные, принципиальные вопросы то отвечать лень до боли, а с таким как вы повеситься можно. )))