Комбинаторика

[Turtur]

Всем привет, не могу понять с чего начать решение такой задачи:

Цитата:

Имеется 11 точек на прямой, между каждыми двумя расстояние 1. Сколькими способами можно выбрать из них 4 такие точки, чтобы любые две из них лежали между собой на расстоянии 2 и больше?

Есть мыслишка предположить, что одной из точек будет первая точка (1), другой точкой - соотвественно третья по счету (2), ещё одной - соотвественно пятая по счету точка прямой (3). Тогда для четвертой, последней нужной точки, мы можем посчитать количество возможных положений. Теперь оставляем предположение, лишь заменяя (3) условие на (3') таким образом, что (3') будет утверждать, что третья нужная нам точка будет являться шестой на исходной прямой. Аналогично продолжать сдвигать точки из условий (1)-(3) слишком долго, муторно, да и вообще не рационально, а как иначе - вообще никак не могу догадаться.
Подайте идею, как можно решение такой банальной задачи свести к известным формулам комбинаторики - сочетания/размещения и тд. Большое спасибо!

[grizzly]

А Вы не находите, что это:

Turtur в сообщении #1077058 писал(а):

между каждыми двумя расстояние 1

противоречит этому:

Turtur в сообщении #1077058 писал(а):

чтобы любые две из них лежали между собой на расстоянии 2 и больше

?

[Turtur]

grizzly

Извиняюсь за примитив.
Дано: 11 точек. Да, между каждыми двумя следующими друг за другом расстояние 1.
Извините за колесницу, Вы правы. Надеюсь, сейчас условие полностью корректно? Для наглядности косорукий рисунок.

[Anton_Peplov]

(Оффтоп)

Хорошо, что условие исправили. А то мне было страшно представить 11 точек, лежащих на одной прямой и при этом равноудаленных друг от друга.

[grizzly]

(Оффтоп)

Anton_Peplov в сообщении #1077085 писал(а):

А то мне было страшно представить 11 точек, лежащих на одной прямой и при этом равноудаленных друг от друга.

А что ж тут страшного? Обычная дискретная метрика. Просто ответ в этом случае слишком простой.

[Anton_Peplov]

(Оффтоп)

Страшного то, что ТС явно имел в виду каноническое $\mathbb{R}^2$

[provincialka]

По-другому условие можно сформулировать так: нельзя выбирать соседние точки.
А вы возьмите, и справа от каждой выбранной пометьте одну точку крестиком. Кроме самой правой, конечно: там не нужно. Сколько будет непомеченных точек и сколько из них надо выбрать?

[grizzly]

Turtur в сообщении #1077058 писал(а):

Аналогично продолжать сдвигать точки из условий (1)-(3) слишком долго, муторно, да и вообще не рационально, а как иначе - вообще никак не могу догадаться.

Всё-таки в любом случае советую посчитать варианты вручную (даже в уме это займёт пару-тройку минут, не больше). Это очень даже рационально, если задача не идёт. При подсчёте Вы очень скоро обнаружите, что ничего нового считать не приходится, а только суммировать те же варианты, которые уже считали раньше. Так и закономерность несложно найти.

Это общая рекомендация -- попытаться покрутить непонятную задачу руками. Иногда ради этого можно / нужно упростить условие -- взять меньшие числа, например (но не в этом случае).

[provincialka]

Я в таких задачах мысленно "склеиваю" взятую точку с соседней, невзятой.

[Turtur]

provincialka
Чего-то не особо проясняется опираться на идею, которую Вы предложили. Для меня ничего не прояснилось.
grizzly
Да я считала уже. Муторно. Получилось 70 возможных размещений. Могу расписать, конечно, но, наверное, не особо надо.
Очень хотелось бы решить красиво, как принято в подобных задачах ч/з несколько (а здесь, может, и вообще одну) формул размещений/сочетаний. Идея

Цитата:

в таких задачах мысленно "склеиваю" взятую точку с соседней, невзятой

хорошая, скорее всего, и есть первый шаг решения, но до меня все равно никак не доходит.
Пожалуйста, если кто-то из Вас уже догадался (скорее всего уж так и есть) как решить просто и красиво - "одним росчерком пера", скажите, или натолкните ещё как-то.

-- 27.11.2015, 14:44 --

В итоге так получается:
$ (5+...+1)+(4+...+1)+(3+...+1)+(2+...+1)+(1)+ +(4+...+1)+(3+...+1)+(2+...+1)+(1)+ +(3+...+1)+(2+...+1)+(1)+ +(2+...+1)+(1)+ +(1). $
Может быть, как-то нужно взять кол-во сочетаний из 6? Ну, кол-во пар из 11 исходных точек - 6. Возвращаясь к идее provincialka.
К слову, это должно как-то напоминать треугольник Паскаля и натолкнуть на кол-во сочетаний, но лично меня - нет, может Вас?))

Для красоты и ляпоты:

[provincialka]

Может, вам поможет тот факт, что $70=C_8^4$?

[grizzly]

Turtur в сообщении #1077292 писал(а):

Да я считала уже. Муторно. Получилось 70 возможных размещений. Могу расписать, конечно, но, наверное, не особо надо.

Расписывать не нужно, всё верно. Я направил Вас не по лучшему пути (потому, что заметить, как свернуть такое решение одной формулой сложно).

Turtur в сообщении #1077292 писал(а):

Возвращаясь к идее provincialka.

Давайте упростим пример. Пусть это будет не 4 точки из 11, а 2 из 5. Таких вариантов, чтоб между ними была хотя бы 1 точка, будет 6. А теперь в каждом из этих 6 вариантов сделайте левую точку настолько жирной, чтобы она накрыла ближайшую справа. И посмотрите, что получилось в итоге -- у Вас выбрано 2 точки из 4, но уже без требования, чтобы между ними была точка. А 6 это и есть $C_4^2$. Вот об этом говорила provincialka.

Теперь попробуйте применить это рассуждение к Вашей задаче.

[provincialka]

Давайте пометим выбранные точки галочками. Рядом с каждой галочкой справа не может стоять галочка. Поэтому соседнюю точку можно пометить, скажем, крестиком, и рассматривать пару "галочка+крестик" в тандеме. Правда, после самой правой галочки крестик не нужен. Но мы его добавим.
Вопрос: сколько у нас будет модифицированных точек (с учетом сдваивания)?

О! Уже написали, и даже лучше, чем я...

[Turtur]

grizzly, provincialka, большущее Вам спасибо!

(Оффтоп)

Цитата:

сделайте левую точку настолько жирной, чтобы она накрыла ближайшую справа

очень эффектно звучит, правда. Изящное объяснение получилось :) А вообще термин "модифицированная точка" нужно брать на заметку и пользоваться методом "склеивания", который предложила provincialka.