Национална олимпиада по математика — национален кръг | Библиотека

Задача 2

Пълен запис

Условие

За всяко естествено число

n

сумата

1+\frac{1}{2}+\cdots+\frac{1}{n}

е представена като несъкратима дроб

\frac{p_{n}}{q_{n}}

. a) Да се докаже, че 3 не дели

p_{67}

. б) Да се намерят всички

n

, за които 3 дели

p_{n}

.

Решение

а) Нека

S_{n}=1+\frac{1}{2}+\cdots+\frac{1}{n}

. Имаме, че

S_{2}=3 \cdot \frac{1}{2}, S_{7}=3 \cdot \frac{121}{140}

,

\begin{gathered} S_{22}-S_{7}=\frac{1}{8}+\frac{1}{22}+\frac{1}{10}+\frac{1}{20}+\frac{1}{11}+\frac{1}{19}+\frac{1}{14}+\frac{1}{16}+\frac{1}{13}+\frac{1}{17}+ \\ \frac{1}{9}+\frac{1}{12}+\frac{1}{15}+\frac{1}{18}+\frac{1}{21}=30 \cdot \frac{a}{b}+\frac{51}{140}=3 \cdot \frac{c}{d} \end{gathered}

където

(a, b)=(c, d)=1

. Лесно се съобразява, че

a

и

b

дават един и същ ненулев остатък при деление на 3. Следователно

c

и

d

дават различни ненулеви остатъци при деление на

3, p_{22}=3 p_{22}^{\prime}

и 3 не дели

p_{22}^{\prime}

. По подобен начин получаваме

S_{67}-S_{22}=90 \frac{e}{f}+\frac{c}{d}

, където 3 не дели

f

. Това показва, че 3 не дели

p_{67}

и

q_{67}

. б) Нека

S_{n}=\frac{k_{n}}{3^{m_{n}} l_{n}}

, където 3 не дели

k_{n}

и

l_{n}

. Тогава

\begin{gathered} S_{3 n}=\frac{S_{n}}{3}+1+\frac{1}{2}+\frac{1}{4}+\frac{1}{5}+\cdots++\frac{1}{3 n-2}+\frac{1}{3 n-1}= \\ \frac{k_{n}}{3^{m_{n}+1} l_{n}}+3 \cdot \frac{a_{n}}{b_{n}}=\frac{k_{n} b_{n}+3^{m_{n}+2} l_{n} a_{n}}{3^{m_{n}+1} l_{n} b_{n}} \end{gathered}

където

b_{n}

не се дели на 3. Следователно, ако

m_{n} \geq-1

, то

m_{3 n}=m_{n}+1

. По подобен начин се вижда, че

m_{3 n+2}=m_{n}+1

при

m_{n} \geq-1

и

m_{3 n+1}=m_{n}+1

при

m_{n} \geq 0

. Понеже

m_{1}=0, m_{2}=m_{7}=m_{22}=-1, m_{67}=0

, лесно следва, че отговорът на задачата е

n=2, 7, 22

.

Отвори задачатаБаза на maths.bgolinat2004-9-2

Задача 3

Пълен запис

Условие

Туристическа група се състои от

n

човека. Измежду всеки трима има двама, които не се познават. Известно е, че групата не може да бъде разпределена в два автобуса така, че всеки да пътува само с непознати. Да се докаже, че в групата има турист с не повече от

\frac{2}{5} n

познати.

Решение

Да разгледаме граф

G

с

n

върха, на върховете на който съответстват членовете на групата и два върха са свързани само когато съответните членове се познават. Условието измежду всеки трима има двама, които не се познават означава, че в

G

няма триъгълник. Ще покажем, че условието известно е, че групата не може да бъде разпределена в два автобуса така, че всеки да пбтува само с непознати означава, че в графа има цикъл с нечетна дължина. Действително, ако всички цикли са с четна дължина, лесно се доказва, че върховете могат да бъдат разпределени в две групи, така, че във всяка група да няма ребра. Да изберем нечетен цикъл с най-малка дължина -

