brain

tamnd's digital brain — notes, problems, research

43815 notes

Kvant Math Problem 1095

The problem involves constructing a chord $MN$ of a circle with center $O$ seen from $A$ under a given angle $\alpha$, with additional geometric constraints.

kvantmathematicsolympiad
Kvant Math Problem 1094

The two inequalities are

kvantmathematicsolympiad
Kvant Math Problem 1093

Represent the configuration by numbers $a_1,\dots,a_n\in{0,1,2}$ arranged cyclically.

kvantmathematicsolympiad
Kvant Math Problem 1092

Consider a single fold of a convex polygon and a subsequent straight cut.

kvantmathematicsolympiad
Kvant Math Problem 1090

Testing small values helps build intuition about the inequality.

kvantmathematicsolympiad
Kvant Math Problem 1089

Let the inradius of triangle $AOB$ be $r_1$, of $BOC$ be $r_2$, of $COD$ be $r_3$, and of $DOA$ be $r_4$.

kvantmathematicsolympiad
Kvant Math Problem 1088

The condition is

kvantmathematicsolympiad
Kvant Math Problem 1087

Let $h_a,h_b,h_c$ be the altitudes of triangle $ABC$.

kvantmathematicsolympiad
Kvant Math Problem 1086

Consider the problem of reaching a target number from $0$ using only two operations: doubling the current number or adding $1$.

kvantmathematicsolympiad
Kvant Math Problem 1085

Consider the problem geometrically.

kvantmathematicsolympiad
Kvant Math Problem 1084

Let the two given circles be $\omega_1$ and $\omega_2$, intersecting at $A$ and $B$.

kvantmathematicsolympiad
Kvant Math Problem 1083

Consider small values of $n$ to understand the inequality.

kvantmathematicsolympiad
Kvant Math Problem 1082

The given equality resembles the identity for the sum of squares of the sides of a quadrilateral.

kvantmathematicsolympiad
Kvant Math Problem 1081

Compute a few values:

kvantmathematicsolympiad
Kvant Math Problem 1080

Let

kvantmathematicsolympiad
Kvant Math Problem 1079

For $n=3$ the problem asks for a single triangle whose three side lengths are irrational and whose area is a nonzero rational number.

kvantmathematicsolympiad
Kvant Math Problem 1078

Assume that a function $f:\mathbb N_0\to\mathbb N_0$ satisfies

kvantmathematicsolympiad
Kvant Math Problem 1077

Let $X(\sigma)$ denote the number of fixed points of a permutation $\sigma$ of an $n$ element set.

kvantmathematicsolympiad
Kvant Math Problem 1075

Consider the problem in terms of digit patterns.

kvantmathematicsolympiad
Kvant Math Problem 1074

Let $m=2n+1$.

kvantmathematicsolympiad
Kvant Math Problem 1073

Consider a hexagon $A_1A_2A_3A_4A_5A_6$ with a point $O$ from which all sides are seen under an angle of $60^\circ$.

kvantmathematicsolympiad
Kvant Math Problem 1072

The expression $989 \cdot 1001 \cdot 1007 + 320$ appears to involve three numbers spaced by six units: $989$, $1001$, $1007$.

kvantmathematicsolympiad
Kvant Math Problem 1071

Consider smaller versions of the game to understand the parity dynamics.

kvantmathematicsolympiad
Kvant Math Problem 1070

Let the tetrahedron have vertices $A,B,C,D$.

kvantmathematicsolympiad
Kvant Math Problem 1069

Consider a small number of families, say three or four, each in a distinct apartment.

kvantmathematicsolympiad
Kvant Math Problem 1068

Consider an angle $AOB$ with points $A$ on one side and $B$ on the other.

kvantmathematicsolympiad
Kvant Math Problem 1067

Let

kvantmathematicsolympiad
Kvant Math Problem 1066

Consider six points in the plane with all pairwise distances at most $1$.

kvantmathematicsolympiad
Kvant Math Problem 1065

We are asked to study vectors $(x;y)$ with non-negative integer coordinates and to decide when they can be written as sums of _generating vectors_, i.

