Rekrutacja do szkoły odbywa się w trzech etapach:

  1. Testowanie online: Po wypełnieniu formularza zgłoszeniowego wnioskodawcy otrzymasz wiadomość e-mail z linkiem. Na rozwiązanie zadań testowych przeznaczono pięć godzin.
  2. Egzamin pisemny: Dla osób rozpoczynających naukę w moskiewskim oddziale ShAD egzamin odbędzie się osobiście w Moskwie pod koniec maja lub na początku czerwca.
    Osoby wchodzące do oddziałów i zaoczny przystąpi do egzaminu online na początku czerwca. W egzamin pisemny W konkursie mogą wziąć udział wyłącznie osoby, które pomyślnie przeszły etap testów online.
  3. Wywiad: na przełomie czerwca i lipca dla wszystkich, którzy pomyślnie przeszli dwa pierwsze etapy, odbędą się rozmowy kwalifikacyjne w oddziałach ShAD lub przez Skype.

Przygotowanie

Po przyjęciu do ShAD wiedza jest sprawdzana w ramach programu ogólnego, obejmującego podstawowe działy wyższej algebry, analizę matematyczną, kombinatorykę, teorię prawdopodobieństwa oraz podstawy programowania. Przykładowe zadania egzaminu pisemnego:

  • Rekrutacja 2012
  • Rekrutacja 2013
  • Rekrutacja 2014
  • Rekrutacja 2016
  • Rekrutacja 2017

Szkolenie płatne

Kandydaci, którzy dobrze wypadli na rozmowie kwalifikacyjnej, ale nie przeszli konkursu ogólnego, będą mogli rozpocząć studia za wynagrodzeniem (tylko w oddziale w Moskwie). Studia płatne nie różnią się od studiów bezpłatnych - musisz wykonywać te same trudne zadania, dotrzymując rygorystycznych terminów. Czesne kosztuje 110 000 rubli za semestr. Jeżeli student zakończy semestr z ocenami dobrymi i celującymi, czesne dla niego zostaje obniżone do 55 000 za semestr. Ci, którzy zdadzą „dobrze” i „doskonało” dwie sesje z rzędu, kontynuują naukę za darmo.

Lato to czas egzaminów wstępnych. W tej chwili kończy się proces selekcji do Szkoły Analizy Danych Yandex – trwają rozmowy kwalifikacyjne z osobami, które zdały już egzamin. ShAD uczy uczenia maszynowego, widzenia komputerowego, analizy tekstu w języku naturalnym i innych dziedzin współczesnej informatyki. Studenci przez dwa lata studiują przedmioty, które zwykle nie są ujęte w programach uniwersyteckich, choć cieszą się dużym zainteresowaniem zarówno w nauce, jak i przemyśle. Studiować można nie tylko w Moskwie – Szkoła posiada filie w Jekaterynburgu, Mińsku, Kijowie, Nowosybirsku, Petersburgu. Istnieje również dział korespondencyjny, w którym można uczyć się, oglądając wykłady wideo i korespondując z nauczycielami Szkoły Moskiewskiej pocztą.

Aby jednak dostać się do ShAD, należy pomyślnie przejść trzy etapy - wypełnić formularz zgłoszeniowy na stronie internetowej, zdać egzamin wstępny i przyjść na rozmowę kwalifikacyjną. Co roku do ShAD wchodzą studenci ostatnich lat, absolwenci i studenci studiów podyplomowych z Moskiewskiego Uniwersytetu Państwowego, Moskiewskiego Instytutu Fizyki i Technologii, Wyższej Szkoły Ekonomicznej, ITMO, Uniwersytetu Państwowego w Petersburgu, UrFU, NSU i nie wszyscy radzą sobie z naszymi testy. W tym roku otrzymaliśmy zgłoszenia od 3500 osób, z czego 1000 zostało dopuszczonych do egzaminu, a jedynie 350 zdało go pomyślnie.

