MathDB
Problems
Contests
International Contests
International Zhautykov Olympiad
2023 International Zhautykov Olympiad
3
3
Part of
2023 International Zhautykov Olympiad
Problems
(1)
Number of ways to write number as linear combination of others
Source: IZHO 2023 P3
2/6/2023
Let
a
1
,
a
2
,
⋯
,
a
k
a_1, a_2, \cdots, a_k
a
1
,
a
2
,
⋯
,
a
k
be natural numbers. Let
S
(
n
)
S(n)
S
(
n
)
be the number of solutions in nonnegative integers to
a
1
x
1
+
a
2
x
2
+
⋯
+
a
k
x
k
=
n
a_1x_1 + a_2x_2 + \cdots + a_kx_k = n
a
1
x
1
+
a
2
x
2
+
⋯
+
a
k
x
k
=
n
. Suppose
S
(
n
)
≠
0
S(n) \neq 0
S
(
n
)
=
0
for all big enough
n
n
n
. Show that for all sufficiently large
n
n
n
, we have
S
(
n
+
1
)
<
2
S
(
n
)
S(n+1) < 2S(n)
S
(
n
+
1
)
<
2
S
(
n
)
.
number theory
Polynomials