Дискретная математика

[usersname]

Подскажите алгоритмы / методы решения.


1. Доказать, что для любого п найдётся п последовательных натуральных чисел, каждое из которых - составное.

2. Найти число подмножеств X множества {0,1,2,3,4,5,6,7,8,9},
обладающих следующими свойствами:

1)|Х|=3;
2) |Х| =5, 1принадлежит Х;
3)|Х|=6, 2 не принадлежитХ;
4)|Х|=7, {0,1} $\subset$ X , 2 не принадлежит Х;
5) множество X состоит из трёх чётных и двух нечётных чисел;
6) |Х| $\le$ 5.
3 На окружности последовательно отмечены точки $A_{1}$ ,.. , $A_{12}$.
Сколько существует хорд с концами в отмеченных точках;
треугольников с вершинами в отмеченных точках;
выпуклых четырёхугольников с вершинами в отмеченных точках;
треугольников с вершинами в отмеченных точках, не имеющих общих точек с прямой $A_{2}$ $A_{8}$
треугольников с вершинами в отмеченных точках, имеющих общие точки с прямой $A_{1}$ $A_{5}$



4. Найти коэффициент при $x^{100}$ в разложении многочлена
$(1+x+x^2+...+$x^{100}$ )^3$


5. Может ли а) конь; б) король; в) ладья побывать на каждой клетке шахматной доски размером 8x8 ровно один раз и последним ходом возвратиться в исходную позицию? Решить такую же задачу для доски 7x7.

Задачи не мои, просто попросили найти решения или их алгоритмы.
Ниже приведены изображения из задачника

http://localhostr.com/files/6ceef0/screen-capture-2.png
http://localhostr.com/files/458b40/screen-capture-4.png
http://localhostr.com/files/c22e0e/screen-capture-3.png
http://localhostr.com/files/2d59b8/screen-capture-5.png

[ozhigin]

287! наверняка проходили Бином Ньютона, а эта формула комбинаторная! попробуйте начать раскладывать по ней!

[PAV]

Тема перемещена из "Помогите решить/разобраться" в карантин. Почему это произошло, можно понять, прочитав тему
Что такое карантин и что нужно делать, чтобы там оказаться
Там же описано, как исправлять ситуацию.

(картинки в качестве замен формул не допускаются, условия задач должны быть набраны текстом, формулы - оформлены согласно правилам форума; приведите свои попытки решения и конкретные затруднения)

-- Пн окт 19, 2009 21:51:51 --

Возвращено

[usersname]

Помогите решить 1е и 4е остальные решены
4е кстати решается разложением на 3 скобки тк 3я степень, а не биномом ньютона

[RIP]

1. Ищите нужные числа в виде $m+2$, $m+3$, $m+4$, ... Сами догадайтесь, какую $m$ взять. Второй сособ --- китайская теорема об остатках.

4. Как ни странно, задача на бином Ньютона. Надо рассмотреть ряд $(1+x+x^2+\ldots)^3$ и подумать: какая связь между коэффициентами при $x^{100}$ у него и многочлена из условия.

[usersname]

RIP в сообщении #253880 писал(а):

1. Ищите нужные числа в виде $m+2$, $m+3$, $m+4$, ... Сами догадайтесь, какую $m$ взять. Второй сособ --- китайская теорема об остатках.

не получается
вот например
список соответствий n и m