Dla tych, którzy chcą spróbować swoich sił i zrozumieć, do czego są zdolni, przygotowaliśmy analizę Egzamin wstępny W tym roku. Opcja, którą dla Ciebie wybraliśmy, została rozwiązana przez 56% osób, które ją rozwiązały. W tej tabeli możesz zobaczyć, ile osób było w stanie rozwiązać każde z zawartych w niej zadań.

Najpierw jednak wyjaśnię, co sprawdzamy na egzaminie i jak podchodzimy do jego przygotowania. W pierwszych latach istnienia SAD nie było egzaminu pisemnego, ponieważ wniosków było jeszcze niewiele, a z każdym, kto zdał test online, można było porozmawiać osobiście. Ale wywiady były dłuższe; niektórzy absolwenci pamiętają, że rozmawiali z nimi przez sześć godzin, oferując im wiele złożone zadania. Potem było więcej chętnych - a w 2012 roku pojawił się egzamin pisemny.

Za stworzenie wariantu odpowiadają kuratorzy moskiewskiego ShAD, wśród których jestem ja; W wyborze zadań pomagają im koledzy z oddziałów. Liczba zadań w wersji nie zmieniła się zbytnio przez te cztery lata: początkowo było ich siedem, a w zeszłym roku osiem. Każda opcja ma problemy matematyczne (od pięciu do siedmiu) i problemy algorytmiczne (jeden lub dwa).

Jeśli chodzi o matematykę, sprawdzamy oczywiście, czy kandydaci są biegli w głównych sekcjach programu: algebrze, analizie matematycznej, kombinatoryce i teorii prawdopodobieństwa. Ale dla nas nie jest ważna wiedza, którą zdobywa się przez wkuwanie i tydzień po sprawdzianie czy egzaminie zapomina się – jak okropne formuły ze stołu Całki nieoznaczone lub Funkcje dystrybucji Studentów; Dlatego też umożliwiamy kandydatom zabranie na egzamin pisemny wszelkich źródeł papierowych. O wiele cenniejsze jest zrozumienie istoty tego, co się dzieje, a także umiejętność zastosowania standardowych faktów i metod w nietypowych sytuacjach. Staramy się również ograniczyć złożoność obliczeniową do minimum; nawet dwucyfrowe rzadko trzeba mnożyć. Dzięki temu na egzaminie nie spotkasz się z rutynowymi i żmudnymi ćwiczeniami obliczeniowymi, a wiele zadań będzie wydawać się niestandardowych, a być może nawet olimpijskich.

Jeśli chodzi o algorytmy, unikamy zadań wymagających znajomości konkretnych struktur danych (drzewa wyszukiwania, tablice mieszające itp.) lub algorytmów (algorytmy szybkiego sortowania, algorytmy wyszukiwania najkrótszych ścieżek na grafach itp.). Ponadto nie wymagamy od kandydatów napisania implementacji wymyślonego algorytmu w jakimkolwiek języku programowania; wręcz przeciwnie, wszelkimi możliwymi sposobami staramy się od tego odwieść ludzi. Rzeczywiście na egzaminie pisemnym najbardziej interesuje nas nie umiejętność programowania, ale umiejętność jasnego opisania algorytmu i, jeśli to konieczne, przekonania czytelnika, że ​​spełnia on ograniczenia dotyczące czasu działania i ilości przydzielonej pamięci. Akceptowane są jednak decyzje zawierające kod w dowolnym języku, który jesteśmy w stanie odczytać, jednak są one trudniejsze do sprawdzenia i dodatkowo nadal muszą być zaopatrzone w uzasadnienie ich poprawności.

Problem 1

Znajdź granicę ciągu (a n), dla którego

Odpowiedź


Rozwiązanie

Najpierw udowodnimy, że ciąg jest zbieżny. Jeśli jakiś< 0 , To n+1< 0 , więc jest ograniczony z góry. Porównajmy jakiś I n+1:


Widzimy to, kiedy za n ∈(-1;0) istnieje nierówność jakiś< a (n+1) , czyli ciąg wzrasta. Zgodnie z twierdzeniem Weierstrassa ma on granicę. Aby to znaleźć, przejdźmy do granicy naszej relacji powtarzania:
skąd granicą może być jedna z liczb 0, –1 i 4. Nietrudno zrozumieć, że jest to 0.

