Q$3$ Hive Minds: Swarm Movement

You control $K$ insects, each of which has a specific target ending location $x_K.$ No two insects may

occupy the same square. In each time step all insects move simultaneously to a currently free square

$($or stay in place$)$; adjacent insects cannot swap in a single time step.

Q$3\mathrm{.}1$

Which of the following is the smallest correct state space representation?

A$.K$ tuples $((x_1,y_1),(x_2,y_2),$dots,$(x_K,y_K))$ encoding the $x$ and $y$ coordinates of each insect.

B$.K$ tuples $((x_1,y_1),(x_2,y_2),$dots,$(x_K,y_K))$ encoding the $x$ and $y$ coordinates of each insect, plus $K$

boolean variables indicating whether each insect is next to another insect.

C$.K$ tuples $((x_1,y_1),(x_2,y_2),$dots,$(x_K,y_K))$ encoding the $x$ and $y$ coordinates of each insect, plus $MN$

booleans indicating which squares are currently occupied by an insect.

D$.MN$ booleans $(b_1,b_2,$dots,$b_{MN})$ encoding whether or not an insect is in each square.

Q$3\mathrm{.}2$

What is the size of the above state space?

A$.MN$

B$.2^{MN}$

C$.KMN$

D$.(MN{)}^K$

E$.(MN{)}^K{2}^K$

F$.(MN{)}^K{2}^{MN}$

G$.2^{K}MN$

H$.2^{MNK}$