Problem 4

Part of 2006 Federal Math Competition of S&M

Problems(3)

guessing a polynomial (Serbia MO 2006 1st Grade P4)

Source:

Tatjana imagined a polynomial

P(x)

with nonnegative integer coefficients. Danica is trying to guess the polynomial. In each step, she chooses an integer

k

and Tatjana tells her the value of

P(k)

. Find the smallest number of steps Danica needs in order to find the polynomial Tatjana imagined.

algebrapolynomial

reversing coins in a row

Source: Serbia MO 2006 2nd Grade P4

n

coins aligned in a row. In each step, it is allowed to choose a coin with the tail up (but not one of the outermost markers), remove it and reverse the closest coin to the left and the closest coin to the right of it. Initially, all the coins have tails up. Prove that one can achieve the state with only two coins remaining if and only if

n-1

is not divisible by

3

gamecombinatorics

minimum # of questions to find arrangement of 7x7 board

Source: Serbia MO 2006 3&4th Grades P4

Milos arranged the numbers

1

49

into the cells of a

7\times7

board. Djordje wants to guess the arrangement of the numbers. He can choose a square covering some cells of the board and ask Milos which numbers are found inside that square. At least, how many questions does Djordje need so as to be able to guess the arrangement of the numbers?

gamecombinatorics