Informacje
  Wiw.pl   Na bieżąco:  Informacje   Co nowego   Matematyka i przyroda:  Astronomia   Biologia   Fizyka   Matematyka   Modelowanie rzeczywistości   Humanistyka:  Filozofia   Historia   Kultura antyczna   Literatura   Sztuka   Czytaj:  Biblioteka   Delta   Wielcy i więksi   Przydatne:  Słowniki   Co i gdzie studiować   Wszechświat w obrazkach    
  Jesteś tutaj:  Wirtualny Wszechświat > Informacje > Nowinki 2000-2002 > Matematyka > Nowinka z dn. 21-06-2000  
 Jesteś tutaj
nowinka:
Bałagan w bibliotece czyli trudna odpowiedź na proste pytanie
autor:
Paweł Strzelecki
z dnia:
21-06-2000





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.

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 n2+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 c1 i c2 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.pl  |  Na bieżąco  |  Informacje  |  Co nowego  |  Matematyka i przyroda  |  Astronomia  |  Biologia  |  Fizyka  |  Matematyka  |  Modelowanie rzeczywistości  |  Humanistyka  |  Filozofia  |  Historia  |  Kultura antyczna  |  Literatura  |  Sztuka  |  Czytaj  |  Biblioteka  |  Delta  |  Wielcy i więksi  |  Przydatne  |  Słowniki  |  Co i gdzie studiować  |  Wszechświat w obrazkach