Регистрирайте сеРегистрирайте се

Задача 10


 
   Форум за математика Форуми -> Задача на седмицата
Предишната тема :: Следващата тема  
Автор Съобщение
Мирослав Стоенчев
Напреднал


Регистриран на: 21 Aug 2007
Мнения: 279

Репутация: 72
гласове: 45

МнениеПуснато на: Fri Jul 11, 2008 6:59 pm    Заглавие: Задача 10

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







Пуснато на:     Заглавие: Реклама

Върнете се в началото
pin01
Начинаещ


Регистриран на: 10 Jul 2008
Мнения: 11


МнениеПуснато на: Fri Jul 11, 2008 8:15 pm    Заглавие:

Мисля, че начина е само един и той е аритметична прогресия с а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
Начинаещ


Регистриран на: 12 Jul 2007
Мнения: 55
Местожителство: Студентски град
Репутация: 12.6
гласове: 4

МнениеПуснато на: Fri Jul 11, 2008 8:56 pm    Заглавие:

Контра пример. 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

Има и още.
Не е само един начинът!
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение Посетете сайта на потребителя AIM Адрес Yahoo Messenger MSN Messenger
martosss
VIP Gold


Регистриран на: 17 Mar 2007
Мнения: 3937
Местожителство: Somewhere over the rainbow
Репутация: 424.2Репутация: 424.2
гласове: 213

МнениеПуснато на: Fri Jul 11, 2008 9:04 pm    Заглавие:

Почти сигурен съм, че отговорът е [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 Smile

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


Последната промяна е направена от martosss на Fri Jul 11, 2008 10:02 pm; мнението е било променяно общо 1 път
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
pin01
Начинаещ


Регистриран на: 10 Jul 2008
Мнения: 11


МнениеПуснато на: Fri Jul 11, 2008 9:08 pm    Заглавие:

да моя грешка сори!!!
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
dimitrov89
Начинаещ


Регистриран на: 12 Jul 2007
Мнения: 55
Местожителство: Студентски град
Репутация: 12.6
гласове: 4

МнениеПуснато на: Fri Jul 11, 2008 9:09 pm    Заглавие:

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... пропускам ли някое?
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение Посетете сайта на потребителя AIM Адрес Yahoo Messenger MSN Messenger
martosss
VIP Gold


Регистриран на: 17 Mar 2007
Мнения: 3937
Местожителство: Somewhere over the rainbow
Репутация: 424.2Репутация: 424.2
гласове: 213

МнениеПуснато на: Fri Jul 11, 2008 10:18 pm    Заглавие:

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

П.П. числата в долния ред са по-малки, тоест 1234 са долу Wink
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
dimitrov89
Начинаещ


Регистриран на: 12 Jul 2007
Мнения: 55
Местожителство: Студентски град
Репутация: 12.6
гласове: 4

МнениеПуснато на: Fri Jul 11, 2008 10:58 pm    Заглавие:

martosss написа:

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


Аз съм хомосексуалист, така че ми е простено....
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение Посетете сайта на потребителя AIM Адрес Yahoo Messenger MSN Messenger
xyz
Напреднал


Регистриран на: 20 May 2007
Мнения: 319

Репутация: 41.2Репутация: 41.2Репутация: 41.2Репутация: 41.2
гласове: 12

МнениеПуснато на: Sun Jul 13, 2008 7:14 pm    Заглавие:

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

Код:

1 2 3
4 5 6
123456
+++---

1 2 5
3 4 6
123456
++--+-

1 2 4
3 5 6
123456
++-+--

1 3 4
2 5 6
123456
+-++--

1 3 5
2 4 6
123456
+-+-+-


Изискването е във всеки префикс броят на минусите да не е повече от броя на плюсовете, което е точно задачата за разположение на скобите. Остава горното изискване да бъде доказано строго...
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
luboslav_p
Начинаещ


Регистриран на: 16 Feb 2008
Мнения: 33
Местожителство: София
Репутация: 12.6
гласове: 7

МнениеПуснато на: Sun Jul 13, 2008 9:41 pm    Заглавие:

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


Регистриран на: 20 May 2007
Мнения: 319

Репутация: 41.2Репутация: 41.2Репутация: 41.2Репутация: 41.2
гласове: 12

МнениеПуснато на: Wed Jul 16, 2008 11:29 am    Заглавие:

luboslav_p написа:
А всъщност, xyz, ти на състезание по математика или информатика си виждал задачата, защото доколкото знам се е падала и на двтата вида състезания под различни форми.

Когато съм се явявал на състезания задачата за разположението на скобите не съм я виждал (мисля че за тази задача говориш). Моето решение е малко дърго и за да се осети смисълът му трябва да е още по-дълго. Затова вместо да я пиша като тема, то ще я опиша в някаква уеб страница и ще дам препратка тук - ама това ще стане по-късно, защото сега съм доста зает...
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
pin01
Начинаещ


Регистриран на: 10 Jul 2008
Мнения: 11


МнениеПуснато на: Wed Jul 16, 2008 10:30 pm    Заглавие:

а може ли да се изрази, чрез някакъв вид формула
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
sd_pld
Начинаещ


Регистриран на: 05 Dec 2006
Мнения: 68

Репутация: 12.9
гласове: 1

МнениеПуснато на: Mon Jul 28, 2008 10:30 pm    Заглавие:

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

[tex]C^{n} _{2n} /(n+1)[/tex]
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
xyz
Напреднал


Регистриран на: 20 May 2007
Мнения: 319

Репутация: 41.2Репутация: 41.2Репутация: 41.2Репутация: 41.2
гласове: 12

МнениеПуснато на: Wed Jul 30, 2008 8:08 am    Заглавие:

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


Регистриран на: 05 Jan 2006
Мнения: 146
Местожителство: Ню Йорк, BG
Репутация: 57.9
гласове: 18

МнениеПуснато на: Sun Aug 17, 2008 5:08 am    Заглавие:

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


По принцип почти не излизат задачи от enumerative combinatorics (аа няма да рискувам да го превеждам на български) по състезанията пo математика. Но по информатика е съвсем различно - покрай динамичното оптимиране се учат числа на Каталан, Стирлинг (2 ред), Бел, Ойлер, кодове на Грей, set-, number- partitions, симетричната група (пермутации), екстремални изброявания и всякакви такива. Понеже задачите по информатика са малко по-доокрасени, трябва да "виждаме" конфигурации като правилните скоби, триангулациите и прочие. Иначе стандартния метод, който би решил задачата е с генериращи функции, ама, както всеки общ метод, може да се получат доста дълги сметки.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Покажи мнения от преди:   
   Форум за математика Форуми -> Задача на седмицата Часовете са според зоната GMT + 2 Часа
Страница 1 от 1

 
Идете на:  
Не Можете да пускате нови теми
Не Можете да отговаряте на темите
Не Можете да променяте съобщенията си
Не Можете да изтривате съобщенията си
Не Можете да гласувате в анкети
You cannot attach files in this forum
Може да сваляте файлове от този форум
Copyright © 2005-2020 math10.com.