Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

A1
...

a b
2018
Answer
...

Solution
...
If both a and b are
divisible by 1009, say with a = 1009q, b = 1009r, then we have 2(q + r) = 3qr
...
This leads to the solutions
q = 1, r = 2 and r = 1, q = 2, corresponding to the ordered pairs (a, b) = (1009, 2018)
and (a, b) = (2018, 1009)
...
This
yields 2 · 1009(1009q + b) = 3 · 1009qb, which can be rewritten as
2 · 1009q = (3q − 2)b
...
Then 1009k + 2 = 3 · 336k + k + 2 is divisible by 3, so
k ≡ 1 (mod 3)
...
For k = 4,
we get q = 1346, a = 1009 · 1346, b = q/2 = 673
...
Assuming there is one, the corresponding value of q is greater than 1346,
and so the corresponding
2q
· 1009
b=
3q − 2
is less than 673
...

b
672
2018
a b
2018
Finally, along with the two ordered pairs (a, b) for which a is divisible by 1009 and b
is not, we get two more ordered pairs by interchanging a and b
...
Let S1 , S2 ,
...
, n} in some order, and let
M be the (2n − 1) × (2n − 1) matrix whose (i, j) entry is
(
0 if Si ∩ Sj = ∅;
mij =
1 otherwise
...

Answer
...

Solution
...
, n} in a different
order, this will replace the matrix M by P M P −1 for some permutation matrix P ,
and the determinant will stay unchanged
...
Then we will show that det(Mn+1 ) = −(det(Mn ))2 , from which
the given answer follows by induction on n because M1 has the single entry 1
...
, S2n −1 for the nonempty subsets of {1, 2,
...
, n + 1} in the order
S1 , S2 ,
...
, S2n −1 ∪ {n + 1}
...
, n + 1}, whether they have

nonempty intersection is completely determined by the relevant entry in Mn
...
To
find det(Mn+1 ), we subtract the middle row from each of the rows below it
...
Then we
can expand the determinant using the middle column (whose only nonzero entry is
now the “central” 1) to get




Mn Mn
Mn O
det(Mn+1 ) = det
= − det
,
Mn O
Mn Mn
where the last step is carried out by switching the ith row with the (2n − 1 + i)th row
for all i = 1, 2,
...
(Because this is an odd number of row swaps, the sign of
the
is reversed
...

A3
...
, x10

i=1

satisfying

10
P

cos(xi ) = 0
...

49
Solution
...
Then the real numbers z1 , z2 ,
...
Also, note that

Answer
...

Thus we can rephrase the problem as follows: Find the maximum value of the
function f given by
f (z1 ,
...
, z10 ) ∈ [−1, 1]10 | z1 + · · · + z10 = 0}
...
, m10 ) ∈ S
...
If we fix z3 = m3 ,
...
, m10 ) − (m33 + · · · + m310 ) = z 3 + (a − z)3 = a3 − 3a2 z + 3az 2
4
has a global maximum at z = m1 on the interval for z that corresponds to
(z, a − z, m3 ,
...
If a ≥ 0 that maximum occurs at both endpoints of the interval
(that is, when either z = 1 or a − z = 1), while if a < 0 the maximum occurs when
z = a − z = a/2
...
Repeating this argument for other pairs
of subscripts besides (1, 2), we see that whenever two of the mi are distinct, one of
them equals 1
...
Suppose that 1 occurs d times among the mi , so that v occurs
10 − d times
...
, m10 ) = 4 · d · 13 + 4 · (10 − d) ·
= 4d −
= h(d), say
...
So
to finish, we can make a table of values
d h(d)
0
0
1 320/81
2 15/2
3 480/49
4 80/9
5
0
and read off that the maximum value is 480
= 9 39
, for d = 3
...
)
A4
...
, n
...
Show that gh = hg
...
)
Solution
...
If n = 1, we have a1 = m and ghm = e,
so g = h−m and g, h commute
...
Then each ak is 0 or 1, and a1 + · · · + an = m
...
km of k for
which ak = 1 are the smallest values for which
mk
mk
mk
≥ 1,
≥ 2,
...
, km =
= n
...

