Found problems: 295
Let $S$ be a set of rational numbers such that whenever $a$ and $b$ are members of $S$, so are $ab$ and $a+b$, and having the property that for every rational number $r$ exactly one of the following three statements is true:
$$r\in S,\;\; -r\in S,\;\;r =0.$$
Prove that $S$ is the set of all positive rational numbers.
Let $A=\{n\in\mathbb{Z}\mid 0<n<2013\}$. A subset $B\subseteq A$ is called [b]reduced[/b] if for any two numbers $x,y\in B$, we must have $x\cdot y \notin B$. For example, any subset containing the numbers $3,5,15$ cannot be reduced, and same for a subset containing $4,16$.
[list=a]
[*] Find the maximal size of a reduced subset of $A$.
[*] How many reduced subsets are there with that maximal size?
[/list]
Find the minimum value of $k$ such that there exists two sequence ${a_i},{b_i}$ for $i=1,2,\cdots ,k$ that satisfies the following conditions.
(i) For all $i=1,2,\cdots ,k,$ $a_i,b_i$ is the element of $S=\{1996^n|n=0,1,2,\cdots\}.$
(ii) For all $i=1,2,\cdots, k, a_i\ne b_i.$
(iii) For all $i=1,2,\cdots, k, a_i\le a_{i+1}$ and $b_i\le b_{i+1}.$
(iv) $\sum_{i=1}^{k} a_i=\sum_{i=1}^{k} b_i.$
Find the maximal cardinality $|S|$ of the subset $S \subset A=\{1, 2, 3, \dots, 9\}$ given that no two sums $a+b | a, b \in S, a \neq b$ are equal.
Let $n > 3$ be an integer. Let $\Omega$ be the set of all triples of distinct elements of
$\{1, 2, \ldots , n\}$. Let $m$ denote the minimal number of colours which suffice to colour $\Omega$ so that whenever
$1\leq a<b<c<d \leq n$, the triples $\{a,b,c\}$ and $\{b,c,d\}$ have different colours. Prove that $\frac{1}{100}\log\log n \leq m \leq100\log \log n$.
Let \(S\) be a set with 10 distinct elements. A set \(T\) of subsets of \(S\) (possibly containing the empty set) is called [i]union-closed[/i] if, for all \(A, B \in T\), it is true that \(A \cup B \in T\). Show that the number of union-closed sets \(T\) is less than \(2^{1023}\).
[i]Proposed by Tony Wang[/i]
A set $A$ is endowed with a binary operation $*$ satisfying the following four conditions:
(1) If $a, b, c$ are elements of $A$, then $a * (b * c) = (a * b) * c$ ,
(2) If $a, b, c$ are elements of $A$ such that $a * c = b *c$, then $a = b$ ,
(3) There exists an element $e$ of $A$ such that $a * e = a$ for all $a$ in $A$, and
(4) If a and b are distinct elements of $A-\{e\}$, then $a^3 * b = b^3 * a^2$, where $x^k = x * x^{k-1}$ for all integers $k \ge 2$ and all $x$ in $A$.
Determine the largest cardinality $A$ may have.
proposed by Bojan Basic, Serbia
Let $n$ be a positive integer. What is the smallest value of $m$ with $m > n$ such that the set $M = \{n, n + 1, ..., m\}$ can be partitioned into subsets so that in each subset, there is a number which equals to the sum of all other numbers of this subset?
It is known that subsets $A_1,A_2, \cdots , A_n$ of set $I=\{1,2,\cdots ,101\}$ satisfy the following condition
$$\text{For any } i,j \text{ } (1 \leq i < j \leq n) \text{, there exists } a,b \in A_i \cap A_j \text{ so that } (a,b)=1$$
Determine the maximum positive integer $n$.
*$(a,b)$ means $\gcd (a,b)$
There are some boys and girls that study in a school. A group of boys is called [i]sociable[/i], if each girl knows at least one of the boys in the group. A group of girls is called [i]sociable[/i], if each boy knows at least one of the girls in the group. If the number of [i]sociable[/i] groups of boys is odd, prove that the number of [i]sociable[/i] groups of girls is also odd.
Let $\mathbb N$ denote the set of all natural numbers. Show that there exists two nonempty subsets $A$ and $B$ of $\mathbb N$ such that
[list=1]
[*] $A\cap B=\{1\};$
[*] every number in $\mathbb N$ can be expressed as the product of a number in $A$ and a number in $B$;
[*] each prime number is a divisor of some number in $A$ and also some number in $B$;
[*] one of the sets $A$ and $B$ has the following property: if the numbers in this set are written as $x_1<x_2<x_3<\cdots$, then for any given positive integer $M$ there exists $k\in \mathbb N$ such that $x_{k+1}-x_k\ge M$.
[*] Each set has infinitely many composite numbers.
[/list]
Let $ Z $ be a set of $ n $ elements. Find the number of such pairs of sets $ (A, B) $ such that $ A $ is contained in $ B $ and $ B $ is contained in $ Z $. We assume that every set also contains itself and the empty set.
Find all sets $S$ of positive integers that satisfy all of the following.
$1.$ If $a,b$ are two not necessarily distinct elements in $S$, then $\gcd(a,b)$, $ab$ are also in $S$.
$2.$ If $m,n$ are two positive integers with $n\nmid m$, then there exists an element $s$ in $S$ such that $m^2\mid s$ and $n^2\nmid s$.
$3.$ For any odd prime $p$, the set formed by moduloing all elements in $S$ by $p$ has size exactly $\frac{p+1}2$.
For a positive integer $n$, ($n\ge 2$), find the number of sets with $2n + 1$ points $P_0, P_1,..., P_{2n}$ in the coordinate plane satisfying the following as its elements:
- $P_0 = (0, 0),P_{2n}= (n, n)$
- For all $i = 1,2,..., 2n - 1$, line $P_iP_{i+1}$ is parallel to $x$-axis or $y$-axis and its length is $1$.
- Out of $2n$ lines$P_0P_1, P_1P_2,..., P_{2n-1}P_{2n}$, there are exactly $4$ lines that are enclosed in the domain $y \le x$.
Let $S$ be a finite, nonempty set of real numbers such that the distance between any two distinct points in $S$ is an element of $S$. In other words, $|x-y|$ is in $S$ whenever $x \ne y$ and $x$ and $y$ are both in $S$.
Prove that the elements of $S$ may be arranged in an arithmetic progression.
This means that there are numbers $a$ and $d$ such that $S = \{a, a+d, a+2d, a+3d, ..., a+kd, ...\}$.
Consider all possible sets of natural numbers $(x_1, x_2, ..., x_{100})$ such that $1\leq x_i \leq 2017$ for every $i = 1,2, ..., 100$. We say that the set $(y_1, y_2, ..., y_{100})$ is greater than the set $(z_1, z_2, ..., z_{100})$ if $y_i> z_i$ for every $i = 1,2, ..., 100$. What is the largest number of sets that can be written on the board, so that any set is not more than the other set?
Given a set $A$ of positive integers, the set $A'$ is composed from the elements of $A$ and all positive integers that can be obtained in the following way:
Write down some elements of $A$ one after another without repeating, write a sign $+ $ or $-$ before each of them, and evaluate the obtained expression. The result is included in $A'$.
For example, if $A = \{2,8,13,20\}$, numbers $8$ and $14 = 20-2+8$ are elements of $A'$.
Set $A''$ is constructed from $A'$ in the same manner.
Find the smallest possible number of elements of $A$, if $A''$ contains all the integers from $1$ to $40$.
Let $A$ be the set of odd integers $\leq 2n-1.$ For a positive integer $m$, let $B=\{a+m\,|\, a\in A \}.$ Determine for which positive integers $n$ there exists a positive integer $m$ such that the product of all elements in $A$ and $B$ is a square.
Givan the set $S = \{1,2,3,....,n\}$. We want to partition the set $S$ into three subsets $A,B,C$ disjoint (to each other) with $A\cup B\cup C=S$ , such that the sums of their elements $S_{A} S_{B} S_{C}$ to be equal .Examine if this is possible when:
a) $n=2014$
b) $n=2015 $
c) $n=2018$
Let $K$ be a convex planar set, symmetric about a point $O$, and let $X, Y , Z$ be three points in $K$. Show that $K$ contains the head of one of the vectors $\overrightarrow{OX} \pm \overrightarrow{OY} , \overrightarrow{OX} \pm \overrightarrow{OZ}, \overrightarrow{OY} \pm \overrightarrow{OZ}$.
What is the number of ordered pairs $(A,B)$ where $A$ and $B$ are subsets of $\{1,2,..., 5\}$ such that neither $A \subseteq B$ nor $B \subseteq A$?
Defined as $N_0$ as the set of all non-negative integers. Set $S \subset N_0$ with not so many elements is called beautiful if for every $a, b \in S$ with $a \ge b$ ($a$ and $b$ do not have to be different), exactly one of $a + b$ or $a - b$ is in $S$. Set $T \subset N_0$ with not so many elements is called charming if the largest number $k$ such that up to 3$^k | a$ is the same for each element $a \in T$. Prove that each beautiful set must be charming.
Let $S$ be the set of points $(x,y)$ in the coordinate plane such that two of the three quantities $3$, $x+2$, and $y-4$ are equal and the third of the three quantities is no greater than this common value. Which of the following is a correct description of $S$?
$\textbf{(A) } \text{a single point} \qquad \textbf{(B) } \text{two intersecting lines} \\ \\ \textbf{(C) } \text{three lines whose pairwise intersections are three distinct points} \\ \\ \textbf{(D) } \text{a triangle} \qquad \textbf{(E) } \text{three rays with a common endpoint}$
Prove that there exist infinitely many pairwisely disjoint sets $A(1), A(2),...,A(2014)$ which are not empty, whose union is the set of positive integers and which satisfy the following condition:
For arbitrary positive integers $a$ and $b$, at least two of the numbers $a$, $b$ and $GCD(a,b)$ belong to one of the sets $A(1), A(2),...,A(2014)$.
A collection $F$ of distinct (not necessarily non-empty) subsets of $X = \{1,2,\ldots,300\}$ is [i]lovely[/i] if for any three (not necessarily distinct) sets $A$, $B$ and $C$ in $F$ at most three out of the following eight sets are non-empty
\begin{align*}A \cap B \cap C, \ \ \ \overline{A} \cap B \cap C, \ \ \ A \cap \overline{B} \cap C, \ \ \ A \cap B \cap \overline{C}, \\ \overline{A} \cap \overline{B} \cap C, \ \ \ \overline{A} \cap B \cap \overline {C}, \ \ \ A \cap \overline{B} \cap \overline{C}, \ \ \ \overline{A} \cap \overline{B} \cap \overline{C}
\end{align*}
where $\overline{S}$ denotes the set of all elements of $X$ which are not in $S$.
What is the greatest possible number of sets in a lovely collection?