Problem 2

Na płaszczyźnie pokrytej identycznymi prostokątami o bokach 10 i 20 (prostokąty mają sąsiadujące boki) narysuj losowy okrąg o promieniu 4. Znajdź prawdopodobieństwo, że okrąg ma punkty wspólne z dokładnie trzema prostokątami.

Odpowiedź


Rozwiązanie

Będziemy monitorować położenie środka okręgu. Jest oczywiste, że możemy ograniczyć nasze rozważania do wnętrza pojedynczego prostokąta. Łatwo zauważyć, że aby okrąg przecinał dokładnie trzy prostokąty, muszą być spełnione dwa warunki: (1) odległości od środka do dwóch najbliższych boków prostokąta muszą być mniejsze niż 4; (2) odległość do najbliższego wierzchołka prostokąta musi być większa niż 4. Wiedząc o tym, możemy przedstawić zbiór punktów spełniających te warunki.

Dlatego wymagane prawdopodobieństwo jest równe

Problem 3

Dima i Wania na zmianę wypełniają matrycę rozmiarów 2n×2n. Celem Wanyi jest sprawienie, aby otrzymana macierz miała wartość własną 1, a celem Dimy jest temu zapobiec. Dima idzie pierwszy. Czy któryś z nich ma zwycięską strategię?

Odpowiedź

Przy odpowiedniej strategii Wania wygra.


Rozwiązanie

Wynikowa macierz A będzie miała wartość własną 1, jeśli macierz A–E będzie zdegenerowany. Wania może to osiągnąć na przykład w następujący sposób. Po tym, jak Dima weszła w jakiś element ij, Wania wchodzi w nowy element ik w tej samej linii, aby tak było a ik -δ ik =-(a ij -δ ij), Gdzie δ ij– Symbol Kroneckera. Następnie suma liczb w każdym z wierszy macierzy A–E będzie równa zeru, czyli macierzy A–E będzie zdegenerowany.

Problem 4

Znajdź wyznacznik macierzy A=(a ij), Gdzie

Odpowiedź


Rozwiązanie

Skorzystajmy ze wzoru: Odejmij poprzednią liczbę od każdego wiersza macierzy, a następnie poprzednią od każdej kolumny. Wynikowa macierz będzie wyglądać następująco:


Kontynuując rozumowanie przez indukcję, jesteśmy przekonani, że wyznacznik macierzy pierwotnej jest równy wyznacznikowi macierzy jednostkowej, tj. 1.

Problem 5

Biorąc pod uwagę dwie tablice liczb całkowitych A I B i wszystkie elementy B są różne. Trzeba znaleźć zestaw indeksów ja_1< i_2 <… < i_k , dla którego zestaw a,..., a jest permutacją elementów tablicy b i różnicą i_k - i_1 minimalne możliwe. Limit czasu - O(nk)(ale może uda Ci się to zrobić szybciej), z pamięci - NA).

Rozwiązanie

Można to zrobić w jednym przejściu przez tablicę a. Za każdym razem, gdy napotykamy element tablicy B, zapisujemy go i jego liczbę w specjalnych tablicach. Jednocześnie utrzymujemy w tych tablicach segment I, w którym mamy nadzieję znaleźć wszystkie różne elementy B. Oczywiste jest, że jeśli kolejny element tablicy a pokrywa się z pierwszym elementem odcinka I, to wyraźnie nie mogę być najkrótszy segment spełniający warunki zadania i możemy przesunąć jego lewy koniec. Jeśli w następnym kroku zrozumiemy, że I zawiera wszystkie różne elementy B, to jestem kandydatem do odpowiedzi; w tym przypadku przesuwamy także jego lewy koniec.

Stopień NA) oczywiste z pamięci. Stopień O(nk) złożoność można uzasadnić następująco: wszystko robimy za jednym razem (stąd N) i na każdym kroku należy szukać elementu w tablicy B(stąd k). Oczywiste jest, że algorytm można ulepszyć: jeśli najpierw posortujesz B i użyj wyszukiwania binarnego, otrzymamy O(n log k). Jeśli użyjesz doskonałego mieszania, możesz osiągnąć złożoność O(n+k).

