Found problems: 21
Let $ A \equal{} (a_{ij})$, where $ i,j \equal{} 1,2,\ldots,n$, be a square matrix with all $ a_{ij}$ non-negative integers. For each $ i,j$ such that $ a_{ij} \equal{} 0$, the sum of the elements in the $ i$th row and the $ j$th column is at least $ n$. Prove that the sum of all the elements in the matrix is at least $ \frac {n^2}{2}$.
A permutation $ \{x_1, x_2, \ldots, x_{2n}\}$ of the set $ \{1,2, \ldots, 2n\}$ where $ n$ is a positive integer, is said to have property $ T$ if $ |x_i \minus{} x_{i \plus{} 1}| \equal{} n$ for at least one $ i$ in $ \{1,2, \ldots, 2n \minus{} 1\}.$ Show that, for each $ n$, there are more permutations with property $ T$ than without.
The numbers of the set $\{1,2,\ldots,n\}$ are colored with $6$ colors. Let
$$S:=\{(x,y,z)\in\{1,2,\ldots,n\}^3:x+y+z\equiv0\pmod n\text{ and }x,y,z\text{ have the same color}\}$$and
$$D:=\{(x,y,z)\in\{1,2,\ldots,n\}^3:x+y+z\equiv0\pmod n\text{ and }x,y,z\text{ have three different colors}\}.$$Prove that
$$|D|\le2|S|+\frac{n^2}2.$$
$(CZS 4)$ Let $K_1,\cdots , K_n$ be nonnegative integers. Prove that $K_1!K_2!\cdots K_n! \ge \left[\frac{K}{n}\right]!^n$, where $K = K_1 + \cdots + K_n$
For any polynomial $P(x)=a_0+a_1x+\ldots+a_kx^k$ with integer coefficients, the number of odd coefficients is denoted by $o(P)$. For $i-0,1,2,\ldots$ let $Q_i(x)=(1+x)^i$. Prove that if $i_1,i_2,\ldots,i_n$ are integers satisfying $0\le i_1<i_2<\ldots<i_n$, then: \[ o(Q_{i_{1}}+Q_{i_{2}}+\ldots+Q_{i_{n}})\ge o(Q_{i_{1}}). \]
At a party attended by $n$ married couples, each person talks to everyone else at the party except his or her spouse. The conversations involve sets of persons or cliques $C_1, C_2, \cdots, C_k$ with the following property: no couple are members of the same clique, but for every other pair of persons there is exactly one clique to which both members belong. Prove that if $n \geq 4$, then $k \geq 2n$.
[i]Proposed by USA.[/i]
$(CZS 4)$ Let $K_1,\cdots , K_n$ be nonnegative integers. Prove that $K_1!K_2!\cdots K_n! \ge \left[\frac{K}{n}\right]!^n$, where $K = K_1 + \cdots + K_n$
For any polynomial $P(x)=a_0+a_1x+\ldots+a_kx^k$ with integer coefficients, the number of odd coefficients is denoted by $o(P)$. For $i-0,1,2,\ldots$ let $Q_i(x)=(1+x)^i$. Prove that if $i_1,i_2,\ldots,i_n$ are integers satisfying $0\le i_1<i_2<\ldots<i_n$, then: \[ o(Q_{i_1}+Q_{i_2}+\ldots+Q_{i_n})\ge o(Q_{i_1}). \]
A permutation $ \{x_1, x_2, \ldots, x_{2n}\}$ of the set $ \{1,2, \ldots, 2n\}$ where $ n$ is a positive integer, is said to have property $ T$ if $ |x_i \minus{} x_{i \plus{} 1}| \equal{} n$ for at least one $ i$ in $ \{1,2, \ldots, 2n \minus{} 1\}.$ Show that, for each $ n$, there are more permutations with property $ T$ than without.
For any polynomial $P(x)=a_0+a_1x+\ldots+a_kx^k$ with integer coefficients, the number of odd coefficients is denoted by $o(P)$. For $i-0,1,2,\ldots$ let $Q_i(x)=(1+x)^i$. Prove that if $i_1,i_2,\ldots,i_n$ are integers satisfying $0\le i_1<i_2<\ldots<i_n$, then: \[ o(Q_{i_{1}}+Q_{i_{2}}+\ldots+Q_{i_{n}})\ge o(Q_{i_{1}}). \]
Let $ n$ and $ k$ be positive integers and let $ S$ be a set of $ n$ points in the plane such that
[b]i.)[/b] no three points of $ S$ are collinear, and
[b]ii.)[/b] for every point $ P$ of $ S$ there are at least $ k$ points of $ S$ equidistant from $ P.$
Prove that:
\[ k < \frac {1}{2} \plus{} \sqrt {2 \cdot n}
\]
Let $ A \equal{} (a_{ij})$, where $ i,j \equal{} 1,2,\ldots,n$, be a square matrix with all $ a_{ij}$ non-negative integers. For each $ i,j$ such that $ a_{ij} \equal{} 0$, the sum of the elements in the $ i$th row and the $ j$th column is at least $ n$. Prove that the sum of all the elements in the matrix is at least $ \frac {n^2}{2}$.
A permutation $ \{x_1, x_2, \ldots, x_{2n}\}$ of the set $ \{1,2, \ldots, 2n\}$ where $ n$ is a positive integer, is said to have property $ T$ if $ |x_i \minus{} x_{i \plus{} 1}| \equal{} n$ for at least one $ i$ in $ \{1,2, \ldots, 2n \minus{} 1\}.$ Show that, for each $ n$, there are more permutations with property $ T$ than without.
Let $ n$ and $ k$ be positive integers and let $ S$ be a set of $ n$ points in the plane such that
[b]i.)[/b] no three points of $ S$ are collinear, and
[b]ii.)[/b] for every point $ P$ of $ S$ there are at least $ k$ points of $ S$ equidistant from $ P.$
Prove that:
\[ k < \frac {1}{2} \plus{} \sqrt {2 \cdot n}
\]
At a party attended by $n$ married couples, each person talks to everyone else at the party except his or her spouse. The conversations involve sets of persons or cliques $C_1, C_2, \cdots, C_k$ with the following property: no couple are members of the same clique, but for every other pair of persons there is exactly one clique to which both members belong. Prove that if $n \geq 4$, then $k \geq 2n$.
[i]Proposed by USA.[/i]
Let $p >3$ be a prime number. For each nonempty subset $T$ of $\{0,1,2,3, \ldots , p-1\}$, let $E(T)$ be the set of all $(p-1)$-tuples $(x_1, \ldots ,x_{p-1} )$, where each $x_i \in T$ and $x_1+2x_2+ \ldots + (p-1)x_{p-1}$ is divisible by $p$ and let $|E(T)|$ denote the number of elements in $E(T)$. Prove that
\[|E(\{0,1,3\})| \geq |E(\{0,1,2\})|\]
with equality if and only if $p = 5$.
Let $ n$ and $ k$ be positive integers and let $ S$ be a set of $ n$ points in the plane such that
[b]i.)[/b] no three points of $ S$ are collinear, and
[b]ii.)[/b] for every point $ P$ of $ S$ there are at least $ k$ points of $ S$ equidistant from $ P.$
Prove that:
\[ k < \frac {1}{2} \plus{} \sqrt {2 \cdot n}
\]
Let $ A \equal{} (a_{ij})$, where $ i,j \equal{} 1,2,\ldots,n$, be a square matrix with all $ a_{ij}$ non-negative integers. For each $ i,j$ such that $ a_{ij} \equal{} 0$, the sum of the elements in the $ i$th row and the $ j$th column is at least $ n$. Prove that the sum of all the elements in the matrix is at least $ \frac {n^2}{2}$.
For any permutation $p$ of set $\{1, 2, \ldots, n\}$, define $d(p) = |p(1) - 1| + |p(2) - 2| + \ldots + |p(n) - n|$. Denoted by $i(p)$ the number of integer pairs $(i, j)$ in permutation $p$ such that $1 \leqq < j \leq n$ and $p(i) > p(j)$. Find all the real numbers $c$, such that the inequality $i(p) \leq c \cdot d(p)$ holds for any positive integer $n$ and any permutation $p.$
The matrix
\[A=\begin{pmatrix} a_{11} & \ldots & a_{1n} \\ \vdots & \ldots & \vdots \\ a_{n1} & \ldots & a_{nn} \end{pmatrix}\]
satisfies the inequality $\sum_{j=1}^n |a_{j1}x_1 + \cdots+ a_{jn}x_n| \leq M$ for each choice of numbers $x_i$ equal to $\pm 1$. Show that
\[|a_{11} + a_{22} + \cdots+ a_{nn}| \leq M.\]
The matrix
\[A=\begin{pmatrix} a_{11} & \ldots & a_{1n} \\ \vdots & \ldots & \vdots \\ a_{n1} & \ldots & a_{nn} \end{pmatrix}\]
satisfies the inequality $\sum_{j=1}^n |a_{j1}x_1 + \cdots+ a_{jn}x_n| \leq M$ for each choice of numbers $x_i$ equal to $\pm 1$. Show that
\[|a_{11} + a_{22} + \cdots+ a_{nn}| \leq M.\]