A_{1}, A_{2}, \ldots, A_{k}

. Поради това, че

G

не съдържа триъгълник и поради факта, че избрания цикъл е с минимална дължина, всеки връх извън цикъла е свързан с най-много два върха от него. Следователно броят на ребрата от вида

\left(X, A_{i}\right), X \neq A_{j}

,

j=1, 2, \ldots, k

е не по-голям от

2(n-k)

. Да означим минималната степен на връх с

\delta

. Очевидно

\sum_{i=1}^{k} d\left(A_{i}\right)=\left|E^{*}\right|+2 k

, където

E^{*}

е множеството на ребрата от вида

X A_{i}

. Имаме

2(n-k) \geq\left|E^{*}\right|=\sum_{i=1}^{k} d\left(A_{i}\right)-2 k \geq k \delta-2 k

Оттук

\delta \leq \frac{2 n}{k}

. Тъй като

k \geq 5

, то

\delta \leq \frac{2 n}{5}

.

Отвори задачатаБаза на maths.bgolinat2004-9-3

Задача 4

Пълен запис

Условие

Във всяка дума, съставена от буквите

a

и

b

, можем да извършваме следните замени:

a b a \rightarrow b, b \rightarrow a b a, b b a \rightarrow a, a \rightarrow b b a

. Възможно ли е от думата

b \underbrace{a a \ldots a}_{2003}

да се получи думата

\underbrace{a a \ldots a}_{2003} b

?

Решение

Ще докажем, че при прилагане на коя да е от разрешените замени броят на буквите

a

на четни (съответно нечетни) позиции запазва четността си. Действително, да разгледаме замяната

a b a \rightarrow b

, приложена към думата

w_{1} a b a w_{2}

. В новополучената дума

w_{1} b w_{2}

всички букви

a

от

w_{1}

са останали на местата си, а всички букви

a

от

w_{2}

са се преместили с две позиции на ляво и следователно са запазили четността на позицията си. Изтриването на двете букви

a

от

a b a

е намалило броя на буквите

a

на четни или нечетни позиции с две. Аналогично, при прилагане на

b b a \rightarrow a

към

w_{1} b b a w_{2}

получаваме

w_{1} a w_{2}

и лесно се вижда, че свойството е изпълнено. Тъй като

a \rightarrow a b a

и

a \rightarrow b b a

са обратни на разгледаните, то за тях е в сила същото свойство. Да забележим, че в думата

b \underbrace{a a \ldots a}_{2003}

броят на буквите

a

на четни позиции е 1002, докато броят на буквите

a

на четни позиции в думата

\underbrace{a a \ldots a}_{2003} b

е 1001. Следователно от първата дума не може да се получи втората.

Отвори задачатаБаза на maths.bgolinat2004-9-4

Задача 5

Пълен запис

Условие

Нека

a, b, c

и

d

са естествени числа такива, че броят на наредените двойки от числа

(x, y), x, y \in(0, 1)

, за които

a x+b y

и

c x+d y

са едновременно цели числа, е 2004. Ако НОД

(a, c)=6

, да се намери НОД(

b, d

).

Решение

Да предположим първо, че

a d \neq b c

. Множеството от точки с координати

(a x+b y, c x+d y), x, y \in(0, 1)

, е вътрешността на успоредника с върхове

A=(0, 0), B=(a, c), C=(b, d)

и

D=(a+b, c+d)

. Неговото лице

S

е равно на

|a d-b c|

. От друга страна, съгласно формулата на Пик, имаме

S= n+\frac{m}{2}-1

, където

n

(съответно

m

) е броят на точките с цели координати във вътрешността (съответно по контура) на успоредника. Нека

e=

НОД

(a, c)

,

f=

НОД

(b, d) a=e a_{1}, c=e c_{1}, b=f b_{1}

и

d=f d_{1}

. Вътрешните точки от страната

A B

имат координати

(a x, c x), x \in(0, 1)

. Следователно броят на тези с цели координати е равен на

e-1

