MathDB

1

2017 Guts #36: USAYNO Number Theory

Welcome to the USAYNO, where each question has a yes/no answer. Choose any subset of the following six problems to answer. If you answer

n

problems and get them all correct, you will receive

\max(0, (n-1)(n-2))

points. If any of them are wrong (or you leave them all blank), you will receive

0

points.
Your answer should be a six-character string containing 'Y' (for yes), 'N' (for no), or 'B' (for blank). For instance if you think 1, 2, and 6 are 'yes' and 3 and 4 are 'no', you should answer YYNNBY (and receive

12

points if all five answers are correct, 0 points if any are wrong).
(a) Does

\sum_{i=1}^{p-1}\frac{1}{i}\equiv 0\pmod{p^2}

for all odd prime numbers

p

? (Note that

\frac{1}{i}

denotes the number such that

i\cdot\frac{1}{i}\equiv 1\pmod{p^2}

)
(b) Do there exist

2017

positive perfect cubes that sum to a perfect cube?
(c) Does there exist a right triangle with rational side lengths and area

5

?
(d) A magic square is a

3\times 3

grid of numbers, all of whose rows, columns, and major diagonals sum to the same value. Does there exist a magic square whose entries are all [color = red]different prime numbers?
(e) Is

\prod_{p} \frac{p^2+1}{p^2-1} = \frac{2^2+1}{2^2-1}\cdot\frac{3^2+1}{3^2-1}\cdot\frac{5^2+1}{5^2-1}\cdot\frac{7^2+1}{7^2-1}\cdot\dots

a rational number?
(f) Do there exist infinite number of pairs of distinct integers

(a,b)

such that

a

and

b

have the same set of prime divisors, and

a+1

and

b+1

have the same set of prime divisors?
[color = red]The USAYNO disclaimer is only included in problem 33. I have included it here for convenience.
[color = red]A clarification was issued for problem 36(d) during the test. I have included it above.

35

1

2017 Guts #35: USAYNO Geometry

Welcome to the USAYNO, where each question has a yes/no answer. Choose any subset of the following six problems to answer. If you answer

n

problems and get them all correct, you will receive

\max(0, (n-1)(n-2))

points. If any of them are wrong (or you leave them all blank), you will receive

0

points.
Your answer should be a six-character string containing 'Y' (for yes), 'N' (for no), or 'B' (for blank). For instance if you think 1, 2, and 6 are 'yes' and 3 and 4 are 'no', you should answer YYNNBY (and receive

12

points if all five answers are correct, 0 points if any are wrong).
(a) Does there exist a finite set of points, not all collinear, such that a line between any two points in the set passes through a third point in the set?
(b) Let

ABC

be a triangle and

P

be a point. The isogonal conjugate of

P

is the intersection of the reflection of line

AP

over the

A

-angle bisector, the reflection of line

BP

over the

B

-angle bisector, and the reflection of line

CP

over the

C

-angle bisector. Clearly the incenter is its own isogonal conjugate. Does there exist another point that is its own isogonal conjugate?
(c) Let

F

be a convex figure in a plane, and let

P

be the largest pentagon that can be inscribed in

F

. Is it necessarily true that the area of

P

is at least

\frac{3}{4}

the area of

F

?
(d) Is it possible to cut an equilateral triangle into

2017

pieces, and rearrange the pieces into a square?
(e) Let

ABC

be an acute triangle and

P

be a point in its interior. Let

D,E,F

lie on

BC, CA, AB

respectively so that

PD

bisects

\angle{BPC}

,

PE

bisects

\angle{CPA}

, and

PF

bisects

\angle{APB}

. Is it necessarily true that

AP+BP+CP\ge 2(PD+PE+PF)

?
(f) Let

P_{2018}

be the surface area of the

2018

-dimensional unit sphere, and let

P_{2017}

be the surface area of the

2017

-dimensional unit sphere. Is

