Call a permutation $a_1,a_2,\ldots,a_n$ [i]quasi-increasing[/i] if $a_k\le a_{k+1}+2$ for each $1\le k\le n-1$. For example, $54321$ and $14253$ are quasi-increasing permutations of the integers $1,2,3,4,5$, but $45123$ is not. Find the number of quasi-increasing permutations of the integers $1,2,\ldots,7$.

assume that we have a n*n table we fill it with 1,...,n such that each number exists exactly n times prove that there exist a row or column such that at least $\sqrt{n}$ diffrent number are contained.

In a game show, Bob is faced with $ 7$ doors, $ 2$ of which hide prizes. After he chooses a door, the host opens three other doors, of which one is hiding a prize. Bob chooses to switch to another door. What is the probability that his new door is hiding a prize?

Prove that there exists a positive $ c$ such that for every positive integer $ N$ among any $ N$ positive integers not exceeding $ 2N$ there are two numbers whose greatest common divisor is greater than $ cN$.

The following diagram shows four vertices connected by six edges. Suppose that each of the edges is randomly painted either red, white, or blue. The probability that the three edges adjacent to at least one vertex are colored with all three colors is $\frac{m}{n}$ , where $m$ and $n$ are relatively prime positive integers. Find $m + n$. [img]https://cdn.artofproblemsolving.com/attachments/6/4/de0a2a1a659011a30de1859052284c696822bb.png[/img]

When $n$ standard 6-sided dice are rolled, the probability of obtaining a sum of 1994 is greater than zero and is the same as the probability of obtaining a sum of $S$. The smallest possible value of $S$ is $ \textbf{(A)}\ 333 \qquad\textbf{(B)}\ 335 \qquad\textbf{(C)}\ 337 \qquad\textbf{(D)}\ 339 \qquad\textbf{(E)}\ 341 $

If $a,b$ and $c$ are three (not necessarily different) numbers chosen randomly and with replacement from the set $\{1,2,3,4,5 \}$, the probability that $ab+c$ is even is $\textbf{(A)}\ \dfrac{2}{5} \qquad \textbf{(B)}\ \dfrac{59}{125} \qquad \textbf{(C)}\ \dfrac{1}{2} \qquad \textbf{(D)}\ \dfrac{64}{125} \qquad \textbf{(E)}\ \dfrac{3}{5}$

Let $\{x_n\}_{n\geq 0}$ be a sequence of real numbers which satisfy \[ (x_{n+1} - x_n)(x_{n+1}+x_n+1) \leq 0, \quad n\geq 0. \] a) Prove that the sequence is bounded; b) Is it possible that the sequence is not convergent?

Let $p$ be a constant number such that $0<p<1$. Evaluate \[\sum_{k=0}^{2004} \frac{p^k (1-p)^{2004-k}}{\displaystyle \int_0^1 x^k (1-x)^{2004-k} dx}\]

Real numbers between 0 and 1, inclusive, are chosen in the following manner. A fair coin is flipped. If it lands heads, then it is flipped again and the chosen number is 0 if the second flip is heads and 1 if the second flip is tails. On the other hand, if the first coin flip is tails, then the number is chosen uniformly at random from the closed interval $[0,1]$. Two random numbers $x$ and $y$ are chosen independently in this manner. What is the probability that $|x-y| > \tfrac{1}{2}$? $\textbf{(A)} \frac{1}{3} \qquad \textbf{(B)} \frac{7}{16} \qquad \textbf{(C)} \frac{1}{2} \qquad \textbf{(D)} \frac{9}{16} \qquad \textbf{(E)} \frac{2}{3}$

For a given number $ n $, let us denote by $ p_n $ the probability that when randomly selecting a pair of integers $ k, m $ satisfying the conditions $ 0 \leq k \leq m \leq 2^n $ (the selection of each pair is equally probable) the number $\binom{m}{k}$ will be even. Calculate $ \lim_{n\to \infty} p_n $.

At Rachelle's school an A counts 4 points, a B 3 points, a C 2 points, and a D 1 point. Her GPA on the four classes she is taking is computed as the total sum of points divided by $4$. She is certain that she will get As in both Mathematics and Science, and at least a C in each of English and History. She think she has a $\frac{1}{6}$ chance of getting an A in English, and a $\frac{1}{4}$ chance of getting a B. In History, she has a $\frac{1}{4}$ chance of getting an A, and a $\frac{1}{3}$ chance of getting a B, independently of what she gets in English. What is the probability that Rachelle will get a GPA of at least 3.5? $\textbf{(A) }\frac{11}{72}\qquad\textbf{(B) }\frac{1}{6}\qquad\textbf{(C) }\frac{3}{16}\qquad\textbf{(D) }\frac{11}{24}\qquad\textbf{(E) }\frac{1}{2}$

