MathDB
Prove that the sum of the 8^n numbers considered is a multiple of n

Source: 2010 Peru Iberoamerican TST problem 1

May 9, 2023
combinatorics

Problem Statement

Let nn be a positive integer. We know that the set In={1,2,…,n}I_n = \{ 1, 2,\ldots , n\} has exactly 2n2^n subsets, so there are 8n8^n ordered triples (A,B,C)(A, B, C), where A,BA, B, and CC are subsets of InI_n. For each of these triples we consider the number ∣A∩B∩C∣\mid A \cap B \cap C\mid. Prove that the sum of the 8n8^n numbers considered is a multiple of nn. Clarification: ∣Y∣\mid Y\mid denotes the number of elements in the set YY.
Back to ProblemsView on AoPS