P_{2018}>P_{2017}

?
[color = red]The USAYNO disclaimer is only included in problem 33. I have included it here for convenience.

34

1

2017 Guts #34: USAYNO Combinatorics

Welcome to the USAYNO, where each question has a yes/no answer. Choose any subset of the following six problems to answer. If you answer

n

problems and get them all correct, you will receive

\max(0, (n-1)(n-2))

points. If any of them are wrong (or you leave them all blank), you will receive

0

points.
Your answer should be a six-character string containing 'Y' (for yes), 'N' (for no), or 'B' (for blank). For instance if you think 1,2, and 6 are 'yes' and 3 and 4 are 'no', you should answer YYNNBY (and receive

12

points if all five answers are correct, 0 points if any are wrong).
(a) Can

1000

queens be placed on a

2017\times2017

chessboard such that every square is attacked by some queen? A square is attacked by a queen if it lies on the same row, column, or diagonal as the queen.
(b) A

2017\times2017

grid of squares originally contains a

0

in each square. At any step, Kelvin the Frog choose two adjacent squares (two squares are adjacent if they share a side) and increments the numbers in both of them by

1

. Can Kelvin make every square contain a different power of

2

?
(c) A tournament consists of single games between every pair of players, where each game has a winner and a loser with no ties. A set of people is dominated if there exists a player who beats all of them. Does there exist a tournament in which every set of

2017

people is dominated?
(d) Every cell of a

19\times19

grid is colored either red, yellow, green, or blue. Does there necessarily exist a rectangle whose sides are parallel to the grid, all of whose vertices are the same color?
(e) Does there exist a

c\in\mathbb{R}^+

such that

\max(|A\cdot A|, |A+A|)\ge c|A|\log^2|A|

for all finite sets

A\subset \mathbb{Z}

?
(f) Can the set

\{1, 2, \dots, 1093\}

be partitioned into

7

subsets such that each subset is sum-free (i.e. no subset contains

a,b,c

with

a+b=c

)?
[color = red]The USAYNO disclaimer is only included in problem 33. I have included it here for convenience.

33

1

2017 Guts #33: USAYNO Algebra

Welcome to the USAYNO, where each question has a yes/no answer. Choose any subset of the following six problems to answer. If you answer

n

problems and get them all correct, you will receive

\max(0, (n-1)(n-2))

points. If any of them are wrong (or you leave them all blank), you will receive

0

points.
Your answer should be a six-character string containing 'Y' (for yes), 'N' (for no), or 'B' (for blank). For instance if you think 1, 2, and 6 are 'yes' and 3 and 4 are 'no', you should answer YYNNBY (and receive

12

points if all five answers are correct, 0 points if any are wrong).
(a)

a,b,c,d,A,B,C,

and

D

are positive real numbers such that

\frac{a}{b} > \frac{A}{B}

and

\frac{c}{d} > \frac{C}{D}

. Is it necessarily true that

\frac{a+c}{b+d} > \frac{A+C}{B+D}

?
(b) Do there exist irrational numbers

\alpha

and

\beta

such that the sequence

\lfloor\alpha\rfloor+\lfloor\beta\rfloor, \lfloor2\alpha\rfloor+\lfloor2\beta\rfloor, \lfloor3\alpha\rfloor+\lfloor3\beta\rfloor, \dots

is arithmetic?
(c) For any set of primes

\mathbb{P}

, let

S_\mathbb{P}

denote the set of integers whose prime divisors all lie in

\mathbb{P}

. For instance

S_{\{2,3\}}=\{2^a3^b \; | \; a,b\ge 0\}=\{1,2,3,4,6,8,9,12,\dots\}

. Does there exist a finite set of primes

\mathbb{P}

and integer polynomials

P

and

Q

such that

\gcd(P(x), Q(y))\in S_\mathbb{P}

for all

x,y

?
(d) A function

f