Sophie has $20$ indistinguishable pairs of socks in a laundry bag. She pulls them out one at a time. After pulling out $30$ socks, the expected number of unmatched socks among the socks that she has pulled out can be expressed in simplest form as $\tfrac{m}{n}$. Find $m+n$.

An exam at a university consists of one question randomly selected from the$ n$ possible questions. A student knows only one question, but he can take the exam $n$ times. Express as a function of $n$ the probability $p_n$ that the student will pass the exam. Does $p_n$ increase or decrease as $n$ increases? Compute $lim_{n\to \infty}p_n$. What is the largest lower bound of the probabilities $p_n$?

Ahuiliztli is playing around with some coins (pennies, nickels, dimes, and quarters). She keeps grabbing $k$ coins and calculating the value of her handful. After a while, she begins to notice that if $k$ is even, she more often gets even sums, and if $k$ is odd, she more often gets odd sums. Help her prove this true! Given $k$ coins chosen uniformly and at random, prove that. the probability that the parity of $k$ is the same as the parity of the $k$ coins' value is greater than the probability that the parities are different.

In the game of "Fingers", $N$ players stand in a circle and simultaneously thrust out their right hands, each with a certain number of fingers showing. The total number of fingers shown is counted out round the circle from the leader, and the player on whom the count stops is the winner. How large must $N$ be for a suitably chosen group of $N/10$ players to contain a winner with probability at least $0.9$? How does the probability that the leader wins behave as $N\to\infty$?

Nine tiles are numbered $1, 2, 3, \ldots, 9,$ respectively. Each of three players randomly selects and keeps three of the tile, and sums those three values. The probability that all three players obtain an odd sum is $m/n,$ where $m$ and $n$ are relatively prime positive integers. Find $m+n.$

A robot on the number line starts at $1$. During the first minute, the robot writes down the number $1$. Each minute thereafter, it moves by one, either left or right, with equal probability. It then multiplies the last number it wrote by $n/t$, where $n$ is the number it just moved to, and $t$ is the number of minutes elapsed. It then writes this number down. For example, if the robot moves right during the second minute, it would write down $2/2=1$. Find the expected sum of all numbers it writes down, given that it is finite. [i]Proposed by Ethan Tan[/i]

Wendy randomly chooses a positive integer less than or equal to $2020$. The probability that the digits in Wendy's number add up to $10$ is $\frac{m}{n}$ , where $m$ and $n$ are relatively prime positive integers. Find $m + n$.

Let $S$ be a set of size $11$. A random $12$-tuple $(s_1, s_2, . . . , s_{12})$ of elements of $S$ is chosen uniformly at random. Moreover, let $\pi : S \to S$ be a permutation of $S$ chosen uniformly at random. The probability that $s_{i+1}\ne \pi (s_i)$ for all $1 \le i \le 12$ (where $s_{13} = s_1$) can be written as $\frac{a}{b}$ where $a$ and $b$ are relatively prime positive integers. Compute $a$.

For $\{1, 2, 3, \dots, n\}$ and each of its nonempty subsets a unique [b]alternating sum[/b] is defined as follows: Arrange the numbers in the subset in decreasing order and then, beginning with the largest, alternately add and subtract successive numbers. (For example, the alternating sum for $\{1, 2, 4, 6, 9\}$ is $9 - 6 + 4 - 2 + 1 = 6$ and for $\{5\}$ it is simply 5.) Find the sum of all such alternating sums for $n = 7$.

Alex, Pei-Hsin, and Edward got together before the contest to send a mailing to all the invited schools. Pei-Hsin usually just stuffs the envelopes, but if Alex leaves the room she has to lick them as well and has a $25\%$ chance of dying from an allergic reaction before he gets back. Licking the glue makes Edward a bit psychotic, so if Alex leaves the room there is a $20\%$ chance that Edward will kill Pei-Hsin before she can start licking envelopes. Alex leaves the room and comes back to find Pei-Hsin dead. What is the probability that Edward was responsible?

A natural number $n$, which is at most $500$, has the property that when one chooses at at random among the numbers $1, 2, 3,...,499, 500$, then the probability is $\frac{1}{100}$ for $m$ to add up to $n$. Determine the largest possible value of $n$.

The faces of each of $7$ standard dice are labeled with the integers from $1$ to $6$. Let $p$ be the probability that when all $7$ dice are rolled, the sum of the numbers on the top faces is $10$. What other sum occurs with the same probability as $p$? $\textbf{(A)} \text{ 13} \qquad \textbf{(B)} \text{ 26} \qquad \textbf{(C)} \text{ 32} \qquad \textbf{(D)} \text{ 39} \qquad \textbf{(E)} \text{ 42}$

Yannick is playing a game with $100$ rounds, starting with $1$ coin. During each round, there is an $n\%$ chance that he gains an extra coin, where $n$ is the number of coins he has at the beginning of the round. What is the expected number of coins he will have at the end of the game?