Subject : Discrete Structures Consider a graph of a game board. Rounds in the ga
ID: 665685 • Letter: S
Question
Subject : Discrete Structures Consider a graph of a game board. Rounds in the game result in a token moved from a game board location to a game board location, possibly returning to the same one. Let the game board location at the end of a sequence of rounds determine the equivalence class into which a sequence falls. Note that game board locations are complete and non-overlapping. Using these equivalence classes, assume sequences having an infinite number of rounds can be classified into a finite number of equivalence classes. A) If a game board is finite, and we have for data only the final location of the token, can we distinguish, by means of the above equivalence classes, between an infinite number of sequences of rounds? B) Consider that the opposite of equivalent is distinct. If a collection of sequences of rounds in the game are all pairwise distinct, and there are an infinite number of such pairs, and the position on the board gives the equivalence class, can the game board be finite? please answer part a and part b for the same problem. thank youExplanation / Answer
(a) Let us take a look at the conditions given in the problem.
Game board if finite that means that there are only some finite many possible location of the token.
Now let us consider a case where the given game board has n positions.
This implies that there are only n possible final positions for a sequence of rounds, so you can distinguish at most n different sequences (and then only if they all end up with the token in different positions).
In particular, you cannot distinguish an infinite number of sequences of rounds.
(b)
The hypothesis states that you have an infinite number of sequence of rounds.
Thus implies that you have an infinite number of sequences of rounds, no two of which are identical.
Moreover, you can distinguish them by their final position on the board, so each must leave the token in a different position on the board.
Thus, the board cannot be finite.