PEN O Problems

Part of PEN Problems

Subcontests

(58)

1

O 59

a_{1} < a_{2} < a_{3} < \cdots

be an infinite increasing sequence of positive integers in which the number of prime factors of each term, counting repeated factors, is never more than

1987

. Prove that it is always possible to extract from

A

an infinite subsequence

b_{1} < b_{2} < b_{3} < \cdots

such that the greatest common divisor

(b_i, b_j)

is the same number for every pair of its terms.

1

O 58

Prove that every infinite sequence

S

of distinct positive integers contains either an infinite subsequence such that for every pair of terms, neither term ever divides the other, or an infinite subsequence such that in every pair of terms, one always divides the other.

1

O 57

Prove that every selection of

1325

M=\{1, 2, \cdots, 1987 \}

must contain some three numbers

\{a, b, c\}

which are pairwise relatively prime, but that it can be avoided if only

1324

integers are selected.

1

O 56

Show that it is possible to color the set of integers

M=\{ 1, 2, 3, \cdots, 1987 \},

using four colors, so that no arithmetic progression with

10

terms has all its members the same color.

1

O 55

M

consists of integers, the smallest of which is

1

and the greatest

100

. Each member of

M

1

, is the sum of two (possibly identical) numbers in

M

. Of all such sets, find one with the smallest possible number of elements.

1

O 54

S

\{1, 2, 3, \cdots, 1989 \}

in which no two members differ by exactly

4

7

. What is the largest number of elements

S

1

O 53

Suppose that the set

M=\{1,2,\cdots,n\}

t

disjoint subsets

M_{1}

\cdots

M_{t}

where the cardinality of

M_i

m_{i}

m_{i} \ge m_{i+1}

i=1,\cdots,t-1

n>t!\cdot e

then at least one class

M_z

contains three elements

x_{i}

x_{j}

x_{k}

with the property that

x_{i}-x_{j}=x_{k}

1

O 52

S

of positive integers such that a number is in

S

if and only if it is the sum of two distinct members of

S

or a sum of two distinct positive integers not in

S

1

O 51

Prove the among

16

consecutive integers it is always possible to find one which is relatively prime to all the rest.

1

O 50

What's the largest number of elements that a set of positive integers between

1

100

inclusive can have if it has the property that none of them is divisible by another?

1

O 49

Consider the set of all five-digit numbers whose decimal representation is a permutation of the digits

1, 2, 3, 4, 5

. Prove that this set can be divided into two groups, in such a way that the sum of the squares of the numbers in each group is the same.

1

O 48

a_{1}, \cdots, a_{44}

be natural numbers such that

0<a_{1}<a_{2}< \cdots < a_{44}<125.

Prove that at least one of the

43

d_{j}=a_{j+1}-a_{j}

occurs at least

10

1

O 47

S

be the set of all composite positive odd integers less than

79

. [*] Show that

S

may be written as the union of three (not necessarily disjoint) arithmetic progressions.[*] Show that

S

cannot be written as the union of two arithmetic progressions.

1

O 46

p

is a prime with

p \equiv 3 \; \pmod{4}

. Show that for any set of

p-1

consecutive integers, the set cannot be divided two subsets so that the product of the members of the one set is equal to the product of the members of the other set.

1

O 45

Find all positive integers

n

with the property that the set

\{n,n+1,n+2,n+3,n+4,n+5\}

can be partitioned into two sets such that the product of the numbers in one set equals the product of the numbers in the other set.

1

O 44

C

of positive integers is called good if for every integer

k

there exist distinct

a, b \in C

such that the numbers

a+k

b+k

are not relatively prime. Prove that if the sum of the elements of a good set

C

2003

, then there exists

c \in C

such that the set

C-\{c\}

1

O 43

Is it possible to find a set

A

of eleven positive integers such that no six elements of

A

have a sum which is divisible by

6

1

O 42

N_{n}

denote the number of ordered

n

-tuples of positive integers

(a_{1},a_{2},\ldots,a_{n})

1/a_{1}+1/a_{2}+\ldots+1/a_{n}=1.

Determine whether

N_{10}

is even or odd.

1

O 41

Prove that for every positive integer

n

there exists an

n

-digit number divisible by

5^n

all of whose digits are odd.

1

O 40

X

be a non-empty set of positive integers which satisfies the following: [*] if

x \in X

4x \in X

x \in X

\lfloor \sqrt{x}\rfloor \in X

X=\mathbb{N}

1

O 39

Find the smallest positive integer

n

for which there exist

n

different positive integers

a_{1}, a_{2}, \cdots, a_{n}

\text{lcm}(a_1,a_2,\cdots,a_n)=1985

i, j \in \{1, 2, \cdots, n \}

gcd(a_i,a_j)\not=1

, [*] the product

a_{1}a_{2} \cdots a_{n}

is a perfect square and is divisible by

243

, and find all such

n

(a_{1}, \cdots, a_{n})