Problem 6

W roku 2222 turnieje siatkówki rozgrywane są według nowego systemu. Mówią, że drużyna A znakomity drużyna B, jeśli A pokonała B, lub dowolna drużyna, która pokonała B. Każda para drużyn gra raz. Remis wykluczają przepisy dotyczące siatkówki. Zespół, który przewyższy wszystkie inne zespoły, zostaje ogłoszony mistrzem. (a) Udowodnij, że mistrz na pewno będzie istniał. (b) Udowodnij, że nie może być dokładnie dwóch mistrzów.

Rozwiązanie

Umówmy się, że każda drużyna za turniej otrzyma liczbę punktów równą liczbie drużyn, które przekroczyła. Najpierw udowodnimy następujący prosty lemat:

Lemat. Niech drużyna E nie przewyższy drużyny K. Wtedy K zdobył więcej punktów niż E.

Dowód. Jeśli E nie pokona K, wówczas K pokonał drużynę E, a także wszystkie drużyny, które pokonała drużyna E.

Niech teraz X będzie drużyną, którą pokonała drużyna E. Jeśli E pokonał X, to K również pokonał X. Zatem K pokonuje X. Jeśli E pokonał drużynę F, która pokonała X, to zauważ, że K również wygrał w F. Oznacza to, że K wygrał z F, który pokonał X, czyli K jest lepszy od X. W sumie K jest lepszy od wszystkich drużyn, które przewyższył E, a nawet E dodatkowo, czyli o co najmniej jedną drużynę więcej niż E. Lemat jest następujący udowodniony.

(a) Niech A będzie drużyną, która zdobyła maksymalną liczbę punktów. Udowodnijmy, że A jest mistrzem. Załóżmy, że tak nie jest i istnieje drużyna B, której A nie pokonał. Z lematu dowiadujemy się, że B zdobył więcej punktów niż A. Sprzeczność.

(b) Miejmy dwóch mistrzów: A i B. Grali ze sobą; Załóżmy na przykład, że wygra A. Ponieważ B jest lepszy od wszystkich innych drużyn (a w szczególności A), wówczas B pokona jakąś drużynę, która pokonała A.

Załóżmy na początek, że są drużyny, które pokonały zarówno A, jak i B. Następnie możemy pokazać, że ta z nich (nazwijmy ją C), która zdobędzie najwięcej punktów, zostanie trzecim mistrzem. Tak naprawdę, niech E będzie drużyną, której nie pokonał C. Następnie, po pierwsze, E pokonał zarówno A, jak i B, a po drugie, E zdobył więcej punktów niż C. Sprzeczność.

Niech teraz nie będzie drużyn, które pokonały A i B. Rozważmy zbiór wszystkich takich drużyn, które pokonały A, ale przegrały z B. Zauważ, że nie jest on pusty (patrz wyżej). Wśród nich weźmy drużynę z największą liczbą punktów. Następnie korzystając z lematu możemy ustalić, że ta drużyna jest trzecim mistrzem.

Problem 7

Oceń całkę

Lato to czas egzaminów wstępnych. W tej chwili kończy się proces selekcji do Szkoły Analizy Danych Yandex – trwają rozmowy kwalifikacyjne z osobami, które zdały już egzamin. ShAD uczy uczenia maszynowego, widzenia komputerowego, analizy tekstu w języku naturalnym i innych dziedzin współczesnej informatyki. Studenci przez dwa lata studiują przedmioty, które zwykle nie są ujęte w programach uniwersyteckich, choć cieszą się dużym zainteresowaniem zarówno w nauce, jak i przemyśle. Studiować można nie tylko w Moskwie – Szkoła posiada filie w Jekaterynburgu, Mińsku, Kijowie, Nowosybirsku, Petersburgu. Istnieje również dział korespondencyjny, w którym można uczyć się, oglądając wykłady wideo i korespondując z nauczycielami Szkoły Moskiewskiej pocztą.

