So now there's the paradox. You can prove with seemingly solid logic that **if someone plays a 4, then they must have had 4 and 5**.

So, the reason why this is not a paradox is that you didn't prove the bolded part. You've proved that, if your partner adheres to a particular decision rule, then the bolded part follows. And then, you've noticed that (a) this rule leads to optimal play if both parties know that it's followed, and (b), there seems to be a different rule that also leads to optimal play if it's followed.

Both of those things are true, but they're not a contradiction. You can have many rules that are optimal.

To be specific, there are six possible pairs of numbers you can have (left), and each one allows for two different plays (right)

(1,2) -> {1,2}

(2,3) -> {2,3}

(3,4) -> {3,4}

(4,5) -> {4,5}

(5,6) -> {5,6}

(6,7) -> {6,7}

A decision rule is any choice of one of the two numbers from the right sets for each pair on the left. (I.e., (1,2) -> 2, (2,3) -> 2, (3,4) -> 4 and so on is one rule.) If you want to follow a fixed decision rule such that your partner is always able to guess your card, there are two prerequisites:

(1) your rule must not choose any number for more than one pair (otherwise, your partner cannot identify your pair if that number is chosen)

(2) your partner must know what rule you are following.

One possible rule is:

(1,2) -> 2

(2,3) -> 3

(3,4) -> 4

(4,5) -> 5

(5,6) -> 6

(6,7) -> 7

This is the one you arrive at by 'forward induction', which was your first argument. Another possible rule is the one you arrive at if you apply the argument backward, i.e.,

(1,2) -> 1

(2,3) -> 2

(3,4) -> 3

(4,5) -> 4

(5,6) -> 5

(6,7) -> 6

But there are other rules as well. In total, there are 64 rules you can follow, and seven of them meet the first criterion, which means they can be optimal if your partner knows you're implementing them. (Take the sequence (1,2,3,4,5,6,7), delete any one number, make those six numbers your choices for the six pairs, in order; the resulting rule meets the fist criterion.) All of those seven rules are equally valid, and for each one, you can prove that they lead to optimal play, provided your partner knows which one you're following.