MathDB
Problems
Contests
National and Regional Contests
Taiwan Contests
TST Round 2
2020 Taiwan TST Round 2
4
4
Part of
2020 Taiwan TST Round 2
Problems
(1)
Games in Quarantine
Source: 2020 Taiwan TST Round 2 Mock Exam 4
5/2/2020
Alice and Bob are stuck in quarantine, so they decide to play a game. Bob will write down a polynomial
f
(
x
)
f(x)
f
(
x
)
with the following properties:(a) for any integer
n
n
n
,
f
(
n
)
f(n)
f
(
n
)
is an integer; (b) the degree of
f
(
x
)
f(x)
f
(
x
)
is less than
187
187
187
.Alice knows that
f
(
x
)
f(x)
f
(
x
)
satisfies (a) and (b), but she does not know
f
(
x
)
f(x)
f
(
x
)
. In every turn, Alice picks a number
k
k
k
from the set
{
1
,
2
,
…
,
187
}
\{1,2,\ldots,187\}
{
1
,
2
,
…
,
187
}
, and Bob will tell Alice the value of
f
(
k
)
f(k)
f
(
k
)
. Find the smallest positive integer
N
N
N
so that Alice always knows for sure the parity of
f
(
0
)
f(0)
f
(
0
)
within
N
N
N
turns.Proposed by YaWNeeT
algebra
polynomial
Taiwan