MathDB
Problems
Contests
National and Regional Contests
Canada Contests
Canadian Mathematical Olympiad Qualification Repechage
2016 Canadian Mathematical Olympiad Qualification
2016 Canadian Mathematical Olympiad Qualification
Part of
Canadian Mathematical Olympiad Qualification Repechage
Subcontests
(8)
8
1
Hide problems
Tiling chipped boards, generating functions, and recursion
Let
n
≥
3
n \geq 3
n
≥
3
be a positive integer. A chipped
n
n
n
-board is a
2
×
n
2 \times n
2
×
n
checkerboard with the bottom left square removed. Lino wants to tile a chipped
n
n
n
-board and is allowed to use the following types of tiles:[*] Type 1: any
1
×
k
1 \times k
1
×
k
board where
1
≤
k
≤
n
1 \leq k \leq n
1
≤
k
≤
n
[*] Type 2: any chipped
k
k
k
-board where
1
≤
k
≤
n
1 \leq k \leq n
1
≤
k
≤
n
that must cover the left-most tile of the
2
×
n
2 \times n
2
×
n
checkerboard.Two tilings
T
1
T_1
T
1
and
T
2
T_2
T
2
are considered the same if there is a set of consecutive Type 1 tiles in both rows of
T
1
T_1
T
1
that can be vertically swapped to obtain the tiling
T
2
T_2
T
2
. For example, the following three tilings of a chipped
7
7
7
-board are the same:http://i.imgur.com/8QaSgc0.pngFor any positive integer
n
n
n
and any positive integer
1
≤
m
≤
2
n
−
1
1 \leq m \leq 2n - 1
1
≤
m
≤
2
n
−
1
, let
c
m
,
n
c_{m,n}
c
m
,
n
be the number of distinct tilings of a chipped
n
n
n
-board using exactly
m
m
m
tiles (any combination of tile types may be used), and define the polynomial
P
n
(
x
)
=
∑
m
=
1
2
n
−
1
c
m
,
n
x
m
.
P_n(x) = \sum^{2n-1}_{m=1} c_{m,n}x^m.
P
n
(
x
)
=
m
=
1
∑
2
n
−
1
c
m
,
n
x
m
.
Find, with justification, polynomials
f
(
x
)
f(x)
f
(
x
)
and
g
(
x
)
g(x)
g
(
x
)
such that
P
n
(
x
)
=
f
(
x
)
P
n
−
1
(
x
)
+
g
(
x
)
P
n
−
2
(
x
)
P_n(x) = f(x)P_{n-1}(x) + g(x)P_{n-2}(x)
P
n
(
x
)
=
f
(
x
)
P
n
−
1
(
x
)
+
g
(
x
)
P
n
−
2
(
x
)
for all
n
≥
3
n \geq 3
n
≥
3
.
7
1
Hide problems
Coordinate plane walk
Starting at
(
0
,
0
)
(0, 0)
(
0
,
0
)
, Richard takes
2
n
+
1
2n+1
2
n
+
1
steps, with each step being one unit either East, North, West, or South. For each step, the direction is chosen uniformly at random from the four possibilities. Determine the probability that Richard ends at
(
1
,
0
)
(1, 0)
(
1
,
0
)
.
6
1
Hide problems
GCD greater than GCD
Determine all ordered triples of positive integers
(
x
,
y
,
z
)
(x, y, z)
(
x
,
y
,
z
)
such that
gcd
(
x
+
y
,
y
+
z
,
z
+
x
)
>
gcd
(
x
,
y
,
z
)
\gcd(x+y, y+z, z+x) > \gcd(x, y, z)
g
cd
(
x
+
y
,
y
+
z
,
z
+
x
)
>
g
cd
(
x
,
y
,
z
)
.
5
1
Hide problems
Midpolygon perimeter
Consider a convex polygon
P
P
P
with
n
n
n
sides and perimeter
P
0
P_0
P
0
. Let the polygon
Q
Q
Q
, whose vertices are the midpoints of the sides of
P
P
P
, have perimeter
P
1
P_1
P
1
. Prove that
P
1
≥
P
0
2
P_1 \geq \frac{P_0}{2}
P
1
≥
2
P
0
.
4
1
Hide problems
f(x + f(y)) + f(x - f(y)) = x
Determine all functions
f
:
R
→
R
f: \mathbb{R} \rightarrow \mathbb{R}
f
:
R
→
R
such that
f
(
x
+
f
(
y
)
)
+
f
(
x
−
f
(
y
)
)
=
x
.
f(x + f(y)) + f(x - f(y)) = x.
f
(
x
+
f
(
y
))
+
f
(
x
−
f
(
y
))
=
x
.
3
1
Hide problems
Good and proper cubes
Given an
n
×
n
×
n
n \times n \times n
n
×
n
×
n
grid of unit cubes, a cube is good if it is a sub-cube of the grid and has side length at least two. If a good cube contains another good cube and their faces do not intersect, the first good cube is said to properly contain the second. What is the size of the largest possible set of good cubes such that no cube in the set properly contains another cube in the set?
2
1
Hide problems
Minimum area and perimeter
Let
P
=
(
7
,
1
)
P = (7, 1)
P
=
(
7
,
1
)
and let
O
=
(
0
,
0
)
O = (0, 0)
O
=
(
0
,
0
)
.(a) If
S
S
S
is a point on the line
y
=
x
y = x
y
=
x
and
T
T
T
is a point on the horizontal
x
x
x
-axis so that
P
P
P
is on the line segment
S
T
ST
ST
, determine the minimum possible area of triangle
O
S
T
OST
OST
.(b) If
U
U
U
is a point on the line
y
=
x
y = x
y
=
x
and
V
V
V
is a point on the horizontal
x
x
x
-axis so that
P
P
P
is on the line segment
U
V
UV
U
V
, determine the minimum possible perimeter of triangle
O
U
V
OUV
O
U
V
.
1
1
Hide problems
11 and 31 divides sums of powers
(a) Find all positive integers
n
n
n
such that
11
∣
(
3
n
+
4
n
)
11|(3^n + 4^n)
11∣
(
3
n
+
4
n
)
.(b) Find all positive integers
n
n
n
such that
31
∣
(
4
n
+
7
n
+
2
0
n
)
31|(4^n + 7^n + 20^n)
31∣
(
4
n
+
7
n
+
2
0
n
)
.