Taking the inverse of both sides, we get
h−1 (g −1 )km −km−1 · · · h−1 (g −1 )k2 −k1 h−1 (g −1 )k1 = e
...
Because
m < n, it will follow by the induction hypothesis that h−1 and g −1 commute, and
thus g and h commute
...
, bm−1 = k2 − k1 , bm = k1 ,
and so, with the convention k0 = 0, we have

 

(m − i + 1)n
(m − i)n
bi = km−i+1 − km−i =
−
m
m

 

(m − i + 1)n
(m − i)n
=− −
+ −
m
m
 


(i − 1)n
in
−n −
−n
=
m
m
  

in
(i − 1)n
=
−
,
m
m
as desired
...
Write m = qn+r with 0 ≤ r < n
...
If we set g 0 = ghq then we have
n
n
0

0

0

g 0 ha1 g 0 ha2 · · · g 0 han = gha1 gha2 · · · ghan = e
...
So by the case considered above, g 0 and h commute
...

A5
...
Show that there exist a positive integer n and a real
number x such that f (n) (x) < 0
...
Suppose, to the contrary, that f (n) (x) ≥ 0 for all integers n ≥ 0 and all
x ∈ R
...
Now we show by
induction on n that for every function f satisfying the given conditions and such that
f (n) (x) ≥ 0 for all n ≥ 0 and all x, we have f (2x) ≥ 2n f (x) for all n ≥ 0 and all x ≥ 0
...
Suppose

we have shown for some particular n that f (2x) ≥ 2n f (x) for all relevant functions
f and all x ≥ 0
...
Therefore, we can
define a function g by g(x) = f 0 (x)/f 0 (1), and for this infinitely differentiable function
we have that g(0) = 0, g(1) = 1, and all derivatives of g are nonnegative
...
Integrating with respect to x from 0 to y gives 12 f (2y) ≥ 2n f (y) for all
y ≥ 0, so this shows that f (2x) ≥ 2n+1 f (x) for all x ≥ 0, completing the induction
proof
...
So it must be the case that f (n) (x) < 0 for some integer n ≥ 0 and some x ∈ R
...
Suppose that A, B, C, and D are distinct points in the Euclidean plane no three of
which lie on a line
...

NOTE: I don’t believe this is quite the final wording of this problem
...
Let v, w, z be the displacement vectors AB, AC, AD from A to the points
B, C, D respectively
...

Because A, B, and C are not collinear, v and w form a basis for R2 , so there
are constants λ, µ ∈ R such that z = λv + µw
...
The determinant (v · v)(w · w) − (v · w)2 of the matrix of this system is
positive (because v and w are linearly independent) by the Cauchy-Schwarz inequality
...

Now we can rewrite the desired quotient as
 1
area(4ABC)
| det(v w)|/2 
det(v w)
  
=
=
 =  ,
