Интересные олимпиадные задачи

bot · Сообщение **bot** » 20 июн 2007, 20:10

Угу, хотя и проще можно. Плюсик будет завтра.
Гляньте вот эту, a то она уж на вторую страницу ушла.
[url=http://e-science.ru/forum/index.php?showtopic=2958]http://e-science.ru/forum/index.php?showtopic=2958[/url]

A ещё
задачка. Доказать, что в любой компании из 6 человек найдутся либо трое попарно знакомых, либо трое попарно незнакомых.

alexpro · Сообщение **alexpro** » 20 июн 2007, 20:16

bot писал(а):Source of the post
Угу, хотя и проще можно.

A его можно узнать?

andrej163 · Сообщение **andrej163** » 20 июн 2007, 20:41

bot писал(а):Source of the post
A ещё
задачка. Доказать, что в любой компании из 6 человек найдутся либо трое попарно знакомых, либо трое попарно незнакомых.

У одного человека среди остальных пяти есть либо не менее трех незнакомых, либо не менее трех знакомых ему. посмотрим на второе. Среди этих трех людей есть либо двое знакомых – тогда они вместе c выбранным человеком образуют нужную тройку, либо они все трое попарно незнакомы.

alexpro · Сообщение **alexpro** » 20 июн 2007, 21:11

andrej163 писал(а):Source of the post
bot писал(а):Source of the post
A ещё
задачка. Доказать, что в любой компании из 6 человек найдутся либо трое попарно знакомых, либо трое попарно незнакомых.

У одного человека среди остальных пяти есть либо не менее трех незнакомых, либо не менее трех знакомых ему. посмотрим на второе. Среди этих трех людей есть либо двое знакомых – тогда они вместе c выбранным человеком образуют нужную тройку, либо они все трое попарно незнакомы.

a если имеет место первое, то, либо в той тройке все знакомы (и это будет искомая тройка), либо хотя бы двое не знакомы. A тогда в последнем случае они c выбранным человеком будут давать искомую тройку.

andrej163 · Сообщение **andrej163** » 20 июн 2007, 21:16

alexpro писал(а):Source of the post
andrej163 писал(а):Source of the post
bot писал(а):Source of the post
A ещё
задачка. Доказать, что в любой компании из 6 человек найдутся либо трое попарно знакомых, либо трое попарно незнакомых.

У одного человека среди остальных пяти есть либо не менее трех незнакомых, либо не менее трех знакомых ему. посмотрим на второе. Среди этих трех людей есть либо двое знакомых – тогда они вместе c выбранным человеком образуют нужную тройку, либо они все трое попарно незнакомы.

a если имеет место первое, то, либо в той тройке все знакомы (и это будет искомая тройка), либо хотя бы двое не знакомы. A тогда в последнем случае они c выбранным человеком будут давать искомую тройку.

Ну это само-сабой выплывает!

alexpro · Сообщение **alexpro** » 20 июн 2007, 21:25

andrej163 писал(а):Source of the post
Ну это само-сабой выплывает!

Ну раз выплывает, то я не возражаю, пусть плавает.

Довольно интересная задачка:

Пусть $\alpha$ - иррациональное число. Тогда множество чисел вида $m\cdot\alpha+n$ , где $$m, n$$

- целые числа, будет всюду плотным множеством в $\mathbb{R}$ (во множестве действительных чисел) (множество $$X$$

всюду плотно во множестве $\mathbb{R}$ , если для сколь угодно малого интервала найдутся элементы из множества $$X$$

, принадлежащие данному интервалу).

AV_77 · Сообщение **AV_77** » 20 июн 2007, 23:43

alexpro писал(а):Source of the post
Довольно интересная задачка:

Пусть $\alpha$ - иррациональное число. Тогда множество чисел вида $m\cdot\alpha+n$ , где - целые числа, будет всюду плотным множеством в $\mathbb{R}$ (во множестве действительных чисел) (множество всюду плотно во множестве $\mathbb{R}$ , если для сколь угодно малого интервала найдутся элементы из множества , принадлежащие данному интервалу).

He так трудно показать, что эта задача эквивалентна следующей. Пусть $$ 0 < x < 1 $$

- иррациональное число. Тогда множество чисел $$ |nx - [nx]| $$

всюду плотно в интервале $$ (0, 1) $$

. Здесь

- ближайшее целое к $$ a $$

число.

Можно, конечно, рассмотреть группу $\mathbb{R}/\mathbb{Z}$ , но мы поступим проще.

Рассмотрим множество $S = \left\{|nx - [nx]| \right\}$ . Пусть $$ y $$

- некоторый его элемент. Покажем сначала, что существует $z \in S$ такой, что $z \le \frac{y}{2}$ . B самом деле, пусть $$ (n-1) y < m <ny $$

, где

- некоторое целое число. Рассмотрим числа $$ z_1 = m - (n-1) y $$

и

. очевидно, что $\min \left{z_1,\ z_2 \right} \le \frac{y}{2}$ . B частности, отсюда следует, что для любого натурального числа $$ m $$

в множестве $$ S $$

существует элемент $$ y $$

, меньший $\frac{1}{m}$ .

Пусть теперь $0 \le a < b \le 1$ - произвольные числа. Тогда $a < \frac{p}{c} < \frac{q}{c} < b$ для некоторых целых $p,\ q,\ c$ . Пусть $y \in S$ таково, что $y < \frac{1}{c}$ . Тогда существует такое натуральное число $$ k $$

, что $\frac{p}{c} < ky < \frac{q}{c}$ . Этим наше утверждение доказано.

Angerran · Сообщение **Angerran** » 21 июн 2007, 02:25

Предложу такую задачку:
Ha доске можно либо написать две единицы, либо стереть любые два из уже написанных одинаковых чисел N и написать вместо них числа N+1 и N-1. Какое минимальное кол-во таких операций требуется, чтобы получить число 2005 ? Сначала доска была чистой.
Скажу сразу что на эту задачу решения у меня нет.

alexpro · Сообщение **alexpro** » 21 июн 2007, 11:59

AV_77 писал(а):Source of the post
He так трудно показать, что эта задача эквивалентна следующей. Пусть - иррациональное число. Тогда множество чисел всюду плотно в интервале . Здесь - ближайшее целое к число.

Можно, конечно, рассмотреть группу $\mathbb{R}/\mathbb{Z}$ , но мы поступим проще.

Рассмотрим множество $S = \left\{|nx - [nx]| \right\}$ . Пусть - некоторый его элемент. Покажем сначала, что существует $z \in S$ такой, что $z \le \frac{y}{2}$ . B самом деле, пусть , где - некоторое целое число. Рассмотрим числа и . очевидно, что $\min \left{z_1,\ z_2 \right} \le \frac{y}{2}$ . B частности, отсюда следует, что для любого натурального числа в множестве существует элемент , меньший $\frac{1}{m}$ .

Пусть теперь $0 \le a < b \le 1$ - произвольные числа. Тогда $a < \frac{p}{c} < \frac{q}{c} < b$ для некоторых целых $p,\ q,\ c$ . Пусть $y \in S$ таково, что $y < \frac{1}{c}$ . Тогда существует такое натуральное число , что $\frac{p}{c} < ky < \frac{q}{c}$ . Этим наше утверждение доказано.

Немного путанный текст. Нельзя ли понятнее. Скажу сразу, есть простое решение.

bot · Сообщение **bot** » 21 июн 2007, 12:24

alexpro писал(а):Source of the post
A его можно узнать?

Угу, можно. Чтобы не бегать далеко за условием приведу его снова, слегка переформулировав.
Для иррационального $$a$$

требуется найти такие иррациональные $$b$$

и

, чтобы
(1) $$p=a+b$$

и

были рациональны,
(2) $\alpha=a+c$ и $\beta=ab$ были иррациональны.
Задачу встретил вчера на одном форуме и дал там это решение:

Берём рациональные $$p$$

и $q\ne 0$ наугад и из (1) вычисляем $$b=p-a$$

и $c=\frac{q}{a}$ - они иррациональны.
Если при этом (2) выполнилось, то есть $\alpha=a+\frac{q}{a}$ и $\beta=ap-a^2$ иррациональны, то всё OK. Если же в каком-то обломались, то достаточно сменить рациональные $$p$$

и/или

на любые другие - это очевидно изменит $\alpha$ и/или $\beta$ на иррациональное слагаемое.

yourdomain.com