For $kFor $k$ less than $n/2$, construct a bijection from the $k$-subsets of $n$ to the $(n-k)$-subsets, such that $x$ is a subset of $f(x)$.
This is a problem from a 2004 Google problem set, and answers have been posted, but could not find a good answer for this one.
 A: I believe an explicit construction can be given as follows:
Note that all we need to do is find a bijection $\displaystyle F$ from $\displaystyle k$-sets to $\displaystyle k$-sets such that $\displaystyle F(X) \cap X = \emptyset$.
Given such an $\displaystyle F$, we can construct the required bijection $\displaystyle f$ by taking $\displaystyle f(X) = [n] - F(X)$, where $\displaystyle [n] = \{1,2,\dots, n\}$ and we are constructing subsets of $\displaystyle [n]$.
Now to construct the bijection $\displaystyle F$. Write $\displaystyle 1,2,\dots n$ along a circle.
Now given a set $\displaystyle X = \{x_1, x_2, \dots, x_k\}$ where $\displaystyle x_1 \lt x_2 \lt \dots x_k$.
Start at $\displaystyle x_1$ and go along the circle clockwise, picking the first element not in the set $\displaystyle X$ (kind of like consistent hashing, if you are a programmer). Then go to $\displaystyle x_2$ and go along clockwise to pick the the first element not picked so far (and not in $\displaystyle X$) and so on.
These $\displaystyle k$ elements you picked form $\displaystyle F(X)$. It is easy to see that $\displaystyle X \cap F(x) = \emptyset$. 
We can also show that $\displaystyle F(X) \neq F(Y)$ if $X \neq Y$.
If $\displaystyle X = \{x_1, x_2, \dots, x_k\}$ and $x_1 \lt x_2 \dots$ and
if $\displaystyle Y = \{y_1, y_2, \dots, y_k\}$ and $y_1 \lt y_2 \dots$
Then suppose $j \gt 1$ is the smallest such that $\displaystyle x_j \neq y_j$ and assume $\displaystyle y_j \lt x_j$.
Now the above algorithm will either have picked $\displaystyle y_j$ to be in $\displaystyle F(X)$ or it would pick different numbers (for $\displaystyle F(X)$ and $\displaystyle F(Y)$) in the $\displaystyle j^{th}$ round.
If there is no such $\displaystyle j \gt 1$, then the sets only differ in the smallest element, and in which case, the resulting $\displaystyle F$ sets would be different too.

If we weren't worried about the exact construction, we can also give an existence proof.
The existence of a bijection can be shown by the following theorem:

Theorem: Every $\displaystyle k$-regular bipartite graph has a perfect matching.

This can be proven by induction on $\displaystyle k$ and using Hall's theorem.
You construct a bipartite graph with $\displaystyle k$-sets as the left partition and $\displaystyle n-k$-sets as the right partition.
Vertex $\displaystyle L_i$ is connected to $\displaystyle R_j$ iff $\displaystyle L_i \subset R_j$.
This is a $\displaystyle \binom{n-k}{n-2k}$ regular bipartite graph.
A: Here is a simple bijection. Make a string of $n$ parentheses by taking at position $i$ an opening parenthesis if $i$ is absent from the original $k$ subset, and a closing parenthesis if $i$ is present. Now certain parentheses in the string will properly match another one, while others don't. Let $S$ be the set of indices of unmatched parentheses. Focussing on the subword extracted at the positions of $S$, any opening parentheses in the subword comes after any closing parenthesis of the subword, since otherwise there would be at least one pair of matching parentheses in the subword, contrary to its construction. Also there are $(n-k)-k=n-2k>0$ more opening parentheses in the subword than closing parentheses, since the matching pairs that were excluded don't affect this balance.
Now the bijection consists of adding to the $k$ subset the first $n-2k$ elements of $S$ which have an opening parenthesis (meaning they are not yet in the $k$ subset). This turns these parentheses into closing parentheses. The key to the fact that this is a bijection is that this change does not change the unmatched status of the modified parentheses. Therefore the exact same construction on the $n-k$ subset produced will produce the same set $S$ of indices of unmatched parentheses, and now changing the last $n-2k$ closing parentheses at indices of $S$ will reconstruct the original situation (and the same reversal also applies if one starts out with a $n-k$ subset, makes a $k$ subset and then a $n-k$ subset again, showing one really has two mutually inverse procedures).
A: The map proposed in Aryabhata's answer is correct, but it seems that the proof of correctness they provided is lacking. In my answer, I will define a bijection $F$ from $k$-sets to $k$-sets such that $X\cap F(X)=\varnothing$, and prove that my map is bijective. I believe that my map will turn out to be the exact same mapping proposed by Aryabhata, just presented in a different way, but I will not prove this.
Imagine a class with $n$ schoolchildren numbered $1$ to $n$. Given a subset $X$ of $k$ children, we need to produce a disjoint subset of $k$ other children. Just like in Aryabhata's answer, we have the children stand in a circle, facing inward, so the numbers increase by one as you move clockwise.
Let's say that each of $k$ children in the subset is wearing a hat. Each child with a hat will look to their left, and if the child on their left is not wearing a hat, then they will pair off with the child on their left. Everyone with a hat who successfully paired off will leave the circle with their partner, causing the circle to shrink. Repeat this procedure until everyone with a hat has a partner; the set of partners will be $F(X)$.
This is a bijection because we can give the inverse mapping; you do the same procedure, except everyone looks to the right to find their partner.
