MathDB

\definecolor{A}{RGB}{70,255,50}\color{A}\fbox{C6.} There are

n

\definecolor{A}{RGB}{0,0,255}\color{A}\text{boys} and

n

\definecolor{A}{RGB}{255,0,255}\color{A}\text{girls} in a club. Some of them are friends with each other. The \definecolor{A}{RGB}{0,0,255}\color{A}\text{boys} want to get into a relationship, so some subset of them wants to ask some \definecolor{A}{RGB}{255,0,255}\color{A}\text{girls} out for a trip. Because the \definecolor{A}{RGB}{0,0,255}\color{A}\text{boys} are shy, for a nonempty set

B

of \definecolor{A}{RGB}{0,0,255}\color{A}\text{boys}, they want to make sure that each of the girl they ask out is friend with one of the \definecolor{A}{RGB}{0,0,255}\color{A}\text{boys} in

B

. If the number of \definecolor{A}{RGB}{255,0,255}\color{A}\text{girls} they are able to ask out is smaller than the number of the \definecolor{A}{RGB}{0,0,255}\color{A}\text{boys} in

B

, then the nonempty set

B

of those \definecolor{A}{RGB}{0,0,255}\color{A}\text{boys} is called a group of complete losers. Show that for any

0 \le k < 2n

, there exists an arrangement of the friendships among those

2n

people so that there are exactly

k

groups of complete losers.
Proposed by [color=#419DAB]ltf0501. [color=#3D9186]#1737

Problem Statement