Wandering jinn

[Quizatzhaderac]

Say you have an l X m grid with n points that loops back on itself (like an RPG world map). l, m, and n are large. A number of the points are occupied by jinn. No two jinn can occupy the same point. With each tick of the clock a jinn can move up, down, left or right. It's possible for two jinn to switch places. Each jinn can see the whole grid and remember all previous states. You can set the initial configuration of the grid and give jinn instructions on how to move under the following restrictions:

• All jinn must have the same orders
• Each jinn must move with each tick
• Each jinn must have a genuine choice of at least two directions to move. If another jinn chooses a point it is not a genuine choice as they can't both be there.

What's the largest density of jinn achievable, and what initial configuration/ set of orders achieves it?

Best possible number:

Spoiler:

n/2. Each jinn most have at least two potential spaces in which to arrive at the next tick, in order to avoid two jinn choosing the same point.

An optimal solution:

Spoiler:

Place jinn solidly along every other row. Conceptually split the grid into (overlapping) 2 X 2 tiles with each djnn starting on the top left. Each jinn has the choice to move clockwise or counter clock wise.

Alternate version: Negative choice
Same basic set-up with different restrictions on the orders you can give the jinn.

• All jinn must have the same orders
• The jinn may potentially stand still
• Each jinn can refuse one direction to move in xor refuse to stay still.

I don't have an optimum solution to this (or know the optimum density). The best result I calculated:

Spoiler:

3n/4 Split the grid into non-overlapping 2 X 2 tiles, putting jinn into any three points on the tile. Define each position on the tile as 1 - 4 with 4 the empty point and each point clockwise to the previous point. Using the following orders by decreasing preference:

• If no jinn refuses to staying still, all stay still
• If no jinn refuses to go clockwise, all go clockwise
• If no jinn refuses to go counter-clockwise, all go counter-clockwise
• If two adjacent jinn refuses to stillness, switch them and other stays still
• If objector to stillness is next to empty space, move it to empty space.
• If jinn on 3 can move forward, 1 still, 2 & 3 forward
• switch jinn on two and three

[Trebla]

Some things are a little unclear to me. What does it mean that "All jinn must have the same orders"?

In your example case, does that mean that...

Spoiler:

If the first jinn chooses to go clockwise, then all subsequent jinn must choose to go clockwise? Do orders change between rounds or do they continue ad infinitum?

And what does it mean that each jinn must have at least 2 directions to move?

Spoiler:

And if we look at the example case
1 - 2 - 3
O O O
4 - 5 - 6
O O O

If #1 decides to move down, then when #4's turn arrives, he will only have one open square to move to (down). If #1 moves up, wrapping to the bottom, then when #4's turn arrives, he will only have one open square to move to again (up). Doesn't that violate the requirement that he must have two options?

You seem to assume simultaneity of moves, but it's unclear how that would occur. Given the sample scenario

O O O O O
O A x B O
O O O O O

Is it possible for either A or B to move to x? How will either know "If another jinn chooses a point it is not a genuine choice as they can't both be there. " If the moves are simultaneous?

[mfb]

Given your A x B scenario, you can demand that only one of the jinns may include "x" in his two options.

As the posted solution for the first case shows, the jinns don't need any data about the environment at all (except its global orientation) - they just decide to go CW or CCW in each step. Their neighbours have a different parity, therefore they will never run into their moves. The nearest jinns with the same parity have a distance of 2 and therefore disjoint 2x2-grids in which they move.


Concerning the variant, I don't understand which "communication" is possible there, as the spoiler suggest a lot of that.