Let A1, A2, A3, …, An be finite sets such that |Ai| is odd for all 1≤i≤n and |Ai∩Aj| is even for all 1≤i<j≤n. Prove that it is possible to pick one element ai in each set Ai so that a1, a2, …,an are distinct.
The best solution was submitted by Ilhee Kim (김일희) and Ringi Kim (김린기), Graduate Students, Princeton University.
Here is Solution of Problem 2011-16.
Alternative solutions were submitted by 강동엽 (전산학과 2009학번, +3, solution by 강동엽), 문상혁 & 박상현 (2010학번, +3), 장경석 (2011학번, +3), 이재석 (수리과학과 2007학번, +2). Three incorrect solutions were submitted by B. Kim, J. Lee, Y. Park.