Aby jednak dostać się do ShAD, należy pomyślnie przejść trzy etapy - wypełnić formularz zgłoszeniowy na stronie internetowej, zdać egzamin wstępny i przyjść na rozmowę kwalifikacyjną. Co roku do ShAD wchodzą studenci ostatnich lat, absolwenci i studenci studiów podyplomowych z Moskiewskiego Uniwersytetu Państwowego, Moskiewskiego Instytutu Fizyki i Technologii, Wyższej Szkoły Ekonomicznej, ITMO, Uniwersytetu Państwowego w Petersburgu, UrFU, NSU i nie wszyscy radzą sobie z naszymi testy. W tym roku otrzymaliśmy zgłoszenia od 3500 osób, z czego 1000 zostało dopuszczonych do egzaminu, a jedynie 350 zdało go pomyślnie.

Dla tych, którzy chcą spróbować swoich sił i zrozumieć, na co ich stać, przygotowaliśmy analizę tegorocznego egzaminu wstępnego. Opcja, którą dla Ciebie wybraliśmy, została rozwiązana przez 56% osób, które ją rozwiązały. W tej tabeli możesz zobaczyć, ile osób było w stanie rozwiązać każde z zawartych w niej zadań.

Najpierw jednak wyjaśnię, co sprawdzamy na egzaminie i jak podchodzimy do jego przygotowania. W pierwszych latach istnienia SAD nie było egzaminu pisemnego, ponieważ wniosków było jeszcze niewiele, a z każdym, kto zdał test online, można było porozmawiać osobiście. Ale wywiady były dłuższe; Niektórzy absolwenci pamiętają, że uczestniczyli w sześciogodzinnych rozmowach kwalifikacyjnych i zadawano im wiele trudnych zadań. Potem było więcej chętnych - a w 2012 roku pojawił się egzamin pisemny.

Za stworzenie wariantu odpowiadają kuratorzy moskiewskiego ShAD, wśród których jestem ja; W wyborze zadań pomagają im koledzy z oddziałów. Liczba zadań w wersji nie zmieniła się zbytnio przez te cztery lata: początkowo było ich siedem, a w zeszłym roku osiem. Każda opcja ma problemy matematyczne (od pięciu do siedmiu) i problemy algorytmiczne (jeden lub dwa).

Jeśli chodzi o matematykę, sprawdzamy oczywiście, czy kandydaci są biegli w głównych sekcjach programu: algebrze, analizie matematycznej, kombinatoryce i teorii prawdopodobieństwa. Ale dla nas nie jest ważna wiedza, którą zdobywa się przez wkuwanie i tydzień po sprawdzianie czy egzaminie zapomina się – jak okropne wzory z tablicy całek nieoznaczonych albo rozkładu Studenta; Dlatego też umożliwiamy kandydatom zabranie na egzamin pisemny wszelkich źródeł papierowych. O wiele cenniejsze jest zrozumienie istoty tego, co się dzieje, a także umiejętność zastosowania standardowych faktów i metod w nietypowych sytuacjach. Staramy się również ograniczyć złożoność obliczeniową do minimum; Nawet liczby dwucyfrowe należy mnożyć rzadko. Dzięki temu na egzaminie nie spotkasz się z rutynowymi i żmudnymi ćwiczeniami obliczeniowymi, a wiele zadań będzie wydawać się niestandardowych, a być może nawet olimpijskich.

Jeśli chodzi o algorytmy, unikamy zadań wymagających znajomości konkretnych struktur danych (drzewa wyszukiwania, tablice mieszające itp.) lub algorytmów (algorytmy szybkiego sortowania, algorytmy wyszukiwania najkrótszych ścieżek na grafach itp.). Ponadto nie wymagamy od kandydatów napisania implementacji wymyślonego algorytmu w jakimkolwiek języku programowania; wręcz przeciwnie, wszelkimi możliwymi sposobami staramy się od tego odwieść ludzi. Rzeczywiście na egzaminie pisemnym najbardziej interesuje nas nie umiejętność programowania, ale umiejętność jasnego opisania algorytmu i, jeśli to konieczne, przekonania czytelnika, że ​​spełnia on ograniczenia dotyczące czasu działania i ilości przydzielonej pamięci. Akceptowane są jednak decyzje zawierające kod w dowolnym języku, który jesteśmy w stanie odczytać, jednak są one trudniejsze do sprawdzenia i dodatkowo nadal muszą być zaopatrzone w uzasadnienie ich poprawności.