kvantmathematicsolympiad
Kvant Math Problem 1064

Let the closed broken line have vertices $V_1,\dots,V_n$ and segments $e_i=V_iV_{i+1}$, where indices are taken modulo $n$.

kvantmathematicsolympiad
Kvant Math Problem 1063

Let the digits of the $n$-digit number $a$ be

kvantmathematicsolympiad
Kvant Math Problem 1062

The first part of the problem deals with a triangle $ABC$ with points $D$ on $AC$ and $E$ on $AB$, forming the intersecting lines $BD$ and $CE$ at $M$.

kvantmathematicsolympiad
Kvant Math Problem 1061

Interpret the cities and roads as a graph.

kvantmathematicsolympiad
Kvant Math Problem 1060

Consider two closed polygonal chains in the plane, each with an odd number of sides.

kvantmathematicsolympiad
Kvant Math Problem 1059

Let

kvantmathematicsolympiad
Kvant Math Problem 1058

Consider a finite subset of $\mathbb{Z}^2$ as a candidate for the marked points and examine what happens when we translate each by all vectors from the given finite set.

kvantmathematicsolympiad
Kvant Math Problem 1057

A move consists of writing a number that is not a divisor of any previously written number.

kvantmathematicsolympiad
Kvant Math Problem 1056

Consider small cases first.

kvantmathematicsolympiad
Kvant Math Problem 1055

Consider a circle with a small number of points to understand the behavior of arcs subtending at most $120^\circ$.

kvantmathematicsolympiad
CF 222E - Decoding Genome

We have an alphabet of size m, consisting of the first m symbols from the sequence a..zA..Z. Some ordered pairs of symbols are forbidden. If pair (x, y) is forbidden, then symbol y cannot appear immediately after symbol x in the DNA string.

codeforcescompetitive-programmingdpmatrices
CF 222D - Olympiad

We are given two multisets of scores. Array a contains the scores obtained in the first tour, and array b contains the scores obtained in the second tour.

codeforcescompetitive-programmingbinary-searchgreedysortingstwo-pointers
CF 222C - Reducing Fractions

The fraction is not given as a single numerator and denominator. Instead, we receive two arrays. The product of all numbers in the first array is the numerator, and the product of all numbers in the second array is the denominator.

codeforcescompetitive-programmingimplementationmathnumber-theorysortings
Kvant Math Problem 1054

Consider four spheres in three-dimensional space.

kvantmathematicsolympiad
CF 220B - Little Elephant and Array

We are given an array of positive integers and many range queries. For each query [l, r], we look only at the subarray between those positions and count how many values x satisfy a very specific condition: Inside that subarray, the value x appears exactly x times.

codeforcescompetitive-programmingconstructive-algorithmsdata-structures
CF 220A - Little Elephant and Problem

We are given an array that was originally sorted in non-decreasing order. At some point, either nothing happened or exactly one pair of elements may have been swapped.

codeforcescompetitive-programmingimplementationsortings
CF 220E - Little Elephant and Inversions

We are given an array of positive integers a of length n. We need to count the number of pairs (l, r) with 1 ≤ l < r ≤ n such that if we take the element at position l and move it just before position r (shifting the elements in between right by one), the resulting array has…

codeforcescompetitive-programmingdata-structurestwo-pointers
CF 220D - Little Elephant and Triangle

We have all lattice points inside the rectangle $$0 le x le w,qquad 0 le y le h.$$ A valid answer is an ordered triple of points that forms a nondegenerate triangle whose area is a positive integer. The order matters, so every geometric triangle contributes up to $3!

codeforcescompetitive-programminggeometrymath
CF 220C - Little Elephant and Shifts

We are given two permutations a and b of length n. Each permutation contains all integers from 1 to n exactly once. We are asked to compute, for every cyclic shift of b, a quantity called the distance.

codeforcescompetitive-programmingdata-structures
CF 219C - Color Stripe

We are given a stripe represented as a row of n cells, where each cell is painted one of k colors labeled with letters A through the k-th letter. The goal is to repaint as few cells as possible so that no two adjacent cells share the same color.

