Both the easy and the hard subproblem can be solved by calculating the answers for small values of N (let's say, up to N=20) by brute-force, looking at the results and guessing how will the progression continue.
Our approach will be somewhat more rigorous:
Let's take any fixed number of cards (N) and assume that we've picked as many cards as possible. Let M be the greatest one among them.
The hard subproblem is a bit more tricky. We'll consider two cases:
N=2K: In order to achieve the maximum of floor(N/2)+1=K+1 cards, we need to take both card number 2K (otherwise, we would be picking cards only from the set 1 to (2K-1) and we already know that we can get at most K cards that way) and card K (the "singleton", as we have described it above).
If N=2, we are done; there is nothing left to choose from.
Otherwise, we consider the pairs {A,N-A} (where 1≤A<K). We have to pick exactly one member from each pair because we can't pick more than one, yet we need to pick K-1 of them in total.
Let's consider the first pair -- {1,N-1}. If N=4, we have two valid choices -- either we take {1,2,4} or {2,3,4}. Otherwise, assume that we took number 1. Then, we wouldn't be able to take neither K-1 (because (K-1)+1=K), nor K+1. In other words, we wouldn't be able to take any number from the pair {K-1,K+1}... a contradiction. Thus, we can't take number 1 and we are forced to take N-1.
Now, we can't pick (K-1), because K+(K-1)=N-1. Thus, we have to pick (K+1) from the pair {K-1,K+1}. We also cannot pick (K-2), because (K-2)+(K+1)=N-1. Therefore, we have to pick (K+2). Repeating this process demonstrates that we don't have any actual choice -- we are simply forced to take the numbers K,K+1,K+2, .... 2K=N. In other words, for even N greater than 4, there is only one way of taking the cards.
N=2K+1: For odd N up to 11, we'll use the brute-force approach to find that the numbers of solutions are 1,3,6,6,5,4. We'll now show that for odd N greater than 11, the number of solution is always 4.
We'll prove a slightly stronger statement -- that the solutions are of the form 1,3,5,...,2K+1=N or K,K+1,K+2,...,2K or K,K+2,K+3,...,2K+1 or K+1,K+2,...,2K+1. The proof will be based on mathematical induction, with K=5 (N=11) as its base. The base case is already proved, thanks to the exhaustive search.
It's obvious that if we want to pick the maximum number of cards (K+1), we'll need to pick either one or both of N and (N-1) cards. Picking just one of them leads to a solution in which the remaining K cards form a solution for the same problem with N'=N-2. Thus, using the inductive hypothesis, we know how they look like. Investigating the possible 8 combinations of "smaller solution" + "one card" shows that only two of them lead to valid solutions for N cards.
Thus, the only remaining candidates for solutions are those, where we pick both cards N and N-1 (which obviously implies we can't pick card number 1). Now, consider the pairs {2,N-2}, {3,N-3}, {4,N-4}, {5,N-5} (note that since 11≤N, all these pairs are distinct). As we have already mentioned more than once, we need to take exactly one number from each of these pairs. If we took 2, we wouldn't be able to take (N-3) (because (N-3)+2 = (N-1)). Then, we'd have to take 3 which would prevent us from taking N-3. Proceeding like this further, we'd be forced to take 4 and 5, which leads to a violation of the rule (as 2+3=5). Therefore, we have to take the card (N-2).
Now, consider the pair {K,K+1}. We have to take exactly one of these cards, but regardless of which one we take, it'll prevent us from taking card (K-1) (because (K-1)+K=N-2 and (K-1)+(K+1)=N-1). Thus, card (K-1) cannot be taken and we're forced to take the other card (K+2) from the pair {K-1,K+2}. However, this prevents us from taking card (K-2), which in turn implies we'll have to take the card (K+3), and so on. In the end, we'll be forced to take all the cards K+2,K+3,...,N and our only choice will be whether we take card K or K+1. This gives us the last remaining two solutions. Q.E.D.