Problem 1

Znajdź granicę ciągu (a n), dla którego

Odpowiedź


Rozwiązanie

Najpierw udowodnimy, że ciąg jest zbieżny. Jeśli jakiś< 0 , To n+1< 0 , więc jest ograniczony z góry. Porównajmy jakiś I n+1:


Widzimy to, kiedy za n ∈(-1;0) istnieje nierówność jakiś< a (n+1) , czyli ciąg wzrasta. Zgodnie z twierdzeniem Weierstrassa ma on granicę. Aby to znaleźć, przejdźmy do granicy naszej relacji powtarzania:
skąd granicą może być jedna z liczb 0, –1 i 4. Nietrudno zrozumieć, że jest to 0.

Problem 2

Na płaszczyźnie pokrytej identycznymi prostokątami o bokach 10 i 20 (prostokąty mają sąsiadujące boki) narysuj losowy okrąg o promieniu 4. Znajdź prawdopodobieństwo, że okrąg ma punkty wspólne z dokładnie trzema prostokątami.

Odpowiedź


Rozwiązanie

Będziemy monitorować położenie środka okręgu. Jest oczywiste, że możemy ograniczyć nasze rozważania do wnętrza pojedynczego prostokąta. Łatwo zauważyć, że aby okrąg przecinał dokładnie trzy prostokąty, muszą być spełnione dwa warunki: (1) odległości od środka do dwóch najbliższych boków prostokąta muszą być mniejsze niż 4; (2) odległość do najbliższego wierzchołka prostokąta musi być większa niż 4. Wiedząc o tym, możemy przedstawić zbiór punktów spełniających te warunki.

Dlatego wymagane prawdopodobieństwo jest równe

Problem 3

Dima i Wania na zmianę wypełniają matrycę rozmiarów 2n×2n. Celem Wanyi jest sprawienie, aby otrzymana macierz miała wartość własną 1, a celem Dimy jest temu zapobiec. Dima idzie pierwszy. Czy któryś z nich ma zwycięską strategię?

Odpowiedź

Przy odpowiedniej strategii Wania wygra.


Rozwiązanie

Wynikowa macierz A będzie miała wartość własną 1, jeśli macierz A–E będzie zdegenerowany. Wania może to osiągnąć na przykład w następujący sposób. Po tym, jak Dima weszła w jakiś element ij, Wania wchodzi w nowy element ik w tej samej linii, aby tak było a ik -δ ik =-(a ij -δ ij), Gdzie δ ij– Symbol Kroneckera. Następnie suma liczb w każdym z wierszy macierzy A–E będzie równa zeru, czyli macierzy A–E będzie zdegenerowany.

Problem 4

Znajdź wyznacznik macierzy A=(a ij), Gdzie

Odpowiedź


Rozwiązanie

Skorzystajmy ze wzoru: Odejmij poprzednią liczbę od każdego wiersza macierzy, a następnie poprzednią od każdej kolumny. Wynikowa macierz będzie wyglądać następująco:


Kontynuując rozumowanie przez indukcję, jesteśmy przekonani, że wyznacznik macierzy pierwotnej jest równy wyznacznikowi macierzy jednostkowej, tj. 1.

Problem 5

Biorąc pod uwagę dwie tablice liczb całkowitych A I B i wszystkie elementy B są różne. Trzeba znaleźć zestaw indeksów ja_1< i_2 <… < i_k , dla którego zestaw a,..., a jest permutacją elementów tablicy b i różnicą i_k - i_1 minimalne możliwe. Limit czasu - O(nk)(ale może uda Ci się to zrobić szybciej), z pamięci - NA).

Rozwiązanie