1

O 38

Prove that for every real number

M

there exists an infinite arithmetical progression of positive integers such that [*] the common difference is not divisible by

10

, [*] the sum of digits of each term exceeds

M

1

O 37

n

k

be positive integers such that

n

is not divisible by

3

k\ge n

. Prove that there exists a positive integer m which is divisible by

n

and the sum of its digits in the decimal representation is

k

1

O 36

Let a and b be non-negative integers such that

ab \ge c^{2}

c

is an integer. Prove that there is a positive integer n and integers

x_{1}

x_{2}

\cdots

x_{n}

y_{1}

y_{2}

\cdots

y_{n}

{x_{1}}^{2}+\cdots+{x_{n}}^{2}=a,\;{y_{1}}^{2}+\cdots+{y_{n}}^{2}=b,\; x_{1}y_{1}+\cdots+x_{n}y_{n}=c

1

O 35

n \ge 3

be a prime number and

a_{1} < a_{2} < \cdots < a_{n}

be integers. Prove that

a_{1}, \cdots,a_{n}

is an arithmetic progression if and only if there exists a partition of

\{0, 1, 2, \cdots \}

A_{1},A_{2},\cdots,A_{n}

such that a_{1} \plus{} A_{1} \equal{} a_{2} \plus{} A_{2} \equal{} \cdots \equal{} a_{n} \plus{} A_{n}, where x \plus{} A denotes the set \{x \plus{} a \vert a \in A \}.

1

O 34

Determine for which positive integers

k

X=\{1990, 1990+1, 1990+2, \cdots, 1990+k \}

can be partitioned into two disjoint subsets

A

B

such that the sum of the elements of

A

is equal to the sum of the elements of

B

1

O 33

Assume that the set of all positive integers is decomposed into

r

disjoint subsets

A_{1}, A_{2}, \cdots, A_{r}

A_{1} \cup A_{2} \cup \cdots \cup A_{r}= \mathbb{N}

. Prove that one of them, say

A_{i}

, has the following property: There exist a positive integer

m

such that for any

k

one can find numbers

a_{1}, \cdots, a_{k}

A_{i}

0 < a_{j+1}-a_{j} \le m \; (1\le j \le k-1)

1

O 31

Prove that, for any integer

a_{1}>1

, there exist an increasing sequence of positive integers

a_{1}, a_{2}, a_{3}, \cdots

a_{1}+a_{2}+\cdots+a_{n}\; \vert \; a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2}

n \in \mathbb{N}

1

O 30

Determine the largest positive integer

n

for which there exists a set

S

n

numbers such that [*] each member in

S

is a positive integer not exceeding

2002

a,b\in S

(not necessarily different), then

ab\not\in S

1

O 29

A

N

\pmod{N^2}

. Prove that there exists a set

B

N

\pmod{N^2}

such that the set

A+B=\{a+b \vert a \in A, b \in B \}

contains at least half of all the residues

\pmod{N^2}

1

O 28

Prove that the set of positive integers cannot be partitioned into three nonempty subsets such that, for any two integers

x

y

taken from two different subsets, the number

x^{2}-xy+y^{2}

belongs to the third subset.

1

O 27

p

q

be relatively prime positive integers. A subset

S\subseteq \mathbb{N}_0

is called ideal if

0 \in S

and, for each element

n \in S

n+p

n+q

S

. Determine the number of ideal subsets of

\mathbb{N}_0

1

O 26

A set of three nonnegative integers

\{x, y, z \}

x<y<z

is called historic if

\{z-y, y-x\}=\{1776,2001\}

. Show that the set of all nonnegative integers can be written as the union of pairwise disjoint historic sets.

1

O 25

A

be a non-empty set of positive integers. Suppose that there are positive integers

b_{1}

\cdots

b_{n}

c_{1}

\cdots

c_{n}

such that [*] for each

i

b_{i}A+c_{i}=\{b_{i}a+c_{i}\vert a \in A \}

A

b_{i}A+c_{i}

b_{j}A+c_{j}

are disjoint whenever

i \neq j

\frac{1}{b_{1}}+\cdots+\frac{1}{b_{n}}\le 1.

1

O 24

Find the number of subsets of

\{1, 2, \cdots, 2000 \}

, the sum of whose elements is divisible by

5

1

O 23

k, m, n

be integers such that

1<n\le m-1 \le k

. Determine the maximum size of a subset

S

\{ 1,2, \cdots, k \}

n

distinct elements of

S

m

1

O 22

Prove that for each positive integer

n

, there exists a positive integer with the following properties: [*] it has exactly

n

digits, [*] none of the digits is 0, [*] it is divisible by the sum of its digits.

1

O 21

A sequence of integers

a_{1}, a_{2}, a_{3}, \cdots

is defined as follows:

a_{1}=1

n \ge 1

a_{n+1}

is the smallest integer greater than

a_{n}

a_{i}+a_{j} \neq 3a_{k}

