Found problems: 5923
For a positive integer $N$, let $T(N)$ denote the number of arrangements of the integers $1, 2, \cdots N$ into a sequence $a_1, a_2, \cdots a_N$ such that $a_i > a_{2i}$ for all $i$, $1 \le i < 2i \le N$ and $a_i > a_{2i+1}$ for all $i$, $1 \le i < 2i+1 \le N$. For example, $T(3)$ is $2$, since the possible arrangements are $321$ and $312$
(a) Find $T(7)$
(b) If $K$ is the largest non-negative integer so that $2^K$ divides $T(2^n - 1)$, show that $K = 2^n - n - 1$.
(c) Find the largest non-negative integer $K$ so that $2^K$ divides $T(2^n + 1)$
[u]Round 1[/u]
[b]p1.[/b] Ash is running around town catching Pokémon. Each day, he may add $3, 4$, or $5$ Pokémon to his collection, but he can never add the same number of Pokémon on two consecutive days. What is the smallest number of days it could take for him to collect exactly $100$ Pokémon?
[b]p2.[/b] Jack and Jill have ten buckets. One bucket can hold up to $1$ gallon of water, another can hold up to $2$ gallons, and so on, with the largest able to hold up to $10$ gallons. The ten buckets are arranged in a line as shown below. Jack and Jill can pour some amount of water into each bucket, but no bucket can have less water than the one to its left. Is it possible that together, the ten buckets can hold 36 gallons of water?
[img]https://cdn.artofproblemsolving.com/attachments/f/8/0b6524bebe8fe859fe7b1bc887ac786106fc17.png[/img]
[b]p3.[/b] There are $2023$ knights and liars standing in a row. Knights always tell the truth and liars always lie. Each of them says, “the number of liars to the left of me is greater than the number of knights to the right.” How many liars are there?
[b]p4.[/b] Camila has a deck of $101$ cards numbered $1, 2, ..., 101$. She starts with $50$ random cards in her hand and the rest on a table with the numbers visible. In an exchange, she replaces all $50$ cards in her hand with her choice of $50$ of the $51$ cards from the table. Show that Camila can make at most 50 exchanges and end up with cards $1, 2, ..., 50$.
[img]https://cdn.artofproblemsolving.com/attachments/0/6/c89e65118764f3b593da45264bfd0d89e95067.png[/img]
[b]p5.[/b] There are $101$ pirates on a pirate ship: the captain and $100$ crew. Each pirate, including the captain, starts with $1$ gold coin. The captain makes proposals for redistributing the coins, and the crew vote on these proposals. The captain does not vote. For every proposal, each crew member greedily votes “yes” if he gains coins as a result of the proposal, “no” if he loses coins, and passes otherwise. If strictly more crew members vote “yes” than “no,” the proposal takes effect. The captain can make any number of proposals, one after the other. What is the largest number of coins the captain can accumulate?
[u]Round 2[/u]
[b]p6.[/b] The town of Lumenville has $100$ houses and is preparing for the math festival. The Tesla wiring company will lay lengths of power wire in straight lines between the houses so that power flows between any two houses, possibly by passing through other houses. The Edison lighting company will hang strings of lights in straight lines between pairs of houses so that each house is connected by a string to exactly one other. Show that however the houses are arranged, the Edison company can always hang their strings of lights so that the total length of the strings is no more than the total length of the power wires the Tesla company used.
[img]https://cdn.artofproblemsolving.com/attachments/9/2/763de9f4138b4dc552247e9316175036c649b6.png[/img]
[b]p7.[/b] You are given a sequence of $16$ digits. Is it always possible to select one or more digits in a row, so that multiplying them results in a square number?
[img]https://cdn.artofproblemsolving.com/attachments/d/1/f4fcda2e1e6d4a1f3a56cd1a04029dffcd3529.png[/img]
PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].
Two 100-digit binary sequences are given. In one operation, one may insert (possibly at the beggining or end) or remove one or more identical digits from a sequence. What is the smallest $k{}$ for which we can transform the first sequence into the second one in no more than $k{}$ operations?
[i]Proposed by V. Novikov[/i]
Let $(a_n)_{n\ge 1}$ be a sequence of real numbers such that
\[a_1\binom{n}{1}+a_2\binom{n}{2}+\ldots+a_n\binom{n}{n}=2^{n-1}a_n,\ (\forall)n\in \mathbb{N}^*\]
Prove that $(a_n)_{n\ge 1}$ is an arithmetical progression.
[i]Lucian Dragomir[/i]
Let $a , b , c$ positive integers, coprime. For each whole number $n \ge 1$, we denote by $s ( n )$ the number of elements in the set $\{ a , b , c \}$ that divide $n$. We consider $k_1< k_2< k_3<...$ .the sequence of all positive integers that are divisible by some element of $\{ a , b , c \}$. Finally we define the characteristic sequence of $( a , b , c )$ like the succession $ s ( k_1) , s ( k_2) , s ( k_3) , .... $ .
Prove that if the characteristic sequences of $( a , b , c )$ and $( a', b', c')$ are equal, then $a = a', b = b'$ and $c=c'$
For a positive integer $k$, define the sequence $\{a_n\}_{n\ge 0}$ such that $a_0=1$ and for all positive integers $n$, $a_n$ is the smallest positive integer greater than $a_{n-1}$ for which $a_n\equiv ka_{n-1}\pmod {2017}$. What is the number of positive integers $1\le k\le 2016$ for which $a_{2016}=1+\binom{2017}{2}?$
[i]Proposed by James Lin[/i]
Does there exist an infinite sequence of integers \(a_0\), \(a_1\), \(a_2\), \(\ldots\) such that \(a_0\ne0\) and, for any integer \(n\ge0\), the polynomial \[P_n(x)=\sum_{k=0}^na_kx^k\] has \(n\) distinct real roots?
[i]Proposed by Amol Rama and Espen Slettnes[/i]
Let $ \left(a_{n}\right)$ be the sequence of reals defined by $ a_{1}=\frac{1}{4}$ and the recurrence $ a_{n}= \frac{1}{4}(1+a_{n-1})^{2}, n\geq 2$. Find the minimum real $ \lambda$ such that for any non-negative reals $ x_{1},x_{2},\dots,x_{2002}$, it holds
\[ \sum_{k=1}^{2002}A_{k}\leq \lambda a_{2002}, \]
where $ A_{k}= \frac{x_{k}-k}{(x_{k}+\cdots+x_{2002}+\frac{k(k-1)}{2}+1)^{2}}, k\geq 1$.
Let $x_1=1$, $x_2$, $x_3$, $\ldots$ be a sequence of real numbers such that for all $n\geq 1$ we have \[ x_{n+1} = x_n + \frac 1{2x_n} . \] Prove that \[ \lfloor 25 x_{625} \rfloor = 625 . \]
For $p \in \mathbb{R}$, let $(a_n)_{n \ge 1}$ be the sequence defined by
\[ a_n=\frac{1}{n^p} \int_0^n |\sin( \pi x)|^x \mathrm dx. \]
Determine all possible values of $p$ for which the series $\sum_{n=1}^\infty a_n$ converges.
[url=https://artofproblemsolving.com/community/c893771h1861957p12597232]8.1[/url] The point $E$ lies on the base $[AD]$ of the trapezoid $ABCD$. The perimeters of the triangles $ABE, BCE$ and $CDE$ are equal. Prove that $|BC| = |AD|/2$
[b]8.2[/b] In a convex pentagon, the lengths of all sides are equal. Find the point on the longest diagonal from which all sides are visible underneath angles not exceeding a right angle.
[url=https://artofproblemsolving.com/community/c893771h1862007p12597620]8.3[/url] Every city in the certain state is connected by airlines with no more than with three other ones, but one can get from every city to every other city changing a plane once only or directly. What is the maximal possible number of the cities?
[url=https://artofproblemsolving.com/community/c893771h1861966p12597273]8.4*/7.4*[/url] (asterisk problems in separate posts)
[url=https://artofproblemsolving.com/community/c893771h1862002p12597605]8.5[/url] Four different three-digit numbers starting with the same digit have the property that their sum is divisible by three of them without a remainder. Find these numbers.
[url=https://artofproblemsolving.com/community/c893771h1861967p12597280]8.6[/url] Given a finite sequence of zeros and ones, which has two properties:
a) if in some arbitrary place in the sequence we select five digits in a row and also select five digits in any other place in a row, then these fives will be different (they may overlap);
b) if you add any digit to the right of the sequence, then property (a) will no longer hold true.
Prove that the first four digits of our sequence coincide with the last four.
PS. You should use hide for answers.Collected [url=https://artofproblemsolving.com/community/c3988085_1969_leningrad_math_olympiad]here[/url].
Let $ a_1$, $ a_2$, $ \ldots$, $ a_n$ be distinct positive integers, $ n\ge 3$. Prove that there exist distinct indices $ i$ and $ j$ such that $ a_i \plus{} a_j$ does not divide any of the numbers $ 3a_1$, $ 3a_2$, $ \ldots$, $ 3a_n$.
[i]Proposed by Mohsen Jamaali, Iran[/i]
Let be the sequence $ \left( x_n \right)_{n\ge 1} $ defined as
$$ x_n= \frac{4009}{4018020} x_{n-1} -\frac{1}{4018020} x_{n-2} + \left( 1+\frac{1}{n} \right)^n. $$
Prove that $ \left( x_n \right)_{n\ge 1} $ is convergent and determine its limit.
Let an infinite sequence of measurable sets be given on the interval $ (0,1)$ the measures of which are $ \geq \alpha>0$. Show that there exists a point of $ (0,1)$ which belongs to infinitely many terms of the sequence.
Let bet a sequence $\left( a_n \right)_{n\ge 1} $ with $ a_1=1 $ and defined as $ a_n=\sqrt[n]{1+na_{n-1}} . $
Show that $ \left( a_n \right)_{n\ge 1} $ is convergent and determine its limit.
[i]Florian Dumitrel[/i]
Define a sequence $<f_0 (x), f_1 (x), f_2 (x), \dots>$ of functions by $$f_0 (x) = 1$$ $$f_1(x)=x$$ $$(f_n(x))^2 - 1 = f_{n+1}(x) f_{n-1}(x)$$ for $n \ge 1$. Prove that each $f_n (x)$ is a polynomial with integer coefficients.
Let $a$, $b$ and $c$ positive integers. Three sequences are defined as follows:
[list]
[*] $a_1=a$, $b_1=b$, $c_1=c$[/*]
[*] $a_{n+1}=\lfloor{\sqrt{a_nb_n}}\rfloor$, $\:b_{n+1}=\lfloor{\sqrt{b_nc_n}}\rfloor$, $\:c_{n+1}=\lfloor{\sqrt{c_na_n}}\rfloor$ for $n \ge 1$[/*]
[/list]
[list = a]
[*]Prove that for any $a$, $b$, $c$, there exists a positive integer $N$ such that $a_N=b_N=c_N$.[/*]
[*]Find the smallest $N$ such that $a_N=b_N=c_N$ for some choice of $a$, $b$, $c$ such that $a \ge 2$ y $b+c=2a-1$.[/*]
[/list]
Three cevians concur at a point lying inside a triangle. The feet of these cevians divide the sides into six segments, and the lengths of these segments form (in some order) a geometric progression. Prove that the lengths of the cevians also form a geometric progression.
Three cats--TheInnocentKitten, TheNeutralKitten, and TheGuiltyKitten labelled $P_1, P_2,$ and $P_3$ respectively with $P_{n+3} = P_{n}$--are playing a game with three rounds as follows:
[list=1]
[*] Each round has three turns. For round $r \in \{1,2,3\}$ and turn $t \in \{1,2,3\}$ in that round, player $P_{t+1-r}$ picks a non-negative integer. The turns in each round occur in increasing order of $t$, and the rounds occur in increasing order of $r$.
$\newline
\newline$
[*] [b]Motivations:[/b] Every player focuses primarily on maximizing the sum of their own choices and secondarily on minimizing the total of the other players’ sums. TheNeutralKitten and TheGuiltyKitten have the additional tertiary priority of minimizing TheInnocentKitten’s sum.
$\newline
\newline$
[*] For round $2$, player $P_{2}$ has no choice but to pick the number equal to what player $P_{1}$ chose in round $1$. Likewise, for round $3$, player $P_{3}$ must pick the number equal to what player $P_{2}$ chose in round $2$.
$\newline
\newline$
[*] If not all three players choose their numbers such that the values they chose in rounds 1,2,3 form an arithmetic progression in that order by the end of the game, all players' sums are set to $-1$ regardless of what they have chosen.
$\newline
\newline$
[*] If the sum of the choices in any given round is greater than $100$, all choices that round are set to $0$ at the end of that round. That is, rules $2$, $3$, and $4$ act as if each player chose $0$ that round.
$\newline
\newline$
[*] All players play optimally as per their motivations. Furthermore, all players know that all other players will play optimally (and so on.)
[/list]
Let $A$ and $B$ be TheInnocentKitten's sum and TheGuiltyKitten's sum respectively. Compute $1000A + B$ when all players play optimally.
Proposed by Harry Chen (Extile)
There is an arithmetic progression of $7$ terms in which all the terms are different prime numbers. Determine the smallest possible value of the last term of such a progression.
Clarification: In an arithmetic progression of difference $d$ each term is equal to the previous one plus $d$.
Let $ \{A_n\}_{n \in \mathbb{N}}$ be a sequence of measurable subsets of the real line which covers almost every point infinitely often. Prove, that there exists a set $ B \subset \mathbb{N}$ of zero density, such that $ \{A_n\}_{n \in B}$ also covers almost every point infinitely often. (The set $ B \subset \mathbb{N}$ is of zero density if $ \lim_{n \to \infty} \frac {\#\{B \cap \{0, \dots, n \minus{} 1\}\}}{n} \equal{} 0$.)
[b]R[/b]thea, a distant planet, is home to creatures whose DNA consists of two (distinguishable) strands of bases with a fixed orientation. Each base is one of the letters H, M, N, T, and each strand consists of a sequence of five bases, thus forming five pairs. Due to the chemical properties of the bases, each pair must consist of distinct bases. Also, the bases H and M cannot appear next to each other on the same strand; the same is true for N and T. How many possible DNA sequences are there on Rthea?
Define a sequence $(a_n)$ recursively by $a_1=0, a_2=2, a_3=3$ and $a_n=\max_{0<d<n} a_d \cdot a_{n-d}$ for $n \ge 4$. Determine the prime factorization of $a_{19702020}$.
[b]p7[/b] Cindy cuts regular hexagon $ABCDEF$ out of a sheet of paper. She folds $B$ over $AC$, resulting in a pentagon. Then, she folds $A$ over $CF$, resulting in a quadrilateral. The area of $ABCDEF$ is $k$ times the area of the resulting folded shape. Find $k$.
[b]p8[/b] Call a sequence $\{a_n\} = a_1, a_2, a_3, . . .$ of positive integers [i]Fib-o’nacci[/i] if it satisfies $a_n = a_{n-1}+a_{n-2}$ for all $n \ge 3$. Suppose that $m$ is the largest even positive integer such that exactly one [i]Fib-o’nacci[/i] sequence satisfies $a_5 = m$, and suppose that $n$ is the largest odd positive integer such that exactly one [i]Fib-o’nacci[/i] sequence satisfies $a_5 = n$. Find $mn$.
[b]p9[/b] Compute the number of ways there are to pick three non-empty subsets $A$, $B$, and $C$ of $\{1, 2, 3, 4, 5, 6\}$, such that $|A| = |B| = |C|$ and the following property holds:
$$A \cap B \cap C = A \cap B = B \cap C = C \cap A.$$
Is it possible to partition all positive integers into disjoint sets $A$ and $B$ such that
(i) no three numbers of $A$ form an arithmetic progression,
(ii) no infinite non-constant arithmetic progression can be formed by numbers of $B$?