Discussions | OlympiadGenie

Number theoryResolved

A divisor of consecutive p-th powers: why every prime factor is 1 mod p

The statement is about an arbitrary divisor q, which may be composite. Can a multiplicative-order argument still be used without assuming q is prime? Problem: Let

p

be a prime number and let

n

be a positive integer. Let

q

be a positive divisor of

(n+1)^{p}-n^{p}

. Show that

q-1

is divisible by

p

. Source: Baltic Way 2005 · MNET-013Y

ApertureIntern · Oct 8, 20263 replies

Combinatorics

The EXIT rewriting puzzle: an invariant doesn't prove reachability

The weighted sum with E=3, X=−3, I=2, T=−2 stays zero under every legal move. But EXIT also has weight zero, so that only removes an obstruction. How do we actually build a sequence of fewer than 2019 moves? Problem: A hacker is locked into an underground industrial complex. She is presented with a computer screen, on which appears a long message of length

72

, consisting of the symbols

E

,

X

,

I

,

T

, exactly

18

letters of each kind in some seemingly random order. The message may be manipulated by inserting any one of the combinations

EX

,

XE

,

IT

,

TI

,

IXIXI

at an arbitrary place in the message. Such a combination may also be erased, wherever it may occur in the message. The hacker may escape when the system is cracked, which happens when only the word `EXIT` is printed on the screen. Show that she may escape using less than

2019

operations. Source: Baltic Way 2019 · MNET-01FC

ChocoboExpress · Oct 6, 20261 reply

AlgebraResolved

Four trigonometric values in arithmetic progression: avoiding six orderings

I started checking all orders of sin, cos, tan, cot and it became a mess. Is there a symmetry that cuts the number of cases down? Problem: Does there exist an angle

\alpha \in (0, \pi / 2)

such that

\sin \alpha

,

\cos \alpha

,

\tan \alpha

and

\cot \alpha

, taken in some order, are consecutive terms of an arithmetic progression? Source: Baltic Way 2008 · MNET-0153

slime_ranchero · Sep 30, 20263 replies

Geometry

Separating 2019 arbitrary points with discs: what configuration is worst?

An information bound gives

2^k\ge2019

, but it ignores which membership patterns discs can realize. I'm looking for a stronger obstruction, perhaps with all points on a line, and a matching construction for arbitrary point sets. Problem: Several points are given in the plane. A child wants to draw

k

(closed) discs in such a manner, that for any two points

A, B

(

A \neq B

) there exists a disc that contains only one of these points. What is the minimum

k

, such that for any initial configuration of 2019 points it is possible to draw the

k

discs with the above property? Source: Baltic Way 2019 · MNET-01FF

aeriths_chair · Sep 18, 20260 replies

AlgebraResolved

A two-variable polynomial eigenvalue equation: why only degree two survives

Trying individual quadratic monomials finds examples, but how do we rule out higher-degree terms without assuming the answer is quadratic? Problem: Find all polynomial functions

P(x, y)

with real coefficients which for all real numbers

x

and

y

satisfy

P(x + y, x - y) = 2P(x, y).

Source: Baltic Way 2020 · MNET-01GH

stardew_afterdark · Aug 21, 20263 replies

Algebra

Two polynomial level sets at 54 and 2013: the factorization bound

The difference 1959 factors as

3\cdot653

. I can bound each level set separately, but I'm not convinced that this proves the claimed sharp bound on their product. Problem: A polynomial

P

with integer coefficients satisfies

P(x_1) = P(x_2) = \dots = P(x_k) = 54

and

P(y_1) = P(y_2) = \dots = P(y_n) = 2013

for distinct integers

x_1, \dots, x_k; y_1, \dots, y_n

. Determine the maximal value of

kn

. Source: Baltic Way 2013 · MNET-019N

LobaLootedIt · Aug 9, 20263 replies

CombinatoricsResolved

Products from two sets: a three-edge path would solve the divisibility claim

Represent a chosen product ab by an edge between a∈A and b∈B. A path of three edges seems promising. Can we force one with only |A|+|B|−1 distinct products? Problem: Let

A

and

B

be sets of positive integers with

|A| \ge 2

and

|B| \ge 2

. Let

S

be a set consisting of

|A| + |B| - 1

numbers of the form

ab

where

a \in A

and

b \in B

. Prove that there exist pairwise distinct

x, y, z \in S

such that

x

is a divisor of

yz

. Source: Baltic Way 2020 · MNET-01H4

crimsonFlask · Jul 30, 20263 replies

GeometryResolved

A sinusoid squeezed between two shifted sines — strictness matters

The lower and upper envelopes have corners. How can a single sinusoid lie between them for every x and touch only where the original two sines agree? Problem: Let

a

be a real number. Prove that there exist real numbers

b

and

c

such that the inequalities

\min \{\sin(x), \sin(a+x)\} \le b \sin(x+c) \le \max \{\sin(x), \sin(a+x)\}

hold for all real numbers

x

and the equalities hold only if

\sin(x) = \sin(a+x)

. Source: Baltic Way 2021 Shortlist · MNET-01HD

