|
5.4. Inclusion–Exclusion
285
elements in
T
. Every other element in
S
is bigger than
a
and can’t divide it, but
divides an odd number of elements in
T
=
T
\ {
a
}
. Hence
T
suffices, completing
the induction and the proof of the lemma.
Now, write each number
n
>
1 in its prime factorization
n
=
p
a
1
1
p
a
2
2
· · ·
p
a
k
k
,
where the
p
i
are distinct primes and the
a
i
ate positive integers. Notice that the
color of
n
will always be the same as the color of
P
(
n
)
=
p
1
p
2
· · ·
p
k
.
Apply the lemma to the set
S
consisting of all
P
(
i
)
for
i
=
2, 3
, . . . ,
1000000
to find a subset
T
⊂
S
such that every element of
S
divides an odd number of
elements in
T
. For each
q
∈
S
, let
t
(
q
)
equal the number of elements in
T
that
q
divides, and let
u
(
q
)
equal the number of primes dividing
q
.
Select all the numbers in
T
, and consider how the color of a number
n
>
1
changes. By the inclusion–exclusion principle, the number of elements in
T
not
relatively prime to
n
equals
q
|
P
(
n
),
q
>
1
(
−
1
)
u
(
q
)
+
1
t
(
q
).
If
x
∈
T
and either gcd
(
x
,
P
(
n
))
or equivalently gcd
(
x
,
n
)
is divisible by
exactly
m
primes, then it is counted for all
q
>
1 that divide gcd
(
x
,
P
(
n
))
. Thus
it is counted
m
1
−
m
2
+
m
3
− · · · =
1 time in the sum. (For example, if
n
=
6,
then the number of elements in
T
divisible by 2 or 3 equals
t
(
2
)
+
t
(
3
)
−
t
(
6
)
.)
By the definition of
T
, each of the values
t
(
q
)
is odd. Because there are 2
k
−
1
divisors
q
>
1 of
P
(
n
)
, the above quantity is the sum of 2
k
−
1 odd numbers and
is odd itself. Therefore after selecting
T
, every number
n
>
1 will switch color
an odd number of times and will turn white.
Finally, select 1 to turn 1 white to complete the process.
Note.
In fact, a slight modification of the above proof shows that
T
is unique if
you restrict it to square-free numbers. With some work, this stronger result implies
that there is in essence exactly one way to make all the numbers white up to trivial
manipulations.
Second solution.
Yes, it is possible. We prove a more general statement, where
we replace 1000000 in the problem by some arbitrary positive integer
m
. We also
focus on the numbers divisible by just a few primes instead of all the primes.
Lemma.
For a finite set of distinct primes S
= {
p
1
,
p
2
, . . . ,
p
n
}
, let Q
m
(
S
)
be
the set of numbers between
2
and m divisible only by primes in S. The elements
of Q
m
(
S
)
can be colored black or white. A permissible move consists in selecting
a number in Q
m
(
S
)
and changing the color of that number and each number
not relatively prime to it. Then it is possible to reverse the coloring of Q
m
(
S
)
by
selecting several numbers in a subset R
m
(
S
)
⊆
Q
m
(
S
)
.
286
II Solutions, 5. Basic Principles in Number Theory
Proof.
We prove the lemma by induction on
n
. If
n
=
1, then selecting
p
1
suffices.
Now suppose
n
>
1, and assume without loss of generality that the numbers are
all black to start with.
Let
T
= {
p
1
,
p
2
, . . . ,
p
n
−
1
}
, and define
t
to be the largest integer such that
t p
n
≤
m
. We can assume
t
≥
1 because otherwise we could ignore
p
n
and just
use the smaller set
T
, and we’d be done by our induction hypothesis.
Now select the numbers in
R
m
(
T
),
R
t
(
T
)
, and
p
n
R
t
(
T
)
= {
p
n
x
|
x
∈
R
t
(
T
)
}
, and consider the effect of this action on a number
y
:
•
y
is not a multiple of
p
n
. Selecting the numbers in
R
m
(
T
)
makes
y
white.
If selecting
x
∈
R
t
(
T
)
changes
y
’s color, selecting
x p
n
will change it back,
so that
y
will become white.
•
y
is a power of
p
n
. Selecting the numbers in
R
m
(
T
)
and
R
t
(
T
)
has no effect
on
y
, but each of the
|
R
t
(
T
)
|
numbers in
x R
t
(
T
)
changes
y
’s color.
•
p
n
|
y
but
y
is not a power of
p
n
. Selecting the numbers in
R
m
(
T
)
makes
y
white. Because
y
=
p
i
n
, it is divisible by some prime in
T
, so selecting
the numbers in
R
t
(
T
)
makes
y
black again. Finally, each of the
|
R
t
(
T
)
|
numbers in
x R
t
(
T
)
changes
y
’s color.
Therefore, all the multiples of
p
n
are the same color (black if
|
R
t
(
T
)
|
is even,
white if
|
R
t
(
T
)
|
is odd), while all the other numbers in
Q
m
(
S
)
are white. If the
multiples of
p
n
are still black, we can select
p
n
to make them white, and we are
done.
We now return to the original problem. Set
m
=
1000000, and let
S
be the set
of all primes under 1000000. From the lemma, we can select numbers between 2
and 1000000 so that all the numbers 2
,
3
, . . . ,
1000000 are white. Finally, com-
plete the process by selecting 1.
Third solution.
Define
P
(
n
)
as in the first solution and note that
n
and
P
(
n
)
are
always the same color. Fix
n
=
p
1
p
2
· · ·
p
k
square-free and consider the effect of
selecting in succession every divisor
q
>
1 of
n
. If
s
is divisible by exactly
m
of
the
p
i
, then 2
k
−
m
divisors of
n
are relatively prime to
s
, and thus the color of
s
is changed by 2
k
−
2
k
−
m
choices of
q
. This is even unless
m
=
k
. Thus the net
effect of choosing all these values of
q
is to change the color of all multiples of
n
and only these.
Now we argue by induction on
n
that for any
n
we can make every number
1
,
2
, . . . ,
n
white. For
n
=
1, we simply choose 1. For the inductive step, suppose
we have found a way to make 1
,
2
, . . . ,
n
−
1 white and we wish to make
n
white. If it is already white, then we are done. If it is black, then
n
is square-free
(otherwise
n
and
P
(
n
) <
n
are the same color; hence white), and hence applying
the construction above, we can change the color of every multiple of
n
. This leaves
1
,
2
, . . . ,
n
−
1 white and flips
n
to make it white.
6
Arithmetic Functions
6.1
Multiplicative Functions
Problem 6.1.6.
Let f be a function from the positive integers to the integers sat-
isfying f
(
m
+
n
)
≡
f
(
n
) (
mod
m
)
for all m
,
n
≥
1
(e.g., a polynomial with
integer coefficients). Let g
(
n
)
be the number of values (including repetitions) of
f
(
1
),
f
(
2
), . . . ,
f
(
n
)
divisible by n, and let h
(
n
)
be the number of these values
relatively prime to n. Show that g and h are multiplicative functions related by
h
(
n
)
=
n
d
|
n
μ(
d
)
g
(
d
)
d
=
n
k
j
=
1
1
−
g
(
p
j
)
p
j
,
where n
=
p
α
1
1
· · ·
p
α
k
k
is the prime factorization of n.
(American Mathematical Monthly)
Solution.
Let
m
and
n
be positive integers such that gcd
(
m
,
n
)
=
1 and let 1
≤
a
≤
m
, 1
≤
b
≤
n
. From the Chinese remainder theorem and the properties
of
f
it follows that
m
|
f
(
a
)
and
n
|
f
(
b
)
if and only if
mn
|
f
(
x
)
, where
x
=
x
(
a
,
b
)
is the unique integer such that
x
≡
a
(
mod
m
)
,
x
≡
b
(
mod
n
)
, and
1
≤
x
≤
min
{
m
,
n
}
. Thus
g
is multiplicative. For
d
|
n
, the number of values
of
f
(
1
), . . . ,
f
(
n
)
divisible by
d
is just
n
d
g
(
d
)
. By a straightforward inclusion–
exclusion count,
h
(
n
)
=
n
−
k
i
=
1
n
p
i
g
(
p
i
)
+
1
≤
i
<
j
≤
k
n
p
i
p
j
(
p
i
p
j
)
− · · ·
,
and we get
h
(
n
)
=
n
k
j
=
1
1
−
g
(
p
j
)
p
j
.
© Birkhäuser Boston, a part of Springer Science + Business Media, LLC 2009
T. Andreescu and D. Andrica,
Number Theory
,
DOI: 10.1007/b11856_17,
287
288
Do'stlaringiz bilan baham: |
