Problem

Source: 2005 Estonia National Olympiad Final Round grade 12 p1

Tags: combinatorics



Punches in the buses of a certain bus company always cut exactly six holes into the ticket. The possible locations of the holes form a $3 \times 3$ table as shown in the figure. Mr. Freerider wants to put together a collection of tickets such that, for any combination of punch holes, he would have a ticket with the same combination in his collection. The ticket can be viewed both from the front and from the back. Find the smallest number of tickets in such a collection.