Сколько чисел нужно вычеркнуть?

[vivaldi]

Какое наименьшее количество чисел нужно вычеркнуть из совокупности чисел 1, 2, 3, ..., 2011 так, чтобы ни одно из оставшихся чисел не равнялось произведению двух других из оставшихся чисел? Каким образом это можно сделать?

[age]

По-моему, $45$. Убираем первые 45 чисел. Проверяем число $2000=2\cdot1000=4\cdot500=5\cdot400=8\cdot250=10\cdot200=16\cdot125=$$20\cdot100=25\cdot80=40\cdot50$. Т.к. с $1$ до $45$ мы всё исключили, то не найдётся никаких двух чисел, произведение которых будет $2000$. Аналогично с остальными.

[vivaldi]

age в сообщении #501144 писал(а):

По-моему, $45$.

Почти

-- 08.11.2011, 15:22 --

age в сообщении #501144 писал(а):

Убираем первые 45 чисел.

Можно убрать меньше.

[Хорхе]

Понятно, что можно вычеркнуть только 44 первых, пока непонятно, можно ли меньше.

У меня было 43, но я обсчитался.

[age]

Хорхе в сообщении #501155 писал(а):

Например, вычеркнуть еще 1763 и вчеркнуть обратно 41 и 43.

Кстати.

[Хорхе]

age в сообщении #501156 писал(а):

Хорхе в сообщении #501155 писал(а):

Например, вычеркнуть еще 1763 и вчеркнуть обратно 41 и 43.

Кстати.

Нет, это не катит.

[age]

Хорхе в сообщении #501157 писал(а):

Нет, это не катит.

Тогда 44, меньше нельзя.

[vivaldi]

age в сообщении #501163 писал(а):

Хорхе в сообщении #501157 писал(а):

Нет, это не катит.

Тогда 44, меньше нельзя.

Можно

[venco]

43.
1 ведь можно оставить.

[Хорхе]

Ага, там есть слово "других". А почему меньше-то нельзя?

[vivaldi]

Хорхе в сообщении #501191 писал(а):

Ага, там есть слово "других". А почему меньше-то нельзя?

Подсказать или сами попытаетесь?
Для такого кита как Вы такая школьная задача - пара пустяков.

[Хорхе]

Мерси пур комплеман, бат ай донт сфинк ай дезёрв. Нее, подсказывать не надо. Оно-то вроде и понятно, только строго как-то не придумывается.

-- Вт ноя 08, 2011 20:27:35 --

А, ну понятно. Давайте единичку тоже запретим, чтобы не делать все время оговорки. Пусть мы вычеркнули не более 44 чисел. Тогда, во-первых, чисел среди оставшихся совсем маленьких (например, меньше десяти) быть не может. Далее, если есть $n$ чисел, не превышающих 45, скажем, $x_1<x_2<\dots<x_n$, то нету как минимум $n-1$-го числа $x_1 x_2, x_1x_3,\dots, x_1 x_n$, больших 45. Ну вот вроде и все.

[vivaldi]

Хорхе в сообщении #501232 писал(а):

Мерси пур комплеман, бат ай донт сфинк ай дезёрв.

(Оффтоп)

А с Ксюшей Вы по-нашенски общались...хотя она-то как раз и полиглот.

-- 08.11.2011, 19:06 --

Хорхе в сообщении #501232 писал(а):

А, ну понятно. Давайте единичку тоже запретим, чтобы не делать все время оговорки. Пусть мы вычеркнули не более 44 чисел. Тогда, во-первых, чисел среди оставшихся совсем маленьких (например, меньше десяти) быть не может. Далее, если есть $n$ чисел, не превышающих 45, скажем, $x_1<x_2<\dots<x_n$, то нету как минимум $n-1$-го числа $x_1 x_2, x_1x_3,\dots, x_1 x_n$, больших 45. Ну вот вроде и все.

Так правильный ответ же 43

Ах, сорри, вроде верно.
Идея в том, чтобы создать 43 непересекающиеся тройки и показать, что в каждой из них хотя бы одно число должно быть стерто.
Например, такие тройки:
(44, 45, 44*45), (43, 46, 43*46), ..., (2, 87, 2*87).

[Хорхе]

Ну так я же запретил единицу (в смысле, она вычеркнута)! Так что 43 и есть. Вы вчитайтесь :)

[vivaldi]

Хорхе в сообщении #501307 писал(а):

Ну так я же запретил единицу (в смысле, она вычеркнута)! Так что 43 и есть. Вы вчитайтесь :)

Так Вы тоже вчитайтесь и тогда поймете, что и я уже вчитался:

vivaldi в сообщении #501270 писал(а):

Ах, сорри, вроде верно.
Идея в том, чтобы создать 43 непересекающиеся тройки и показать, что в каждой из них хотя бы одно число должно быть стерто.
Например, такие тройки:
(44, 45, 44*45), (43, 46, 43*46), ..., (2, 87, 2*87).