. Аналогично броят на вътрешните точки с цели координати от страните

B D, C D

и

A C

е равен съответно на

f-1, e-1

и

f-1

. Следователно

\frac{m}{2}=e+f

и тогава условието приема вида

e f\left|a_{1} d_{1}-b_{1} c_{1}\right|=2003+e+f \tag{1}

Тъй като

e=

НОД

(a, c)=6

следва, че

f

дели

2009=7^{2}.41

и

6 f

дели

2009+f

. Това е възможно само при

f=1, 7, 49

. За всяка от тези стойности на

f

числата

e=6, a_{1}=1+\frac{2009+f}{6 f}, b_{1}=c_{1}=d_{1}=1

изпълняват (1) и следователно НОД

(b, d)=1, 7

или 49. Нека сега

a d=b c

. Тогава лесно се вижда, че

a_{1}=b_{1}

и

c_{1}=d_{1}

. За всяко

x \in\left(0, \frac{1}{e}\right)

полагаме

y=\frac{1-x e}{f}\lt{}\frac{1}{f}

. Тогава

e x+f y=1

и

a x+b y=a_{1}

и

c x+d y=c_{1}

са цели числа. Следователно в този случай съществуват безбройно много двойки

(x, y)

с исканото свойство, което противоречи на условието.

Отвори задачатаБаза на maths.bgolinat2004-9-5

Задача 6

Пълен запис

Условие

Нека

p

е просто число. За произволни цели числа

0 \leq a_{1}\lt{} a_{2} \cdots\lt{}a_{m}\lt{}p

и

0 \leq b_{1}\lt{}b_{2} \cdots\lt{}b_{n}\lt{}p

да означим с

k

броят на различните остатъци при деление на

p

на числата

a_{i}+b_{j}, 1 \leq i \leq m, 1 \leq j \leq n

. Да се докаже, че: а) ако

m+n\gt{}p

, то

k=p

; б) ако

m+n \leq p

, то

k \geq m+n-1

.

Решение

а) Нека

t

е произволен остатък при деление на

p

, т. е.

t \in\{0, 1, 2, \ldots, p-1\}

. Да разгледаме остатъците при деление на

p

на числата

t-a_{i}, 1 \leq i \leq m

и

b_{j}, 1 \leq j \leq n

. Това са

m+n\gt{}p

на брой числа, всяко от които може да приема

p

възможни стойности

0, 1, \ldots, p-1

. Следователно измежду тях има две равни. Тъй като при

i \neq j

числата

t-a_{i}

и

t-a_{j}

(съответно

b_{i}

и

b_{j}

), дават различни остатъци при деление на

p

, то съществуват

r

и

s

, за които

t-a_{r}

и

b_{s}

дават еднакви остатъци, т. е.

a_{r}+b_{s}

при деление на

p

дава остатък

t

. Тъй като

t

е произволен остатък, то

k=p

. б) Нека

m+n \leq p

и да означим

A=\left\{a_{1}, a_{2}, \ldots, a_{m}\right\}, B=\left\{b_{1}, b_{2}, \ldots, b_{n}\right\}

. За всеки две множества

X

и

Y

нека

X+Y=\{x+y(\bmod p) \mid x \in X, y \in Y\}

. Искаме да покажем, че

k=|A+B| \geq m+n-1

. Без ограничение можем да предполагаме, че

m \leq n

. Ще докажем твърдението с индукция по

m

.

(*)

При

m=1

и за произволно

n

имаме

|A+B|=\left|a_{1}+B\right|

. Тъй като при

i \neq j

имаме

a_{1}+b_{i} \neq a_{1}+b_{j}(\bmod p)

, то

\left|a_{1}+B\right|=|B|=n=m+1-1

, т. е. твърдението е вярно при

m=1

.

(*)

Да допуснем, че твърдението е вярно за всеки две множества

X

и

Y

, за които

|X|\lt{}m, |X|\lt{}|Y|

и

|X|+|Y| \leq p

.

Отвори задачатаБаза на maths.bgolinat2004-9-6