is called P-recursive if there exists a positive integer

m

and real polynomials

p_0(n), p_1(n), \dots, p_m(n)

[color = red], not all zero, satisfying

p_m(n)f(n+m)=p_{m-1}(n)f(n+m-1)+\dots+p_0(n)f(n)

for all

n

. Does there exist a P-recursive function

f

satisfying

\lim_{n\to\infty} \frac{f(n)}{n^{\sqrt{2}}}=1

?
(e) Does there exist a nonpolynomial function

f: \mathbb{Z}\to\mathbb{Z}

such that

a-b

divides

f(a)-f(b)

for all integers

a\neq b

?
(f) Do there exist periodic functions

f, g:\mathbb{R}\to\mathbb{R}

such that

f(x)+g(x)=x

for all

x

?
[color = red]A clarification was issued for problem 33(d) during the test. I have included it above.

32

1

2017 Guts #32: Finally, a three-variable inequality!

Let

a

,

b

,

c

be non-negative real numbers such that

ab + bc + ca = 3

. Suppose that

a^3 b + b^3 c + c^3 a + 2abc(a + b + c) = \frac{9}{2}.

What is the maximum possible value of

ab^3 + bc^3 + ca^3

?

31

1

2017 Guts #31: Imbalance of league

A baseball league has

6

teams. To decide the schedule for the league, for each pair of teams, a coin is flipped. If it lands head, they will play a game this season, in which one team wins and one team loses. If it lands tails, they don't play a game that season. Define the imbalance of this schedule to be the minimum number of teams that will end up undefeated, i.e. lose

0

games. Find the expected value of the imbalance in this league.

30

1

2017 Guts #30: Polygon with vertices on grid

Consider an equilateral triangular grid

G

with

20

points on a side, where each row consists of points spaced

1

unit apart. More specifically, there is a single point in the first row, two points in the second row, ..., and

20

points in the last row, for a total of

210

points. Let

S

be a closed non-self-intersecting polygon which has

210

vertices, using each point in

G

exactly once. Find the sum of all possible values of the area of

S

.

29

1

2017 Guts #29: Cycle factoring

Yang has the sequence of integers

1, 2, \dots, 2017

. He makes

2016

swaps in order, where a swap changes the positions of two integers in the sequence. His goal is to end with

2, 3, \dots, 2017, 1

. How many different sequences of swaps can Yang do to achieve his goal?

28

1

2017 Guts #28: Weird sequence and sum

Let

\dots, a_{-1}, a_0, a_1, a_2, \dots

be a sequence of positive integers satisfying the folloring relations:

a_n = 0

for

n < 0

,

a_0 = 1

, and for

n \ge 1

,

a_n = a_{n - 1} + 2(n - 1)a_{n - 2} + 9(n - 1)(n - 2)a_{n - 3} + 8(n - 1)(n - 2)(n - 3)a_{n - 4}.

Compute

\sum_{n \ge 0} \frac{10^n a_n}{n!}.

27

1

2017 Guts #27: Computational number theory

Find the smallest possible value of

x + y

where

x, y \ge 1

and

x

and

y

are integers that satisfy

x^2 - 29y^2 = 1

.

26

1

2017 Guts #26: Kelvin's demise

Kelvin the Frog is hopping on a number line (extending to infinity in both directions). Kelvin starts at

0

. Every minute, he has a

\frac{1}{3}

chance of moving

1

unit left, a

\frac{1}{3}

chance of moving

1

unit right, and

\frac{1}{3}

chance of getting eaten. Find the expected number of times Kelvin returns to

0

(not including the start) before he gets eaten.

25

1

2017 Guts #25: Vanilla equation

Find all real numbers

x

satisfying the equation

x^3 - 8 = 16 \sqrt[3]{x + 1}

.

24

1

2017 Guts #24: How to find 2^2016 mod p?

At a recent math contest, Evan was asked to find

2^{2016} \pmod{p}

