Problem

Source: Russian TST 2016, Day 9 P1 (Group NG), P3 (Groups A & B)

Tags: combinatorics



Several people came to the congress, each of whom has a certain number of tattoos on both hands. There are $n{}$ types of tattoos, and each of the $n{}$ types is found on the hands of at least $k{}$ people. For which pairs $(n, k)$ is it always possible for each participant to raise one of their hands so that all $n{}$ types of tattoos are present on the raised hands?