The other half is much harder to solve. For a simple example - my client knows that there is an enemy player around a corner. It knows exactly where that player is, because that player is walking, and making noise. A cheats could allow the cheater to see his opponent's player's model through the wall.
For a more blatant example, consider cheats in a first-person shooter that just snap your aim to the nearest enemy's head. This involves zero violation of the game's logic, and also makes the game completely unplayable for everyone in a lobby.