for a given prime number

p

with

100 < p < 500

. Evan has forgotten what the prime

p

was, but still remembers how he solved it:
[*] Evan first tried taking

2016

modulo

p - 1

, but got a value

e

larger than

100

. [*] However, Evan noted that

e - \frac{1}{2}(p - 1) = 21

, and then realized the answer was

-2^{21} \pmod{p}

.
What was the prime

p

?

23

1

2017 Guts #23: Expected minimum distance

Five points are chosen uniformly at random on a segment of length

1

. What is the expected distance between the closest pair of points?

22

1

2017 Guts #22: Fighting frogs

Kelvin the Frog and

10

of his relatives are at a party. Every pair of frogs is either friendly or unfriendly. When

3

pairwise friendly frogs meet up, they will gossip about one another and end up in a fight (but stay friendly anyway). When

3

pairwise unfriendly frogs meet up, they will also end up in a fight. In all other cases, common ground is found and there is no fight. If all

\binom{11}{3}

triples of frogs meet up exactly once, what is the minimum possible number of fights?

21

1

2017 Guts #21: Maximum value of ratio in triangle

Let

P

and

A

denote the perimeter and area respectively of a right triangle with relatively prime integer side-lengths. Find the largest possible integral value of

\frac{P^2}{A}

[color = red]The official statement does not have the final period.

20

1

2017 Guts #20: n % 1000 > n % 1001

For positive integers

a

and

N

, let

r(a, N) \in \{0, 1, \dots, N - 1\}

denote the remainder of

a

when divided by

N

. Determine the number of positive integers

n \le 1000000

for which

r(n, 1000) > r(n, 1001).

19

1

2017 Guts #19: Number of odd coefficients

Find (in terms of

n \ge 1

) the number of terms with odd coefficients after expanding the product:

\prod_{1 \le i < j \le n} (x_i + x_j)

e.g., for

n = 3

the expanded product is given by

x_1^2 x_2 + x_1^2 x_3 + x_2^2 x_3 + x_2^2 x_1 + x_3^2 x_1 + x_3^2 x_2 + 2x_1 x_2 x_3

and so the answer would be

6

.

18

1

2017 Guts #18: Largest possible inscribed circle

Let

ABCD

be a quadrilateral with side lengths

AB = 2

,

BC = 3

,

CD = 5

, and

DA = 4

. What is the maximum possible radius of a circle inscribed in quadrilateral

ABCD

?

17

1

2017 Guts #17: Maximal number of subsequences

Sean is a biologist, and is looking at a strng of length

66

composed of the letters

A

,

T

,

C

,

G

. A substring of a string is a contiguous sequence of letters in the string. For example, the string

AGTC

has

10

substrings:

A

,

G

,

T

,

C

,

AG

,

GT

,

TC

,

AGT

,

GTC

,

AGTC

. What is the maximum number of distinct substrings of the string Sean is looking at?

16

1

2017 Guts #16: Complex nonlinear system

Let

a

and

b

be complex numbers satisfying the two equations \begin{align*} a^3 - 3ab^2 & = 36 \\ b^3 - 3ba^2 & = 28i. \end{align*} Let

M

be the maximum possible magnitude of

a

. Find all

a

such that

|a| = M

.

15

1

2017 Guts #15: Weird process II

Start by writing the integers

1, 2, 4, 6

on the blackboard. At each step, write the smallest positive integer

n

that satisfies both of the following properties on the board.
[*]

n

is larger than any integer on the board currently. [*]

n

cannot be written as the sum of

2

distinct integers on the board.
Find the

100

-th integer that you write on the board. Recall that at the beginning, there are already

4

integers on the board.

14

1

2017 Guts #14: Unhappy classroom

Mrs. Toad has a class of

2017

students, with unhappiness levels

1, 2, \dots, 2017

respectively. Today in class, there is a group project and Mrs. Toad wants to split the class in exactly

