Per comprendere cosa succede sul vostro problema di una sola riga, la cosa migliore e' di giocarci un po'.
Fatevi delle istanze ragionevolmente piccole (incominciando da piccolissime) e vedete quante posizioni accese vi restano all'ottimo.
E' probabile che entri la luce.