Có 4 bạn nam và 4 bạn nữ tham gia các dự án ngoại khóa. Biết rằng:
+ Mỗi người tham gia tối đa 2 dự án.
+ Bất kỳ cặp 1 nam và 1 nữ nào cũng làm chung với nhau ít nhất 1 dự án.
Chứng minh rằng có ít nhất 1 dự án có từ 2 bạn nam và 2 bạn nữ trở lên cùng tham gia.

Gọi bốn bạn nam là $B_1,B_2,B_3,B_4$ và bốn bạn nữ là $G_1,G_2,G_3,G_4$.

Với mỗi cặp $(G_i,B_j)$, do $G_i$ và $B_j$ cùng tham gia ít nhất một dự án, ta chọn một dự án mà cả hai cùng tham gia và ghi tên dự án đó vào ô $(i,j)$ của một bảng $4\times 4$.

Vì mỗi người tham gia tối đa 2 dự án nên trong mỗi hàng và mỗi cột của bảng có không quá 2 tên dự án khác nhau. Giả sử ngược lại rằng không có dự án nào có đồng thời ít nhất 2 bạn nam và ít nhất 2 bạn nữ. Khi đó, với mỗi dự án $D$, ta tô màu cho $D$ theo quy tắc:

- Tô xanh nếu $D$ có nhiều nhất 1 bạn nam.
- Nếu $D$ không được tô xanh, thì $D$ có ít nhất 2 bạn nam, nên theo giả sử phản chứng, $D$ có nhiều nhất 1 bạn nữ; khi đó tô $D$ màu hồng.

Như vậy mỗi dự án được gán đúng một màu, và mỗi ô của bảng mang màu của dự án được ghi trong ô đó. Bảng có 16 ô, nên theo nguyên lý Dirichlet, một trong hai màu xuất hiện ít nhất 8 lần.

Trường hợp 1: Có ít nhất 8 ô màu xanh.

Trong một hàng cố định, không thể có 3 ô màu xanh. Thật vậy, ba ô ấy nằm ở ba cột khác nhau, tức là liên quan đến ba bạn nam khác nhau. Vì một dự án màu xanh có nhiều nhất 1 bạn nam, nên ba ô xanh đó phải mang ba tên dự án khác nhau. Khi ấy bạn nữ tương ứng với hàng đó tham gia ít nhất 3 dự án, trái với giả thiết.

Vậy mỗi hàng có nhiều nhất 2 ô xanh. Nhưng tổng số ô xanh ít nhất là 8, nên cả bốn hàng đều có đúng 2 ô xanh.

Xét một hàng bất kỳ. Hai ô xanh trong hàng ấy phải mang hai tên dự án khác nhau. Hai ô còn lại là màu hồng; lấy một trong hai ô hồng đó. Dự án ghi trong ô hồng khác với cả hai dự án ở hai ô xanh, vì mỗi dự án đã được gán một màu duy nhất. Do đó bạn nữ của hàng này tham gia ít nhất 3 dự án, lại mâu thuẫn.

Trường hợp 2: Có ít nhất 8 ô màu hồng.

Lập luận hoàn toàn tương tự theo các cột. Trong một cột có đỉnh, không thể có 3 ô màu hồng, vì một dự án màu hồng có nhiều nhất 1 bạn nữ; do đó ba ô hồng ở ba hàng khác nhau phải tương ứng với ba dự án khác nhau, khiến bạn nam của cột ấy tham gia ít nhất 3 dự án.

Vì thế mỗi cột có nhiều nhất 2 ô hồng. Tổng số ô hồng ít nhất là 8, nên mỗi cột có đúng 2 ô hồng. Trong một cột, hai ô hồng tương ứng với hai dự án khác nhau, còn một ô xanh bất kỳ trong cột tương ứng với một dự án khác hai dự án ấy. Suy ra bạn nam của cột đó tham gia ít nhất 3 dự án, mâu thuẫn.

Cả hai trường hợp đều dẫn đến mâu thuẫn. Vậy giả sử phản chứng là sai.
Do đó tồn tại ít nhất một dự án có từ 2 bạn nam và 2 bạn nữ trở lên cùng tham gia.

Nhận xét.
Bằng lập luận tương tự, ta có thể tổng quát bài toán như sau: Với các số nguyên $a,b>1$, giả sử có $2(a-1)(b-1)+2$ bạn nam và $2(a-1)(b-1)+2$ bạn nữ tham gia, mỗi người tham gia không quá $a$ dự án. Khi đó, tồn tại ít nhất một dự án có $b$ bạn nam và $b$ bạn nữ trở lên cùng tham gia. Trường hợp $a=6$, $b=3$ ta được P3 IMO 2001.