MathNet 2018-part-07 — 177 problems (EN–VI)

Let $G$ be a simple graph with $k$ connected components, which have $a_{1}, \ldots, a_{k}$ vertices, respectively. Determine the number of ways to add $k-1$ edges to $G$ to form a connected graph, in terms of the numbers $a_{i}$.

Let $a_{0} = a_{1} = 1$ and $a_{n+1} = 7 a_{n} - a_{n-1} - 2$ for all positive integers $n$. Prove that $a_{n}$ is a perfect square for all $n$.

When the number
$$
N = 1^{1} \times 2^{2} \times 3^{3} \times \cdots \times 9^{9}
$$
is written as a decimal number, how many zeros does it end in?

A square and an equilateral triangle have the property that the area of each is the perimeter of the other. What is the area of the square?

Find all the ways which one can assign an integer to each vertex of a $100$-gon subject to the following condition: among any three consecutive numbers written down, one of the numbers is the sum of the other two.

Give an example of a strictly increasing function $f: \mathbb{R} \rightarrow [0,1]$ with the property that
$$
f(x+y) \leq f(x)+f(y)
$$
for any real numbers $x$ and $y$.

Louis moves around on the lattice points according to the following rules: From point $(x, y)$ he may move to any of the points $(y, x)$, $(3x, -4y)$, $(-2x, 5y)$, $(x+1, y+6)$ and $(x-7, y)$. Show that if he starts at $(0,1)$ he can never get to $(0,0)$.

A sequence $a_{1}, a_{2}, \ldots$ of positive integers satisfies $a_{1}=1$ and
$$
a_{n+1}=2^{a_{n}}+a_{n}
$$
for $n \geq 1$. Prove that $a_{1}, a_{2}, \ldots, a_{243}$ leave distinct remainders when divided by $243$.

Let $ABC$ be a triangle with incenter $I$ and circumcenter $O$ for which $BC \lt AB \lt AC$. Let $D$ and $E$ be points in the interiors of sides $AB$ and $AC$, respectively, of triangle $ABC$, such that $DB = BC = CE$. Prove that $\overline{DE} \perp \overline{IO}$.

Let $m \gt 1$ be a fixed positive integer. For a nonempty string of base-ten digits $S$, let $c(S)$ be the number of ways to split $S$ into contiguous nonempty strings of digits such that the base-ten number represented by each string is divisible by $m$. These strings are allowed to have leading zeroes.
In terms of $m$, what are the possible values that $c(S)$ can take?
For example, if $m = 2$, then $c(1234) = 2$ as the splits $1234$ and $12 \mid 34$ are valid, while the other six splits are invalid.

Consider a finite set of points $T \subset \mathbb{R}^n$ contained in the $n$-dimensional unit ball centered at the origin, and let $X$ be the convex hull of $T$. Prove that for all positive integers $k$ and all points $x \in X$, there exist points $t_1, t_2, \ldots, t_k \in T$, not necessarily distinct, such that their centroid
$$
\frac{t_1 + t_2 + \cdots + t_k}{k}
$$
has Euclidean distance at most $\frac{1}{\sqrt{k}}$ from $x$.

(The $n$-dimensional unit ball centered at the origin is the set of points in $\mathbb{R}^n$ with Euclidean distance at most 1 from the origin. The convex hull of a set of points $T \subset \mathbb{R}^n$ is the smallest set of points $X$ containing $T$ such that each line segment between two points in $X$ lies completely inside $X$.)

A polygon in the plane (with no self-intersections) is called equitable if every line passing through the origin divides the polygon into two (possibly disconnected) regions of equal area.
Does there exist an equitable polygon which is not centrally symmetric about the origin?
(A polygon is centrally symmetric about the origin if a 180-degree rotation about the origin sends the polygon to itself.)

Find all functions $f: \mathbb{R}^{+} \rightarrow \mathbb{R}^{+}$ such that
$$
f(x+f(y+x y))=(y+1) f(x+1)-1
$$
for all $x, y \in \mathbb{R}^{+}$.
($\mathbb{R}^{+}$ denotes the set of positive real numbers.)

Let $G$ be an undirected simple graph. Let $f(G)$ be the number of ways to orient all of the edges of $G$ in one of the two possible directions so that the resulting directed graph has no directed cycles. Show that $f(G)$ is a multiple of $3$ if and only if $G$ has a cycle of odd length.

For some real number $c$, the graphs of the equation $y = |x - 20| + |x + 18|$ and the line $y = x + c$ intersect at exactly one point. What is $c$?

There are two prime numbers $p$ so that $5p$ can be expressed in the form $\left\lfloor\frac{n^{2}}{5}\right\rfloor$ for some positive integer $n$. What is the sum of these two prime numbers?

Let $\omega_{1}, \omega_{2}, \ldots, \omega_{100}$ be the roots of $\frac{x^{101}-1}{x-1}$ (in some order). Consider the set
$$
S=\left\{\omega_{1}^{1}, \omega_{2}^{2}, \omega_{3}^{3}, \ldots, \omega_{100}^{100}\right\}
$$
Let $M$ be the maximum possible number of unique values in $S$, and let $N$ be the minimum possible number of unique values in $S$. Find $M-N$.

Let $\alpha, \beta$, and $\gamma$ be three real numbers. Suppose that
$$
\begin{aligned}
\cos \alpha+\cos \beta+\cos \gamma & =1 \\
\sin \alpha+\sin \beta+\sin \gamma & =1
\end{aligned}
$$
Find the smallest possible value of $\cos \alpha$.

Rachel has the number $1000$ in her hands. When she puts the number $x$ in her left pocket, the number changes to $x+1$. When she puts the number $x$ in her right pocket, the number changes to $x^{-1}$. Each minute, she flips a fair coin. If it lands heads, she puts the number into her left pocket, and if it lands tails, she puts it into her right pocket. She then takes the new number out of her pocket. If the expected value of the number in Rachel's hands after eight minutes is $E$, then compute $\left\lfloor\frac{E}{10}\right\rfloor$.

For how many pairs of sequences of nonnegative integers $\left(b_{1}, b_{2}, \ldots, b_{2018}\right)$ and $\left(c_{1}, c_{2}, \ldots, c_{2018}\right)$ does there exist a sequence of nonnegative integers $\left(a_{0}, \ldots, a_{2018}\right)$ with the following properties:
- For $0 \leq i \leq 2018, a_{i}\lt 2^{2018}$;
- For $1 \leq i \leq 2018, b_{i}=a_{i-1}+a_{i}$ and $c_{i}=a_{i-1} \mid a_{i}$;
where $\mid$ denotes the bitwise or operation?
(The bitwise or of two nonnegative integers $x=\cdots x_{3} x_{2} x_{1} x_{0}$ and $y=\cdots y_{3} y_{2} y_{1} y_{0}$ expressed in binary is defined as $x \mid y=\cdots z_{3} z_{2} z_{1} z_{0}$, where $z_{i}=1$ if at least one of $x_{i}$ and $y_{i}$ is 1 , and 0 otherwise.)