(1 ; 4)
(2 ; 8)
(3 ; 8)
(4 ; 24)
(5 ; 24)
(6 ; 90)
(7 ; 90)
(8 ; 114)
(9 ; 114)
(10 ; 114)
(11 ; 114)
(12 ; 114)
(13 ; 114)
(14 ; 524)
(15 ; 524)
(16 ; 524)
(17 ; 524)
(18 ; 888)
(19 ; 888)
(20 ; 1130)
(21 ; 1130)
(22 ; 1328)
(23 ; 1328)
(24 ; 1328)
(25 ; 1328)
(26 ; 1328)
(27 ; 1328)
(28 ; 1328)
(29 ; 1328)
(30 ; 1328)
(31 ; 1328)
(32 ; 1328)
(33 ; 1328)
(34 ; 9552)
(35 ; 9552)
(36 ; 15684)
(37 ; 15684)
(38 ; 15684)
(39 ; 15684)
(40 ; 15684)
(41 ; 15684)
(42 ; 15684)
(43 ; 15684)
(44 ; 19610)
(45 ; 19610)
(46 ; 19610)
(47 ; 19610)
(48 ; 19610)
(49 ; 19610)
(50 ; 19610)
(51 ; 19610)
(52 ; 31398)
(53 ; 31398)
(54 ; 31398)
(55 ; 31398)
(56 ; 31398)
(57 ; 31398)
(58 ; 31398)
(59 ; 31398)
(60 ; 31398)
(61 ; 31398)
(62 ; 31398)
(63 ; 31398)
(64 ; 31398)
(65 ; 31398)
(66 ; 31398)
(67 ; 31398)
(68 ; 31398)
(69 ; 31398)
(70 ; 31398)
(71 ; 31398)
(72 ; 155922)
(73 ; 155922)
(74 ; 155922)
(75 ; 155922)
(76 ; 155922)
(77 ; 155922)
(78 ; 155922)
(79 ; 155922)
(80 ; 155922)
(81 ; 155922)
(82 ; 155922)
(83 ; 155922)
(84 ; 155922)
(85 ; 155922)
(86 ; 360654)
(87 ; 360654)
(88 ; 360654)
(89 ; 360654)
(90 ; 360654)
(91 ; 360654)
(92 ; 360654)
(93 ; 360654)
(94 ; 360654)
(95 ; 360654)
(96 ; 370262)
(97 ; 370262)
(98 ; 370262)
(99 ; 370262)
(100 ; 370262)

Цитата:

4. Как ни странно, задача на бином Ньютона. Надо рассмотреть ряд $(1+x+x^2+\ldots)^3$ и подумать: какая связь между коэффициентами при $x^{100}$ у него и многочлена из условия.

гм, симметрично

[ИСН]

Короче, RIP сложно говорит. В первой, считаю, можно дать совет (до него не там просто догадаться, after all; человеку угодно лишить себя этого удовольствия - be my guest): подумате про $n!$.
Во второй - вычислить первые 3-4 коэффициента, угадать общую формулу, доказать, применить.

[usersname]

ИСН в сообщении #253915 писал(а):

Короче, RIP сложно говорит. В первой, считаю, можно дать совет (до него не там просто догадаться, after all; человеку угодно лишить себя этого удовольствия - be my guest): подумате про $n!$.
Во второй - вычислить первые 3-4 коэффициента, угадать общую формулу, доказать, применить.

уже неделю думаем -__-

Цитата:

(до него не там просто догадаться, after all; человеку угодно лишить себя этого удовольствия - be my guest)[

проблемы со сном уже как неделю, смысл не улавливаю

[jetyb]

К четверттой задаче:
Нарисуйте 100 кружочков. Сколькими способами мы можем расставить с краю от них или между ними 2 палочки(они могут стоять и на одном месте)? Какое вообще отношение имеет эта задача к рассматриваемой?

[Maslov]

jetyb в сообщении #253930 писал(а):

Нарисуйте 100 кружочков.

Имеется в виду, 100 кружочков в одну линию

[usersname]

jetyb в сообщении #253930 писал(а):

К четверттой задаче:
Нарисуйте 100 кружочков. Сколькими способами мы можем расставить с краю от них или между ними 2 палочки(они могут стоять и на одном месте)? Какое вообще отношение имеет эта задача к рассматриваемой?

10100 ?

[ИСН]

Начните с малого. 100 - это очень много. Пусть будет 2.

[usersname]

ни одним из предложенных методов решения не осилил.
вот появились например такие методы

1) перефраз. доказать что для любого n любая последовательность натуральных чисел не содержит простых.
n=3 3,4,5

4) посчитать кол-во целочисленных решений через s, n, и r но ф-лу для s нигде найти не могу. получается чтото типа сочетаний без повторений с учетом s
или
$(1-x^{101})^3 \cdot (1-x)^{-3}$ и разложить по биному

[ИСН]

Зашибись. До сих пор я Вас понимал, а тут перестал.

[RIP]

usersname в сообщении #254251 писал(а):

1) перефраз. доказать что для любого n любая последовательность натуральных чисел не содержит простых.
n=3 3,4,5

Вашу переформулировку нифига не понял. К тому же Вам уже давно ответ написали: докажите, что все числа $(n+1)!+2,(n+1)!+3,(n+1)!+4,\ldots,(n+1)!+(n+1)$ составные.