15

groups. The unhappiness level of a group is the average unhappiness of its members, and the unhappiness of the class is the sum of the unhappiness of all

15

groups. What's the minimum unhappiness of the class Mrs. Toad can achieve by splitting the class into

15

groups?

13

1

2017 Guts #13: Frogs and toads

The game of Penta is played with teams of five players each, and there are five roles the players can play. Each of the five players chooses two of five roles they wish to play. If each player chooses their roles randomly, what is the probability that each role will have exactly two players?

12

1

2017 Guts #12: OMO redux

In a certain college containing

1000

students, students may choose to major in exactly one of math, computer science, finance, or English. The diversity ratio

d(s)

of a student

s

is the defined as number of students in a different major from

s

divided by the number of students in the same major as

s

(including

s

). The diversity

D

of the college is the sum of all the diversity ratios

d(s)

.
Determine all possible values of

D

.

11

1

2017 Guts #11: Partition of 3-space

Consider the graph in

3

-space of

0 = xyz(x + y)(y + z)(z + x)(x - y)(y - z)(z - x).

This graph divides

3

-space into

N

connected regions. What is

N

7

7

7

7

7

7

7

7

7

2017 Harvard-MIT Mathematics Tournament

Subcontests

2017 Guts #36: USAYNO Number Theory

2017 Guts #35: USAYNO Geometry

2017 Guts #34: USAYNO Combinatorics

2017 Guts #33: USAYNO Algebra

2017 Guts #32: Finally, a three-variable inequality!

2017 Guts #31: Imbalance of league

2017 Guts #30: Polygon with vertices on grid

2017 Guts #29: Cycle factoring

2017 Guts #28: Weird sequence and sum

2017 Guts #27: Computational number theory

2017 Guts #26: Kelvin's demise

2017 Guts #25: Vanilla equation

2017 Guts #24: How to find 2^2016 mod p?

2017 Guts #23: Expected minimum distance

2017 Guts #22: Fighting frogs

2017 Guts #21: Maximum value of ratio in triangle

2017 Guts #20: n % 1000 > n % 1001

2017 Guts #19: Number of odd coefficients

2017 Guts #18: Largest possible inscribed circle

2017 Guts #17: Maximal number of subsequences

2017 Guts #16: Complex nonlinear system

2017 Guts #15: Weird process II

2017 Guts #14: Unhappy classroom

2017 Guts #13: Frogs and toads

2017 Guts #12: OMO redux

2017 Guts #11: Partition of 3-space

2017 Harvard-MIT Mathematics Tournament

Subcontests

2017 Guts #36: USAYNO Number Theory

2017 Guts #35: USAYNO Geometry

2017 Guts #34: USAYNO Combinatorics

2017 Guts #33: USAYNO Algebra

2017 Guts #32: Finally, a three-variable inequality!

2017 Guts #31: Imbalance of league

2017 Guts #30: Polygon with vertices on grid

2017 Guts #29: Cycle factoring

2017 Guts #28: Weird sequence and sum

2017 Guts #27: Computational number theory

2017 Guts #26: Kelvin's demise

2017 Guts #25: Vanilla equation

2017 Guts #24: How to find 2^2016 mod p?

2017 Guts #23: Expected minimum distance

2017 Guts #22: Fighting frogs

2017 Guts #21: Maximum value of ratio in triangle

2017 Guts #20: n % 1000 &gt; n % 1001

2017 Guts #19: Number of odd coefficients

2017 Guts #18: Largest possible inscribed circle

2017 Guts #17: Maximal number of subsequences

2017 Guts #16: Complex nonlinear system

2017 Guts #15: Weird process II

2017 Guts #14: Unhappy classroom

2017 Guts #13: Frogs and toads

2017 Guts #12: OMO redux

2017 Guts #11: Partition of 3-space

2017 Guts #20: n % 1000 > n % 1001