Задача 10

[Мирослав Стоенчев]

Задача 10. (Панчев) По колко начина могат да се разположат числата от 1 до 2n в таблица от 2 редa и n стълба така, че във всеки ред числата отляво надясно да нарастват и всяко число от по-долния ред да е по-малко от числото над него?

[Реклама]

[pin01]

Мисля, че начина е само един и той е аритметична прогресия с аk1+d, d=2, като ak1=а1+а2=а1+а1+1=2a1+1, а e а1 първи член от долния ред=> a2 е от горния.
=>аkn=2a2n-1, а за 2n незнам какво значение има, след като винаги имаме начло ak1 и d=2 =>само един начин и той е аритметична прогресия с първи член аk1 и d=2 и последен член akn.
За геометрична прогресия не става май.
Т.е. от условието сега забелязах, че а1=1 =>а2=2 => ак1=3, аk2=5,..., аkn

[dimitrov89]

Контра пример. pin01!
Ако числата са 10

1 2 3 4 5
6 7 8 9 10

1 3 5 7 9
2 4 6 8 10

1 2 5 7 9
3 4 6 8 10

Има и още.
Не е само един начинът!

[martosss]

Почти сигурен съм, че отговорът е [tex]\red n^2-n[/tex], но сега нямам време да пиша решение, ето как тръгвам аз:

Ясно е, че 1 и 2n са фиксирани в двата края на таблицата - 1 е долу в ляво, а 2n е горе в дясно. Нека подредим числата по следния начин:

[tex](n+1) (n+2) (n+3) ... (2n)[/tex]
[tex]\;\;1\;\;\;\;\;\; 2\;\;\;\;\;\; 3\;\;\; ...\;\; n[/tex]

Това е [tex]\red 1[/tex] вариант.


Сега нека n го преместим в горния ред и последователно слагаме на негово място някое от тези от първата редичка(без 2n), като n и останалите n-1 числа се нареждат по възходящ ред(за тях има само една възможна подредба).
Получаваме [tex]\red n-1[/tex] възможности(понеже горе имаме n-1 числа, а пък 2n е винаги в горния десен ъгъл и не го мърдаме)

Сега нека n и n-1 ги преместим горе, долу остават 2 празни места, които може да заместим с n-1 от горните, като подребдата на две числа е 1 вариант, тоест ако имаме примерно числата 5 и 7 те могат да са наредени само като 57,тъй като наредбата 75 противоречи на условието да са във възходящ ред.

получават се комбинации...

По този начин може да местим 1, 2, 3, 4 елемента и т. н. получава се нещо като Нютоновия бином, ама не точно, всеки случай отговорът е n^2-n

Знам, че това не е пълно и вярно решение, ама е идея, тепърва трябва да видя по какъв начин да го опиша най-разбираемо, но стават нещо от сорта на [tex]C_1^n+C_2^n+C_3^n+...+C_n^n-n[/tex]

[pin01]

да моя грешка сори!!!

[dimitrov89]

1 2 3
4 5 6

1 2 5
3 4 6

1 2 4
3 5 6

1 3 4
2 5 6

1 3 5
2 4 6

при n=3 получавам 5 решения, а според теб трябва да са 6... пропускам ли някое?

[martosss]

да, не ми е верен отговора, и аз не знам защо казах този отговор точно трябва дапомисля още ...

П.П. числата в долния ред са по-малки, тоест 1234 са долу

[dimitrov89]

[xyz]

Всъщност тази задача много ми напомна на задачата за разположение на скобите при умножението на n числа. Добре известна задача с няколко решения (че и едно мое, което не съм го срещал на друго място засега).
Наистина горната редица ги маркираме с "+", а тези от долната с "-". След това разглеждаме 2n редицата с +- маркировката. Ето и примерите:

[luboslav_p]

Точно така е. Търсеният брой начини е точно броя начини за правилно(брой отварящи по-голям или равен на брой затварящи във всеки отрязък) поставяне на n чифта скоби. А всъщност, xyz, ти на състезание по математика или информатика си виждал задачата, защото доколкото знам се е падала и на двтата вида състезания под различни форми. Ще ми е интересно да видя какво точно си написал като решение.

[xyz]

[pin01]

а може ли да се изрази, чрез някакъв вид формула

[sd_pld]

[xyz]

А ето и един линк за тези, които обичат да четат Wikipedia:
http://en.wikipedia.org/wiki/Catalan_number
Задачата е решена по 3 начина. Дори и моят бях почнал да го пиша за да го вкарвам, ама се отказах...

[krassi_holmz]