codeforcescompetitive-programmingbrute-forcedpgreedy
CF 219D - Choosing Capital for Treeland

We are asked to choose a capital city in a tree-shaped country with one-way roads. Each city is a node, and each road is a directed edge. The goal is to orient all roads so that from the chosen capital, we can reach every other city by following the roads in their direction.

codeforcescompetitive-programmingdfs-and-similardpgraphstrees
CF 219E - Parking Lot

We have a linear parking lot with n spaces numbered from 1 to n. Cars arrive and depart over time. When a car arrives, we must assign it a spot that maximizes the distance to the nearest occupied space.

codeforcescompetitive-programmingdata-structures
CF 217E - Alien DNA

We start with a DNA string. Each mutation chooses a contiguous segment, keeps that segment in place, and inserts a transformed copy immediately after it.

codeforcescompetitive-programmingdata-structuresdsutrees
Kvant Math Problem 1053

The first few Fibonacci numbers with at least four digits are

kvantmathematicsolympiad
Kvant Math Problem 1052

Consider a convex $n$-gon with vertices labeled cyclically as $A_1, A_2, \dots, A_n$.

kvantmathematicsolympiad
Kvant Math Problem 1051

Consider a $3\times3$ cluster of pieces on an $8\times8$ chessboard.

kvantmathematicsolympiad
Kvant Math Problem 1050

Let the chosen points be

kvantmathematicsolympiad
Kvant Math Problem 1049

Consider a cylinder $\text{Ц}_1$ with radius $R_1$ and height $H_1$, and define its diameter-to-height ratio $k = \frac{2R_1}{H_1}$.

kvantmathematicsolympiad
Kvant Math Problem 1048

Consider the simplest nontrivial cases of the knight’s tour game.

kvantmathematicsolympiad
Kvant Math Problem 1047

Consider a small round-robin tournament with $n$ players.

kvantmathematicsolympiad
Kvant Math Problem 1046

Consider an acute-angled triangle $ABC$ with $\angle A = 60^\circ$.

kvantmathematicsolympiad
Kvant Math Problem 1045

Consider the geometry of the kingdom, which is a square of side $2$ km.

kvantmathematicsolympiad
Kvant Math Problem 1044

Let

kvantmathematicsolympiad
Kvant Math Problem 1042

Let the class contain $n$ students.

kvantmathematicsolympiad
Kvant Math Problem 1041

A regular pentagon is determined up to congruence by any three consecutive vertices.

kvantmathematicsolympiad
Kvant Math Problem 1040

For $n=1$ the three groups are ${1},{2},{3}$, and $3=1+2$.

kvantmathematicsolympiad
Kvant Math Problem 1039

Label the tetrahedron vertices as $A$, $B$, $C$, $D$.

kvantmathematicsolympiad
Kvant Math Problem 1038

The rectangle contains $mn$ cells.

kvantmathematicsolympiad
Kvant Math Problem 1037

Consider the equation $x^y - y^x = x + y$ with $x, y \in \mathbb{N}$.

kvantmathematicsolympiad
Kvant Math Problem 1036

Consider a pentagon and imagine cutting it into two smaller pentagons of equal area and shape.

kvantmathematicsolympiad
Kvant Math Problem 1035

Consider marking points on $[0,1]$ sequentially.

kvantmathematicsolympiad
Kvant Math Problem 1034

Consider small chocolate bars first.

kvantmathematicsolympiad
Kvant Math Problem 1033

Let the square have vertices $A,B,C,D$ in cyclic order.

kvantmathematicsolympiad
Kvant Math Problem 1032

Begin with small values of $n$ to detect a pattern.

kvantmathematicsolympiad
Kvant Math Problem 1031

Reflecting on the problem, the point $M$ is chosen on the line $\ell$ to minimize the sum $MA + MB$.

kvantmathematicsolympiad
Kvant Math Problem 1030

Consider simple convex polyhedra such as nested cubes, tetrahedra, or pyramids.

kvantmathematicsolympiad
Kvant Math Problem 1028