i, j,

k

\{1, 2, 3, \cdots, n+1 \}

, not necessarily distinct. Determine

a_{1998}

1

O 20

Determine the smallest integer

n \ge 4

for which one can choose four different numbers

a, b, c,

d

n

distinct integers such that

a+b-c-d

is divisible by

20

1

O 19

m, n \ge 2

be positive integers, and let

a_{1}, a_{2}, \cdots,a_{n}

be integers, none of which is a multiple of

m^{n-1}

. Show that there exist integers

e_{1}, e_{2}, \cdots, e_{n}

, not all zero, with

\vert e_i \vert<m

i

e_{1}a_{1}+e_{2}a_{2}+ \cdots +e_{n}a_{n}

is a multiple of

m^n

1

O 18

p

be an odd prime number. How many

p

-element subsets

A

\{1,2,\ldots \ 2p\}

are there, the sum of whose elements is divisible by

p

1

O 17

Find the maximum number of pairwise disjoint sets of the form

S_{a,b}=\{n^{2}+an+b \; \vert \; n \in \mathbb{Z}\},

a,b \in \mathbb{Z}

1

O 16

Is it possible to find

100

positive integers not exceeding

25000

such that all pairwise sums of them are different?

1

O 15

Is it possible to choose

1983

distinct positive integers, all less than or equal to

10^{5}

, no three of which are consecutive terms of an arithmetic progression?

1

O 14

p

be a prime number,

p \ge 5

k

be a digit in the

p

-adic representation of positive integers. Find the maximal length of a non constant arithmetic progression whose terms do not contain the digit

k

p

-adic representation.

1

O 13

n

k

be given relatively prime natural numbers,

k<n.

Each number in the set

M=\{1,2,...,n-1\}

is colored either blue or white. It is given that [*] for each

i\in M,

i

n-i

have the same color, [*] for each

i\in M,i\ne k,

i

\left \vert i-k \right \vert

have the same color. Prove that all numbers in

M

have the same color.

1

O 12

m

n

be positive integers. If

x_1

x_2

\cdots

x_m

are positive integers whose arithmetic mean is less than

n+1

y_1

y_2

\cdots

y_n

are positive integers whose arithmetic mean is less than

m+1

, prove that some sum of one or more

x

's equals some sum of one or more

y

1

O 11

S=\{1,2,3,\ldots,280\}

. Find the smallest integer

n

n

-element subset of

S

contains five numbers which are pairwise relatively prime.

1

O 10

m \ge 2

be an integer. Find the smallest integer

n>m

such that for any partition of the set

\{m,m+1,\cdots,n\}

into two subsets, at least one subset contains three numbers

a, b, c

c=a^{b}

1

O 9

n

be an integer, and let

X

n+2

integers each of absolute value at most

n

. Show that there exist three distinct numbers

a, b, c \in X

c=a+b

1

O 8

a

b

be positive integers greater than

2

. Prove that there exists a positive integer

k

and a finite sequence

n_1

\cdots

n_k

of positive integers such that

n_1 =a

n_k =b

n_i n_{i+1}

is divisible by

n_{i}+n_{i+1}

i

(1 \le i \le k)

1

O 7

Show that for each

n \ge 2

, there is a set

S

n

integers such that

(a-b)^2

ab

for every distinct

a, b\in S

1

O 6

S

be a set of integers such that [*] there exist

a, b \in S

\gcd(a, b)=\gcd(a-2,b-2)=1

x,y\in S

x^2 -y\in S

S=\mathbb{Z}

1

O 5

M

be a positive integer and consider the set

S=\{n \in \mathbb{N}\; \vert \; M^{2}\le n <(M+1)^{2}\}.

Prove that the products of the form

ab

a, b \in S

1

O 4

The set of positive integers is partitioned into finitely many subsets. Show that some subset

S

has the following property: for every positive integer

n

S

contains infinitely many multiples of

n

1

O 3

Prove that the set of integers of the form

2^{k}-3

k=2,3,\cdots

) contains an infinite subset in which every two members are relatively prime.

1

O 2

p

be a prime. Find all positive integers

k

such that the set

\{1,2, \cdots, k\}

can be partitioned into

p

subsets with equal sum of elements.

1

O 1

Suppose all the pairs of a positive integers from a finite collection

A=\{a_{1}, a_{2}, \cdots \}

are added together to form a new collection

A^{*}=\{a_{i}+a_{j}\;\; \vert \; 1 \le i < j \le n \}.

A=\{ 2, 3, 4, 7 \}

A^{*}=\{ 5, 6, 7, 9, 10, 11 \}

B=\{ 1, 4, 5, 6 \}

B^{*}=\{ 5, 6, 7, 9, 10, 11 \}

. These examples show that it's possible for different collections

A

B

to generate the same collections

A^{*}

B^{*}

A^{*}=B^{*}

for different sets

A

B

|A|=|B|

|A|=|B|

must be a power of

2