I think this problem can be solved by condition.

Interesting fact (is there a pure combinatorial solution?) but strange choice for №8 and very strange that nobody did it at the contest. Explcit formula for number of surjective maps + Euler's theorem make it straightforward. Maybe contestants didn't know explicit formula? (but certainly they could find it)

many participants made the same mistake as you. $k\leq 2^n$, but not $\leq n+2$.

oh, such a silly mistake Well, we can reduce the problem to the case k=n by combinatorial argument and then use that computation. That's cool. (I found that reduction immediately trying to find pure combi solution. Suddenly it turns out to be very useful)

I would like to know the details of this, because I don't know a purely combinatorial solution

The same with me. I mean just that: Cyclic shift of enumeration of cards makes a new distribution of cards. Consider orbits of this action. Their lengths are divisible by 2^k unless all k sets of cards are stable undo the 2^k-shift. So we can consider only these distributions. But these distributions are bijective with arbitrary distributions of 2^k cards/ So we can suppose k=n. Rest of solution is as in mahanmath's post.

...This comment was wrong...

and what about about your=official solution? (or maybe you want to get it from mathlinkers:) )

Stop! What is the $2^k$-shift, if $k>n$?

ooops, it's the same mistake,sorry (( just such an unusual notation? when k>n...

Why isn't there a clear solution to this? Basically, the number of ways is the same as those for choosing $k-1$ objects out of $2^n-1$ and we want to find the exponent of $2$ in this, which is straightforward by Lucas-Kummer Theorem.

anantmudgal09 wrote: Why isn't there a clear solution to this? Basically, the number of ways is the same as those for choosing $k-1$ objects out of $2^n-1$ ... No, it is not the same.

Why so? Isn't this just the stars and bars thing? Sorry if this is a silly query. Okay, I get the point now, not all of the cards are to be given, so it is a summation of binomial coefficients.

See here: https://lirias.kuleuven.be/bitstream/123456789/266662/1/Lengyel.pdf

I don't see how the induction step can be completed when $k$ is even, since we have no control over $(k+1)^{2^n}$ mod $2^{2^n}$

OK, it was 10 years ago. Let's post oficial solution. Suppose the children are numbered from 1 to $k$. We denote by $S(2^n, k)$ the number of distributions in question. Two statements about $S(2^n, k)$: $$ \text{$2^{k-1}$ divides $S(2^n, k)$} \eqno{(\mathcal E_{n,k})} $$and $$ \\ \text{$2^{k}$ does not divide $S(2^n, k)$} \eqno{(\mathcal F_{n,k})} $$will be proved by induction in $n$ (for all $k$ at once). \smallskip The base $n=0$ is obvious since $S(2^0, 1)=1$. The induction step from $n$ to $n+1$. We call {\it red} the cards with numbers 1, 2, \dots, $2^n$, and {\it green} all the rest. Each distribution of $2^{n+1}$ cards can be considered as a distribution of red cards and a distribution of green cards, with additional requirement that each child gets a card of at least one colour. Case 1: $k\leq 2^n$. We arbitrarily choose two non-empty sets $A$ and $B$ of children receiving red and green cards. Then $$ S(2^{n+1}, k)=\sum_{|A\cup B|=k}S\bigl(2^n, |A|\bigr)\cdot S\bigl(2^n, |B|\bigr). $$ To prove the statement $\mathcal E_{n+1,k}$ we apply hypothesis to the right-hand side. We find that each term is divisible by $2^{|A|-1+|B|-1}$ and therefore by $2^{k-2}$. It remains to note that each term except one occurs exactly twice in this sum, because the sets $A$ and $B$ are interchangeable. The only exception is formed by the pair $A=B=\{1, 2, \dots, k \}$, but the corresponding term is divisible by $2^{k-1}\cdot 2^{k-1}$. To prove $\mathcal F_{n+1,k}$ we need to count the terms divisible by $2^{k-2}$ exactly. The number of these terms is equal to the number of ways to divide $\{1, 2, \dots, k \}$ into two disjoint sets $A$ and $B$, that is, $$ \binom{k}1+\binom{k}2+\binom{k}3+\dots+\binom{k}{k-1}=2^k-2. $$Thus $$ S(2^{n+1}, k)=\!\!\!\sum_{|A\cup B|=k}\!\! S\bigl(2^n, |A|\bigr)\cdot S\bigl(2^n, |B|\bigr)\equiv 2^{k-2}\cdot(2^k-2)\equiv 2^{k-1}\!\!\!\!\!\pmod {2^k}. $$ Case 2: $k > 2^n$. Following the above argument we can apply the hypothesis only when $|A|, |B|\leq 2^n$. In fact, however, the statement $\mathcal E_{n,k}$ is also true when ${k>2^n}$, because in this case $2^{k-1}$ divides $S(2^n, k)=0$. Thus in the present case the proof of $\mathcal E_{n+1,k}$ requires no modification. To prove $\mathcal F_{n+1,k}$ we count the terms divisible by $2^{k-2}$ exactly. The number of these terms is equal to the number of ways to divide $\{1, 2, \dots, k \}$ into two disjoint sets $A$ and $B$, containing at most $2^n$ elements each, that is, $\binom{k}{k-2^n}+\binom{k}{k-2^n+1}+\dots+\binom{k}{2^n}$. As in the case 1, we need to know only the residue of this number modulo 4. Using the identities $\binom{k}{\ell}=\binom{k-1}{\ell-1}+\binom{k-1}{\ell}$ and $\binom{k-1}{\ell}=\binom{k-1}{k-1-\ell}$ we obtain \[ \binom{k}{k-2^n}+\binom{k}{k-2^n+1}+\dots+\binom{k}{2^n} = \left(\binom{k-1}{k-2^n-1}+\binom{k-1}{k-2^n}\right)+ \left(\binom{k-1}{k-2^n}+\binom{k-1}{k-2^n+1}\right)+\dots + \left(\binom{k-1}{2^n-1}+\binom{k-1}{2^n}\right) \equiv \binom{k-1}{k-2^n-1}+\binom{k-1}{2^n}\equiv 2 \binom{k-1}{2^n}\pmod 4. \]It remains to check that for each $m$, $2^n\leq m<2^{n+1}$, the number $\binom{m}{2^n}$ is odd. It follows from the expansion $$ \binom{m}{2^n}=\frac{m}{m-2^n}\cdot\frac{m-1}{m-1-2^n}\cdots\frac{2^n+2}{2}\cdot\frac{2^n+1}{1}.$$ Thus $$S(2^{n+1}, k)\equiv 2^{k-1}\pmod {2^k}.$$