Begin by considering the configuration of two intersecting lines and points $D$ and $E$ on them.

kvantmathematicsolympiad
Kvant Math Problem 1027

The number $1987$ is prime, since it is not divisible by any prime not exceeding $\sqrt{1987}<45$.

kvantmathematicsolympiad
Kvant Math Problem 1026

Let the common measure of each arc be $x$.

kvantmathematicsolympiad
Kvant Math Problem 1025

Consider a convex quadrilateral $ABCD$ with extensions of opposite sides $AB$ and $CD$, and $AD$ and $BC$, intersecting at points $P$ and $Q$ respectively.

kvantmathematicsolympiad
Kvant Math Problem 1024

Consider two triangles with angles $\alpha, \beta, \gamma$ and $\alpha_1, \beta_1, \gamma_1$.

kvantmathematicsolympiad
Kvant Math Problem 1023

For small numbers of triangles the statement is false.

kvantmathematicsolympiad
Kvant Math Problem 1022

For numbers $1,2,\dots,2n$, suppose they are arranged in two rows and $n$ columns.

kvantmathematicsolympiad
Kvant Math Problem 1021

Consider how the mountaineer’s progress depends on the day’s starting point.

kvantmathematicsolympiad
Kvant Math Problem 1020

Consider a sphere of radius $1$ with a curve drawn on it, either open of length less than $\pi$ or closed of length less than $2\pi$.

kvantmathematicsolympiad
Kvant Math Problem 1019

Consider first a small example on a $3 \times 3$ portion of the grid.

kvantmathematicsolympiad
Kvant Math Problem 1018

Consider a regular $n$-gon $A_1 A_2 \dots A_n$ with center $O$.

kvantmathematicsolympiad
Kvant Math Problem 1017

Consider assigning integers to the vertices of a regular pentagon and performing the prescribed operation whenever a vertex carries a negative number.

kvantmathematicsolympiad
Kvant Math Problem 1016

For a polygon circumscribed about a circle of radius $r$, let the sides be $s_1,\dots,s_n$, with corresponding side lengths $\ell_1,\dots,\ell_n$.

kvantmathematicsolympiad
Kvant Math Problem 1015

The polynomial is

kvantmathematicsolympiad
Kvant Math Problem 1014

Consider small examples of pairwise coprime numbers, such as $a_1=2$, $a_2=3$, $a_3=5$.

kvantmathematicsolympiad
Kvant Math Problem 1013

Consider triangle $ABC$ with points $M$ on $AB$ and $N$ on $BC$.

kvantmathematicsolympiad
Kvant Math Problem 1012

Consider arrangements of circles in the plane where each circle touches several others.

kvantmathematicsolympiad
Kvant Math Problem 1011

For the first inequality,

kvantmathematicsolympiad
Kvant Math Problem 1010

Consider the sequence defined by $r_1=2$ and $r_{n+1}=r_1 r_2 \cdots r_n + 1$.

kvantmathematicsolympiad
Kvant Math Problem 1009

Let the parallelogram be represented by vectors.

kvantmathematicsolympiad
Kvant Math Problem 1008

Number the steps from $1$ at the bottom to $2n+1$ at the top.

kvantmathematicsolympiad
CF 208B - Solitaire

We are given a shuffled deck of up to 52 cards arranged in a line, each represented by a value and a suit. Initially, every card forms its own pile.

codeforcescompetitive-programmingdfs-and-similardp
CF 208C - Police Station

We are given an undirected, connected graph representing cities and roads, where every road has the same travel time. Among all cities, city 1 and city n are special: we care about travel between these two endpoints.

codeforcescompetitive-programmingdpgraphsshortest-paths
Kvant Math Problem 1007

The equality

kvantmathematicsolympiad
CF 208E - Blood Cousins

We are given a rooted forest where each person has at most one parent. If we follow parent pointers upward, we eventually reach a root or fall off the structure. This defines a collection of trees. A “k-th ancestor” means applying the parent relation k times.

codeforcescompetitive-programmingbinary-searchdata-structuresdfs-and-similartrees