Właściwa strona - http://www.wiw.pl/nowinki/matematyka/200006/20000621-001.asp Wiw Matematyka i przyroda: Astronomia Biologia Fizyka Matematyka Humanistyka: Historia Kultura antyczna Literatura Plastyka Czytaj: Biblioteka Delta Inne: Słowniki Szkoły wyższe Wszechświat w obrazkach Nowinki Nowości Jesteś tutaj: Wirtualny Wszechświat Matematyka Nowinki matematyczne Jesteś tutaj nowinka: Bałagan w bibliotece czyli trudna odpowiedź na proste pytanie autor: Paweł Strzelecki z nbspdnia: 21-06-2000 Najświeższe nowinki Najlepsza matematyka w Internecie Inernetowa witryna ScientificAmerican.com, związana ze słynnym czasopismem "Scientific American" którego polska edycja ukazuje się jako "Świat Nauki", ogłosiła listę najlepszych naukowych witryn w anglojęzycznej Sieci - po pięć w każdej z dziesięciu dziedzin. Kostyczny, dogmatyczny pedant 18 marca 2001 r. minęło 130 lat od śmierci angielskiego matematyka o nazwisku znanym niemal każdemu dziecku, które w szkole liznęło odrobinę logiki zdań. Historycy matematyki podejrzewają go o rozpowszechnianie złośliwej anegdoty o Bogu, Diderocie i Eulerze. Wszystkie nowinki Powrót Matematyka - strona główna Nowinki Wirtualnego Wszechświata Szukacz Przeszukaj za pomocą Szukacza: witrynę Matematyka cały Wirtualny Wszechświat Przeszukaj inne witryny wydawnictwa Prószyński i S-ka Jak zadawać pytania? Zespół Osoby, które przygotowały dla Ciebie witrynę Nowinki Bałagan w bibliotece czyli trudna odpowiedź na proste pytanie W 1999 r. panowie J. Baik, P. Deift i K. Johansson rozwiązali pewien stary problem kombinatoryczny, otwarty od kilkudziesięciu lat. Nie byłoby w tym nic szczególnego w matematyce pełno jest problemów otwartych od kilkudziesięciu lat, gdyby nie fakt, że problem ma dość elementarne, niemal rekreacyjne sformułowanie, a rozwiązanie odwołuje się do potężnych środków, daleko wykraczających poza kombinatorykę. Są wśród nich równania różniczkowe, funkcje specjalne, operatory całkowe i inne przerażające narzędzia; prześledzenie dowodów dla nikogo nie będzie bułką z masłem. Pod tym względem sprawa przypomina historię Wielkiego Twierdzenia Fermata w miniaturze: elementarne pytanie i skomplikowany, zrozumiały wyłącznie dla wybrańców dowód. Zainteresowani szczegółami powinni zajrzeć do przeglądowego artykułu Percy'ego Deifta w "Notices of the American Mathematical Society" patrz strona wwww: http://www.ams.org/ notices/200006/200006-toc.html z czerwca /lipca 2000 r. Dla wszystkich pozostałych - garść informacji. Wyobraźmy sobie, że na półce mamy N książek, które chcemy ustawić w porządku alfabetycznym. Jako że nie lubimy pracować, chcielibyśmy możliwie najmniejszą liczbę razy zdejmować tę czy inną książkę z półki i wstawiać w inne miejsce. Ile książek trzeba przestawić? To zależy od tego, jaki bałagan mamy w bibliotece. Ustawienie książek jest pewną permutacją liczb 1, 2, ..., N. Jeśli najdłuższy podciąg rosnący zawarty w tej permutacji ma długość , to najmniejsza liczba przestawień koniecznych do uporządkowania biblioteki jest oczywiście ... równa N- . Oto banalny przykład: w permutacji 1,2,5,4,3 najdłuższymi podciągami rosnącymi są 1,2,4, 1,2,3 oraz 1,2,5; aby wszystkie liczby stały w porządku rosnącym, wystarczy wstawić w odpowiednie miejsce dwie z nich. Nie to jednak nas interesuje. Z punktu widzenia leniwego bibliotekarza ciekawe jest następujące pytanie: jeśli muszę często porządkować książki na bardzo długich półkach, to jaka, średnio biorąc, będzie najmniejsza liczba koniecznych przestawień? Czego powinienem się spodziewać? Ile będę musiał się nadreptać? Pytanie jest ciekawe nie tylko dla leniwego bibliotekarza; w rozmaitych wersjach i odmianach pojawia się, oprócz kombinatoryki i statystyki, również w teorii macierzy losowych, którą wprowadził do fizyki teoretycznej noblista Eugene Wigner, by opisywać rozpraszanie neutronów. Oto odpowiedź: dla dużych N do uporządkowania losowo wybranej permutacji potrzeba średnio przestawień, a rozrzut najmniejszej liczby koniecznych przestawień jest w przybliżeniu proporcjonalny do . Wygląda elementarnie, lecz uzasadnienie wymaga przedzierania się przez liczne obszary matematyki, bardzo odległe od wyjściowego pytania. Paweł Strzelecki Najdłuższy podciąg rosnący Pytanie o długość najdłuższego podciągu rosnącego zawartego w ciągu mającym ustaloną liczbę różnych wyrazów ma swoją ciekawą historię. W 1935 r. Erd s i Szekeres wykazali, że każdy ciąg mający n 2 +1 różnych wyrazów zawiera podciąg rosnący lub malejący złożony z n+1 wyrazów. W nieco innej wersji to samo pytanie pojawiło się na jednej ze słynnych Moskiewskich Olimpiad Matematycznych; więcej informacji znajdzie Czytelnik w artykule prof. Aleksandra Pełczyńskiego "Zadanie o 101 liczbach" w "Delcie" z maja 1974 r. angielska wersja artykułu jest dostępna w Internecie: patrz strona www: http://www.mimuw.edu.pl/ delta/delta9/ Pelczyn/Pelczyns.html. wróć Czego powinienem się spodziewać? Oto ścisłe sformułowanie problemu. Załóżmy, że przestrzeń probablistyczna jest zbiorem wszystkich permutacji liczb 1, 2, ..., N. Wszystkie zdarzenia elementarne są równoprawdopodobne. Niech będzie zmienną losową, przyporządkowującą każdej permutacji długość najdłuższego zawartego w niej ciągu rosnącego. Pytanie brzmi: jak szybko rośnie, dla N dążących do nieskończoności, wartość oczekiwana i wariancja owej zmiennej losowej? Wymarzona odpowiedź: podać rozwinięcia asymptotyczne obu ciągów. wróć Odpowiedź Oto odpowiedź w ścisłym sformułowaniu: , , gdzie liczby c 1 i c 2 są tzw. absolutnymi stałymi, wyrażającymi się w dość skomplikowany sposób przez funkcje specjalne konkretnie: przez klasyczną funkcję Airy'ego, czyli jedno z rozwiązań równania różniczkowego . wróć [ góra strony ] Wiw - strona główna | Astronomia i kosmologia | Biologia | Fizyka | Matematyka | Historia | Kultura antyczna | Literatura | Szkoła-Plastyka | Nowinki | Nowości | Szkoły wyższe | Biblioteka | Wszechświat w obrazkach | Słowniki | Copyright Prószyński i S-ka SA 2000. All rights reserved. Wszystkie prawa zastrzeżone.