MathDB
Problems
Contests
National and Regional Contests
PEN Problems
PEN O Problems
29
29
Part of
PEN O Problems
Problems
(1)
O 29
Source:
5/25/2007
Let
A
A
A
be a set of
N
N
N
residues
(
m
o
d
N
2
)
\pmod{N^2}
(
mod
N
2
)
. Prove that there exists a set
B
B
B
of
N
N
N
residues
(
m
o
d
N
2
)
\pmod{N^2}
(
mod
N
2
)
such that the set
A
+
B
=
{
a
+
b
∣
a
∈
A
,
b
∈
B
}
A+B=\{a+b \vert a \in A, b \in B \}
A
+
B
=
{
a
+
b
∣
a
∈
A
,
b
∈
B
}
contains at least half of all the residues
(
m
o
d
N
2
)
\pmod{N^2}
(
mod
N
2
)
.
modular arithmetic
induction
ceiling function
inequalities
number theory