area(4ABD)
| det(v z)|/2
λ det(v v) + µ det(v w)
µ
a rational number
...
)
(The B section starts on the next page
...
Let P be the set of vectors defined by
  

a 
P=
 0 ≤ a ≤ 2, 0 ≤ b ≤ 100, and a, b ∈ Z
...

 
1
Answer
...

b
Solution
...
Thus if the set P \ {v} is to be partitioned into two sets of equal
3 · 50 · 101


 
303
a
sum, the vector
− v must have both coordinates even
...
It remains to show that this
 necessary condition on v is also sufficient
...
Given a
d
 
1
particular vector v =
in P with b even, there are 302 lattice points in P \ {v}
...
, P302 such that the sum of the displacement
# » # »
#
»
vectors P1 P2 , P3 P4 ,
...
To do so, we first partition the set P \ {v} into 24 rectangular
sets of 4 × 3 lattice points, along with a single 5 × 3 rectangular set from which one
of the points in the middle column is missing
...
For the 5 × 3 rectangular set with a
single point missing, there are (up to symmetry) two cases, depending on whether
the missing point is on an edge or at the center (the parity condition on b guarantees
that it will be either on an edge or at the center)
...
As an example, if the 5 × 3 rectangle is the set
  

a 
 0 ≤ a ≤ 2, 0 ≤ b ≤ 4, and a, b ∈ Z
b
 
1
and v =
is the missing point, then the second diagram corresponds to the
0
partition of the rectangular set minus that point into the two subsets of equal size
and equal sum
{(0, 0), (0, 2), (0, 4), (1, 2), (2, 4), (2, 2), (2, 1)} and
{(0, 1), (0, 3), (1, 4), (1, 1), (2, 3), (1, 3), (2, 0)},
which contain the starting and end points, respectively, of the displacement vectors
shown
...
Let n be a positive integer, and let fn (z) = n + (n − 1)z + (n − 2)z 2 + · · · + z n−1
...

P
P
Solution
...



n
n
X
 X

j
z ≤
|z|j ≤ n, with equality only
On the other hand, when |z| ≤ 1, we have 


j=1

j=1

for z = 1
...

B3
...

Answer
...

Solution
...
If a divides b then we can write b = aq, and modulo 2a − 1 we then
have 2b − 1 = (2a )q − 1 ≡ 1q − 1 = 0
...

Let b = aq + r with 0 ≤ r < a; we then have 2b − 1 = 2r (2aq − 1) + (2r − 1)
...
Because 0 ≤ r < a, it
follows that r = 0, so a divides b
...
So we may assume that
m
n = 2m for some nonnegative integer m
...
So we may assume
l
that m = 2l , that is, n = 22 , for some nonnegative integer l, and we have to find all
n < 10100 of this form for which n − 2 divides 2n − 2
...
We can write l = 2k , so that n = 22 , and to finish we have
to find the values of k ≥ 0 for which n < 10100
...
Then we have 2m = n < 10100 <
4 100
(2 )
= 2400
...
Conversely, 22 = 22 = 2256 < 2300 = (23 )100 < 10100
...

B4
...
Prove that if xn = 0 for some n, then the sequence is
periodic
...
Let z be a (complex) root of the polynomial z 2 − 2az + 1
...
If the Fibonacci numbers F0 , F1 , F2 ,
...
We now show by induction on n that this equation holds for all n
...

Suppose that xn = 0 for some n, say xm = 0
...
Now note that the Fibonacci sequence modulo d is periodic:
There are only finitely many (specifically, d2 ) possibilities for a pair (Fi mod d, Fi+1
mod d) of successive Fibonacci numbers modulo d, and when a pair reoccurs, say
(Fi mod d, Fi+1 mod d) = (Fj mod d, Fj+1 mod d) with i < j, it is straightforward to
show by induction that Fi+k = Fj+k mod d for all k, including negative k for which
z Fn + z −Fn
i + k ≥ 0
...

=

B5
...
Suppose that

2
1 ∂f1
∂f2
∂f1 ∂f2
>0
−
+
∂x1 ∂x2 4 ∂x2 ∂x1
everywhere
...

Solution
...


∂f2
∂x2

From the givens, the entries of A are positive everywhere, and the determinant of A is
also positive everywhere
...
That is, for any
nonzero vector v, we have vT Av = v·Av > 0, so vT (J +J T )v = vT Jv+(vT Jv)T > 0
...

We now show that if P and Q are distinct points in R2 , then the dot product of the
#
»
# »
displacement vectors P Q and f (P )f (Q) is positive; it then follows that f (P ) 6= f (Q),
showing that f is one-to-one
...

#
»
In particular, the displacement vector f (P )f (Q) can be written as
1
#
»
# » 
f (P )f (Q) = f (Q) − f (P ) = f (P + tP Q)
t=0

d h
# »i
=
f (P + tP Q) dt
0 dt
Z 1
# » # »
J(P + tP Q) P Q dt,
=
Z

1

0

# »
using the multivariable chain rule
...
By our earlier observation, the integrand is positive for all t, and so
the integral is also, completing the proof
...
Let S be the set of sequences of length 2018 whose terms are in the set {1, 2, 3, 4, 5, 6, 10}
and sum to 3860
...

2048
Solution
...

2048
2
We can interpret this as the probability that a random variable X takes on a value in
the set A = {1, 2, 3, 4, 5, 6, 10}, if the possible values of the variable are all the positive
∞
P
integers, and the probability of taking on the value k is 2−k
...
)
2018
Now consider a sequence X = (Xn )n=1 of independent random variables that
each take positive integer values k with probability 2−k
...
Therefore, the probability that the sequence
(Xn ) will be in S is
P(X ∈ S) = |S| · 2−3860
...
So we have the inequality

2018
2018
−3860
|S| · 2
= P(X ∈ S) <
,
2048
and the desired result follows

---