What is the maximum number of items in a river crossing puzzle?

Question

A River Crossing puzzle puts limits on the number of items that may cross a boundary, with limits on what may be left together. The "Fox, goose and bag of beans" is one of the earliest examples. Of course, by increasing the capacity of the boat, or the number/type of barriers, infinity is the upper limit. For this question, I am asking with the classical configuration of one barrier, with a limit of one transport per move. You can increase the number of items and their ability to coexist.

What is the largest number of items in a solvable river crossing puzzle that has been documented? What is the maximum that could be created?

Answer 1

If you have just items to transport, infinity. But it's no riddle, then.

But in 'classical' problem, every item except 1 is endangered by another item, every item except 1 is threatened by another item.

Under that circumstances you can't even solve it with 4, because no matter what item you take, there will be at least one 'colission' pair:

A -> B -> C -> D

It's unsolvable even if there's no threat from B to C, because you can 'break' only 1 danger pair, unless they have similar element (which can take place only by 3 items, because, in case of 4 and more 1 element would have to be neutral:

A->B->C, D

So without neutral elements, it's not solvable under that model.

If we take, that an element can be a danger for many, it's not going better:

A->B, A->C

this is solvable (removing A, than taking B and exchanging it for A, than taking C), but with any element more, it's unsolvable. Because you can either have A in boat, or have maximal 2 elements safe from A (one that you moved to the island in one step, the second in your boat).

So with 'simple' threatening rules (A can't be with B) it's solvable only for 3.

Answer 2

For another viewpoint, let's take the "classic" version, of A -> B, B -> C (that is, fox eats goose, goose eats beans) and add a D such that it neither threatens anything nor is threatened by anything (a rock, say), as in the "neutral" element of @Lukasz's answer. Now is it solvable? Well, let's see (\/ = boat):

  ABCD\/~~~~~~~~~~
  A CD  ~~~~~~~~~~\/ B
* A CD\/~~~~~~~~~~   B
* A C   ~~~~~~~~~~\/ B D
  A C \/~~~~~~~~~~   B D
  A     ~~~~~~~~~~\/ BCD
  AB  \/~~~~~~~~~~    CD
   B    ~~~~~~~~~~\/A CD
   B  \/~~~~~~~~~~  A CD
        ~~~~~~~~~~\/ABCD

As you can see, yes, it is solvable with two extra steps (marked with an *). Similarly, by adding more "neutral" elements and adding more extra steps, there is no limit on how many items you can have.

Note that there can only be two "predators" (objects that threaten other objects) because you can break a chain of two by removing one, but you can't break a chain of three by removing one:

A -> B -> C -> D            A -> B
                            C -> D
             !      (or)
A         C -> D            A  !
                            C -> D   

This is not true if they have the same "prey," since removing that prey breaks all chains. Note that, however, you can't have three predators for one prey, because you can only carry one item, and there will have to be an intermediate step with one of those predators with the prey (try it!).