MathDB

2^(n-1) subsets, every three have a common element

Source: Bundeswettbewerb Mathematik 1972, round 1, problem 3

May 1, 2007

inductioncombinatorics proposedcombinatorics

Problem Statement

2^{n-1}

subsets are choosen from a set with

n

elements, such that every three of these subsets have an element in common. Show that all subsets have an element in common.