I recently played an online card game in which the cards were spread on the table. The goal was for me to pick up as many as possible, subject to the following rule:
After picking up the first card, every subsequent card had to be 1 higher or 1 lower than the previous pick. So if the cards were three 1s, three 2s and three 3s, I could go 1→2→3→2→1→2→3, but then I wouldn't be able to pick up the last 1 and 3.
I generalized this to a multiset of natural numbers, from which I generated a graph with an edge between i
and j
if |i-j|=1
. This is of course NP-Easy by reduction to the longest path problem; but is it hard?