Predicting the movement of people on a grid.

Question

Let there be a $30$ by $30$ grid that is there are $900$ tiles.The rows are numbered from 1-30 while the columns are numbered from (i) to (xxx). There are total of $100$ people and each of them is standing on a unique tile which means that $100$ tiles are occupied.
Every minute, each person moves to a predetermined tile and no person is standing on the same tile at the same minute. There is a specific pattern with which each person is moving which may or may not be same for each person.
We are given the names of the occupied tiles after every minute(for example, an occupied tile could be 1(i) or maybe 13(xxiv)). The problem is that we don't know which tile corresponds to which person neither do we know what is the pattern with which each of the person is moving. So my question is, if given the names of occupied tile after every minute continuously for $15$ minutes, how can we predict the occupied tiles in the $16^{\text{th}}$ minute?
Can this be solved by hand or do I have to use some programming language to solve it?

My question is influenced by this game.

Answer 1

This cannot be solved at all. For any occupation pattern (including the one after minute 15) there are at least two (why?) different possible occupation patterns for the next minute. It may just turn out that the movement patterns may be very complicated.

Answer 2

The game you want to solve has not a unique solution. The actual game is requiring you to reconstruct an algorithm based on its output. We expect the organizers of the context have chosen an algorithm which can be predicted (probably it is simple in some sense). If we don't have the output we cannot give you any hint...

The question is similar to the following: find the 6th term in the sequence: 1,2,4,7,11... Maybe you believe you have found the solution, but you cannot be mathematically sure about it.

Note, moreover, that contrary to your question, the algorithm is the same for all frogs (persons in your transliteration) and that it does not depend on the frog, but eventually only on its position.

Answer 3

One would need substantial restrictions on the algorithm followed by the actors to solve this. As stated this type of problem is almost always insoluble with certainty. The idea of the problem you linked to was to get as close as you can to predicting the answer, most likely by making some ad hoc simplifying assumptions (perhaps frogs only look at and move to nearby pads).

For instance, if one is given 15 distinct snapshots, and hence 14 data points of the form "state $A[i]$ $\to$ state $A[i+1]$", one can partially define the algorithm $X$ which tells each actor in a state $A[i]$ to move to a particular place in $A[i+1]$ depending on their position in the grid. (Thus this $X$ may be the same for all actors if you require this.) Then, since $A[15]$ is distinct from all previous entries, we are free to define $X$ to do whatever we want to $A[15]$.

This very straightforward trick doesn't work if there are repeated snapshots, but by cunningly considering the order in which the actors move I'm pretty sure you can extend it to this case because there are many more actors than snapshots. (Exercise: Construct an example set of snapshots with a smaller number of actors for which you can make the prediction with complete certainty. Can you find out a relation between the number of actors and number of snapshots which allows for the possibility of such an example?)

Answer 4

Hi I'm not sure if I understand this correctly. But think of the following: When constructing such an algorithm, you have to make sure that no two frogs happen to move to the same tile. This can e.g. be done easily, if the next tile is only determined by the current position of the frog (of course there are others, but maybe that algorithm has been used). To find out, you would have to find out, which position is the follow-up position for each tile. As the frogs are not marked and you can't directly find out, you would have to keep track of all the position (obviously, not by hand), e.g. tile (3,5) is always marked after tile (27/8) had been marked before. This would mean, that a frog on (3,5) always jumps to (27/8).

I'm not saying this is bound to be the algorithm, but it would be an easy way to avoid collisions. And since there are very many frogs, this would still be hard to find out.