Try this special variation on the game of Nim:
Put a pile of 42 stones on the table (although if you don't have 42, any multiple of six will do). Explain to your student that each turn, each of you will remove either 1, 3, or 5 stones, and the person who removes the last stone from a pile wins. Then, explain that the person who moves second has a winning strategy, and offer them a choice of who goes first. Most likely, they'll make you go first.
Then, challenge one of your students to win exactly six of seven games of this type (perhaps offering some sort of prize as a reward). You could also do four out of five, two out of three, as long as they have to try to lose at least one game. They'll probably figure out some time during the first six games that they can force a win by taking 6 stones minus however many you took, especially if they've seen this sort of thing before.
But when they try to lose the seventh game, they'll find it's impossible. Can you guess why?
Every turn when you take stones, you'll leave an odd number, and every turn when they take stones, they'll leave an even number. There's no way to break this pattern within the defined rules, and a consequence of this is that the person who moves second always wins (since 0 is an even number), no matter whether he follows any sort of strategy.
This introduces them to the idea of invariants. It's hard to know the exact level of theory you're looking for, but I think this is a good example purely from a discovery point of view, and doing something counterintuitive (being unable to lose a game even when you want to).