ACM ICPC Philippines 2008: Problem A

.
2nd Philippine National Inter-Collegiate Programming Competition
(ACM Philippines 2008)
22 November 2008, Cebu City

Problem A: “Induction”
Input File: a.in

Introduction:

The following problem has appeared in several mathematical competitions before:

Show that any positive integer can be represented as a sum of one or more numbers of satisfying the following conditions

a) the numbers are of form (2^s)(3^r) where s and r are nonnegative integers, and

b) no summand is a factor of another summand.

The standard proof to the statement is as follows:

We prove the statement by induction.

Base Case:

If n = 1, then n = (2^0)*(3^0). If n = 2 then n = (2*)(3^0). If n = 3, then n = (2^0)*3

Inductive Step

We assume that the statement is true for all natural numbers less than n. We shall now prove that the statement is true for n.

Case 1: Assume that n is even.

Since n/2 is less than n, then n/2 has a representation that satisfies the conditions above. We just multiply the set of summands of n/2 by 2 and we use this as a representation for n.

Case 2: Assume that n is odd.

We find s such that 3^s is less than or equal to n which is less than or equal to 3^(s+1).

If n = 3^s , then we are already done.

If 3^s < m =" (n" m =" ((n" m =" <" n =" 2m">Task: Given a positive integer n, write a program that should output a set of numbers of the form: (2^s)(3^r) , (where s and r are nonnegative integers), satisfying the following conditions:

a) The sum of the numbers in the set is n.

b) No element in the set is a factor of another element in the set.

Sample Input / Sample Output

23 / Case 1: {8, 6, 9}

67 / Case 2: {16, 24, 27}

-----------------------------------------------------------------------------------

Problem Category: Moderate

Number of teams that have solved this problem: 8 (out of 39)

Success rate: 21%

For more information, contact: computingsoc@gmail.com
.