Można to zrobić w jednym przejściu przez tablicę a. Za każdym razem, gdy napotykamy element tablicy B, zapisujemy go i jego liczbę w specjalnych tablicach. Jednocześnie utrzymujemy w tych tablicach segment I, w którym mamy nadzieję znaleźć wszystkie różne elementy B. Oczywiste jest, że jeśli kolejny element tablicy a pokrywa się z pierwszym elementem odcinka I, to wyraźnie nie mogę być najkrótszy segment spełniający warunki zadania i możemy przesunąć jego lewy koniec. Jeśli w następnym kroku zrozumiemy, że I zawiera wszystkie różne elementy B, to jestem kandydatem do odpowiedzi; w tym przypadku przesuwamy także jego lewy koniec.

Stopień NA) oczywiste z pamięci. Stopień O(nk) złożoność można uzasadnić następująco: wszystko robimy za jednym razem (stąd N) i na każdym kroku należy szukać elementu w tablicy B(stąd k). Oczywiste jest, że algorytm można ulepszyć: jeśli najpierw posortujesz B i użyj wyszukiwania binarnego, otrzymamy O(n log k). Jeśli użyjesz doskonałego mieszania, możesz osiągnąć złożoność O(n+k).

Problem 6

W roku 2222 turnieje siatkówki rozgrywane są według nowego systemu. Mówią, że drużyna A znakomity drużyna B, jeśli A pokonała B, lub dowolna drużyna, która pokonała B. Każda para drużyn gra raz. Remis wykluczają przepisy dotyczące siatkówki. Zespół, który przewyższy wszystkie inne zespoły, zostaje ogłoszony mistrzem. (a) Udowodnij, że mistrz na pewno będzie istniał. (b) Udowodnij, że nie może być dokładnie dwóch mistrzów.

Rozwiązanie

Umówmy się, że każda drużyna za turniej otrzyma liczbę punktów równą liczbie drużyn, które przekroczyła. Najpierw udowodnimy następujący prosty lemat:

Lemat. Niech drużyna E nie przewyższy drużyny K. Wtedy K zdobył więcej punktów niż E.

Dowód. Jeśli E nie pokona K, wówczas K pokonał drużynę E, a także wszystkie drużyny, które pokonała drużyna E.

Niech teraz X będzie drużyną, którą pokonała drużyna E. Jeśli E pokonał X, to K również pokonał X. Zatem K pokonuje X. Jeśli E pokonał drużynę F, która pokonała X, to zauważ, że K również wygrał w F. Oznacza to, że K wygrał z F, który pokonał X, czyli K jest lepszy od X. W sumie K jest lepszy od wszystkich drużyn, które przewyższył E, a nawet E dodatkowo, czyli o co najmniej jedną drużynę więcej niż E. Lemat jest następujący udowodniony.

(a) Niech A będzie drużyną, która zdobyła maksymalną liczbę punktów. Udowodnijmy, że A jest mistrzem. Załóżmy, że tak nie jest i istnieje drużyna B, której A nie pokonał. Z lematu dowiadujemy się, że B zdobył więcej punktów niż A. Sprzeczność.

(b) Miejmy dwóch mistrzów: A i B. Grali ze sobą; Załóżmy na przykład, że wygra A. Ponieważ B jest lepszy od wszystkich innych drużyn (a w szczególności A), wówczas B pokona jakąś drużynę, która pokonała A.

Załóżmy na początek, że są drużyny, które pokonały zarówno A, jak i B. Następnie możemy pokazać, że ta z nich (nazwijmy ją C), która zdobędzie najwięcej punktów, zostanie trzecim mistrzem. Tak naprawdę, niech E będzie drużyną, której nie pokonał C. Następnie, po pierwsze, E pokonał zarówno A, jak i B, a po drugie, E zdobył więcej punktów niż C. Sprzeczność.

Niech teraz nie będzie drużyn, które pokonały A i B. Rozważmy zbiór wszystkich takich drużyn, które pokonały A, ale przegrały z B. Zauważ, że nie jest on pusty (patrz wyżej). Wśród nich weźmy drużynę z największą liczbą punktów. Następnie korzystając z lematu możemy ustalić, że ta drużyna jest trzecim mistrzem.