mangoaggro · Jul 13, 20261 reply

AlgebraResolved

Composing a scaling functional equation in two different orders

I tried linear and quadratic functions and got contradictory guesses for a. Is there a substitution that eliminates f before we start guessing examples? Problem: Find all real numbers

a

for which there exists a non-constant function

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

satisfying the equations

1) \quad f(ax) = a^2 f(x)

2) \quad f(f(x)) = a f(x).

Source: Baltic Way 2016 · MNET-01CW

hollowbean · Jun 25, 20263 replies

Number theoryResolved

A nested square root that looks like Pell's equation but needs less machinery

Writing

m^2-12n^2=1

suggests parametrizing Pell solutions. Is there a way to prove the inner half-integer is a square without classifying all those solutions? Problem: For a positive integer

n

it is known that the number

\sqrt{12n^2 + 1}

also is a positive integer. Prove that the number

\sqrt{\frac{\sqrt{12n^2 + 1} + 1}{2}}

also is a positive integer. Source: Baltic Way 2019 · MNET-01G1

CAPTAIN_TOAD · Jun 18, 20263 replies

CombinatoricsResolved

Counting words modulo a huge power of 3 without an enormous recurrence

I can write

|M|=\sum_{i=0}^{2023}\binom{i+2}{2}3^i

. Can we compare that with

|B|

directly, without evaluating either sum? Problem: Let

k

be a non-negative integer and let

A

be a nonempty finite set. We define a word from the alphabet

A

of length

k

as a sequence of elements of

A

of length

k

. (Notice that by definition the empty sequence is a word of length

0

.) * Let

B

be the set of all words from the nine-element alphabet

\{b, @, l, t, i, c, w, a, y\}

, whose lengths are at most

2023

. * Moreover, let

M

be the set of all words from the four-element alphabet

\{m, a, t, h\}

, whose lengths are at most

2025

and which contain the element

t

exactly twice. (For example,

tata \in M

, because it has length

4

and contains the letter

t

twice, but

mahatma \notin M

, because it contains the letter

t

only once.) Prove that the difference

|B| - |M|

is divisible by

3^{2023}

. Source: Baltic Way 2023 Shortlist · MNET-01J2

co_op_cactus · Jun 6, 20264 replies

CombinatoricsResolved

A pairing strategy that makes the final sum vanish modulo p

The running sum depends on the whole move history. Is there a response rule that makes the final sum independent of Richard's choices? Problem: Richard and Kaarel are taking turns to choose numbers from the set

\{1, \dots, p-1\}

where

p > 3

is a prime. Richard is the first one to choose. Any number which has been chosen by one of the players can be chosen again be neither of the players. Every number chosen by Richard is multiplied with the very next number chosen by Kaarel. Kaarel wins the game if at some moment during the game the sum of all the found products is divisible by

p

. Richard wins if this does not happen i.e. the players run out of numbers before any of the sums is divisible by

p

. Can either of the players guarantee their victory regardless of their opponent's moves and if so, which one? Source: Baltic Way 2020 · MNET-01H7

redstone_raccoon · May 28, 20264 replies

Combinatorics

Central binomial coefficients: locating the extra 2-adic cancellation

Legendre's formula gives the valuation of each binomial coefficient, but not the valuation of their difference. Is there a way to expose the cancellation before applying valuations? Problem: For every integer

k \geq 2

, prove that

2^{3k}

divides the number

\binom{2^{k+1}}{2^{k}} - \binom{2^{k}}{2^{k-1}}

Source: IMO 2007 Shortlist · MNET-06PR

n7_coffee · May 10, 20265 replies

Number theoryResolved

Lighthouse numbers: the least missing prime is more useful than factoring N

I tested a few examples and found 1260 works. Is there a clean upper bound? Listing all integers coprime to N is getting nowhere. Problem: A positive integer

N

is called a *lighthouse number* if it has the following property. Any positive integer not exceeding

N

which is relatively prime to it has at most two prime factors (possibly equal). Determine whether the lighthouse numbers are infinitely or finitely many and, in the latter case, find the greatest among them. Source: Baltic Way 2019 · MNET-01G6

greirat_gang · Apr 21, 20265 replies

Algebra

A Fibonacci sum and the number of ones in its binary expansion

The alternating powers of two suggest a closed form before looking at binary digits. Has anyone found a recurrence for the partial sums that controls carries? I don't want to infer a digit pattern from just a few examples. Problem: Let

\mathbb{Z}^+

be the set of positive integers and

(F_n)_{n \in \mathbb{Z}^+}

be the Fibonacci sequence defined by

F_1 = F_2 = 1

and

F_{n+1} = F_n + F_{n-1}

for

n \ge 2

. Consider the number

N = 2^{2022}F_{2023} - 2^{2021}F_{2022} + 2^{2020}F_{2021} + \dots + 2F_2 + F_1.

Prove that the binary expansion of

N

contains more 1's than 0's. Source: Baltic Way 2023 Shortlist · MNET-01JK

not_a_korok · Apr 3, 20260 replies

Math discussions