Proofs of Universal Statements: Mathematical Induction · The Method of Mathematical Induction
Lesson 10
Programming problem. One can prove that for any \(n \in \mathbb{Z}_{\ge1}\), from any set of \(2^{n+1}\) integers, one can choose \(2^{n}\) integers whose sum is divisible by \(2^{n}\). Implement a program that finds such a subset.
The first line contains an integer \(1 \le n \le 12\). The second line contains \(2^{n+1}\) integers \[1 \le a_{0}, a_{1}, \dotsc, a_{2^{n+1}-1}\le 10^{9}.\] Output \(2^{n}\) zero-based indices in increasing order.
Hint:
Typically, induction in programming is expressed through recursive calls. Think how one can find subsets divisible by \(2^{n-1}\) and manipulate them to obtain a subset divisible by \(2^{n}\).
Public samples
Input
2 2 3 5 6 3 3 1 10
Expected output
1 2 4 6