Problem 7

Oceń całkę
Cześć! Miło nam pogratulować przyjęcia do Szkoły Analizy Danych! Bliżej września kustosz Twojego oddziału napisze o kwestiach organizacyjnych.

Okazuje się, że jestem w szkole. I, jestem prawie pewien, najstarszy uczeń. Z parami nie będzie problemu, będzie można nawet wybrać się na lodowisko (z wyjątkiem tego, że jazdę z instruktorem trzeba będzie przełożyć na weekend). A teraz co zrobiłem.

Znajomy zasugerował, abyś spróbował szczęścia: „można”. Selekcja internetowa to było piekło i ciemność, cierpiałem cztery godziny. Chociaż, muszę przyznać, trochę czytałem: w zadaniach programistycznych po prostu tłumaczyłem programy z pseudokodu na C++ i po prostu rozwiązałem jedno zadanie macierzowe bez znalezienia klucza, korzystając z Excela. Nie wiedziałem, co to jest „dodatni wskaźnik bezwładności” (czy dobrze przeliterowałem tę nazwę?) - musiałem sprawdzić, okazało się, że jest to po prostu liczba elementów dodatnich w rozwinięciu diagonalnym formy kwadratowej.

Cóż, drugi etap to egzamin bezpośredni. Kupiłem e-czytnik, zakryłem się notatkami i zacząłem się przygotowywać. Najbardziej bałem się strasznych całek: każdy student pierwszego roku by mnie w tym prześcignął. Cóż, przejdźmy do rzeczy. To właśnie zaoferowali nam Yandexoidowie podczas egzaminu (warunki zadań zostały obniżone).

  1. Na ile sposobów można przejść od (0,0,0) do ( N, 2N, 3N), czy możesz wykonać kroki o +1 wzdłuż dowolnej osi?
  2. Znajdź 319. pochodną w miejscu zerowym funkcji (x²+17) / (x 4 −5x²+4)
  3. Ile permutacji dojeżdża do (123)(456)?
  4. W trójkącie równobocznym ABC obszar 1 wybierz punkt M. Znajdź oczekiwania dotyczące obszaru A.B.M..
  5. ∫ 1 / √1+e X dx
  6. Pokaż, że macierz liczb całkowitych nie ma wymiernych (niecałkowitych) wartości własnych.
  7. Na okrężnej drodze stoją kanistry z benzyną. Istnieje samochód o znanym zużyciu paliwa i pustym zbiorniku o nieograniczonej pojemności. Dla O( N) operacji, dowiedz się, od którego kanistra zacząć, aby podczas zbierania paliwa przejechać całą drogę i nie zatrzymać się z pustym (lub stwierdzić, że to niemożliwe).

Rozwiązałem 6 problemów - z wyjątkiem całki. To prawda, zmartwiłem się i błędnie rozwiązałem zadania 2 i 3 (przy prawidłowej technice!)

Podczas rozmowy pytali bardziej o sprawy osobiste: dlaczego zdecydowałeś się pójść do szkoły, czy jest Ci ciężko w pracy, czy to w porządku, że wszyscy są młodsi od Ciebie? Wystąpiło czterodniowe opóźnienie w odpowiedzi (w pierwszych dniach okresowo potrząsałem moim e-mailem przez Internet, gdy mój partner się odwracał). I w końcu odpowiedzieli.

Pozytywne wrażenia z przyjęcia. Zapamiętałem siebie jako wojownika. Kupiłem w końcu e-czytnik (z urządzeniem się nie rozstaję, zakup trafiony).

Negatywne doświadczenia. Powinienem się uspokoić, wtedy zadania 2 i 3 by się udały. Nie warto było w ogóle rozwiązywać całki ani poświęcać więcej czasu całkom w przygotowaniu. Wreszcie przygotowanie jako takie było mało przydatne. Wyciągnąłem twierdzenia, przypomniałem sobie, jak uzasadnione jest to czy tamto, ale potrzebny był tylko zapis permutacji.