<commit_before>---
layout: page
permalink: /2020/egzamin/1/
---

## 2020 Egzamin - Pierwszy termin

### Zadanie 1

<div>
W jednym kroku <em>spaceru po kracie</em> \(\mathbb{Z}^2\) z punktu \((x,y)\)
możemy przejść do \((x \pm 1, y)\) lub \((x, y \pm 1)\). Znajdź zwarty wzór na
liczbę spacerów złożonych z \(n\) kroków, które zaczynają się i kończą w punkcie
\((0,0)\).
</div>

<div data-collapse>
  <h4 class="collapsible">Rozwiązanie</h4>
  <div class="solution">
    <p>
      <p>
        Zauważmy, że ciąg złożny z \(L, P, G, D\) jest spacerem wtedy i tylko wtedy, gdy \(\#L\) = \(\#P\) oraz \(\#G\) = \(\#D\). Dzieje się tak, bo żeby zacząć i skończyć w \(0, 0\) potrzebujemy tyle samo skrętów w prawo co lewo itd. 
      </p>
      <p>
        <em>Zliczanie</em>: 
        Wybierzmy połowę miejsc. W wybrane miejsca wstawmy \(L\). Ponownie wybierzmy połowę miejsc (z \(n\) - miejsca z dwóch wyborów mogą się pokrywać). W wybrane miejsca wstawiamy \(P\). Wybór miejsc rozumiemy podług tej tabelki (pierwsze miejsce reprezentuje pierwszy wybór, drugie - analogicznie):
        </p>
        <p>
          \(\_P = P\)
        </p>
        <p>
          \(LP = D\)
        </p>
          \(\_\_ = G\)
        <p>
          \(L\_ = L\)
        </p>

      <p>
        Czyli na przykład: \(n = 4\), pierwszy wybór: \(L\_L\_\). Drugi wybór: \(PP\_\_\). Sumarycznie: \(DPLG\).

        Twierdzę, że takie wybory zliczają spacery.
      </p>

    <p>
      <em>Prawidłowość wyboru</em>:

      \(n\) dowolne, z pierwszego wyboru mamy \(\frac{n}{2}\) \(L\), z drugiego \(\frac{n}{2}\) \(P\). Niech \(x\) to będzie liczba pokrywających się miejsc. Policzmy teraz liczbę poszczególnych kierunków:
      <p>
        \(\#L = \frac{n}{2} - x \) (\(\frac{n}{2}\) było na starcie, zabieramy \(x\), bo tyle się pokrywa)
      </p>

      <p>
        \(\#P = \frac{n}{2} - x\) (Skoro po drugim wyborze \(x\) miejsc się pokrywa, a wybieraliśmy z \(\frac{n}{2}\), to na \(\frac{n}{2} - x \) stoi samo \(P\))
      </p>

      <p>
        \(\#D = x\) (Bo \(x\) się pokrywa)
      </p>

      <p>
        \(\#G = x \)(Bo na \(\frac{n}{2}\) coś stoi z pierwszego wyboru, wiemy, że \(x\) się pokrywa z drugim, czyli z drugiego wyboru mamy \(\frac{n}{2} - x\) nowych miejsc [niepokrywających się z pierwszym wyborem]. Czyli \(\frac{n}{2} + \frac{n}{2} - x \) to liczba miejsc, na którym coś stoi. Odejmujemy od \(n\), żeby otrzymać liczbę miejsc pustych i wychodzi \(x\)).
      </p>

      <p>
        Czyli ten sposób zawsze wybiera prawidłowe spacery.
      </p>

    </p>

    <p>
      <em>Zlicza każdy spacer</em>:

      Niech \(S\) będzie dowolnym spacerem z zadania. \(A, B, C, D\) to odpowiednio zbiory pozycji \(L, P, G, D\) tego spaceru.

      Z pierwszego wyboru niech wszystkie \(L\) padną na pozycję z \(A\). To ustawia wszystkie \(L\) jak trzeba.

      Z drugiego, niech \(\|D\|\) \(P\) padnie na pozycję z \(D\). To ustawia wszystkie \(D\) jak trzeba

      Pozostałe \(P\) z drugiego wybour \((\frac{n}{2} - \|D\|\)) niech padną na puste pozycje. To ustawia \(P\) i zarazem \(G\).
    </p>

    <p>
      <em>Różnowartościowość wyboru</em>:
      Tabelka zdefiniowana na początku pozwala uzyskać dany skręt na dokładnie jeden sposób, więc dwa różne wybory muszą dać różne podziały.
    </p> 

    <p>
      <em> Wzór:  </em>
        <p>
          Dwa razy wybieramy połowę z \(n\): \(\binom{n}{\frac{n}{2}}^2\)<commit_msg>Poprawki<commit_after>---
layout: page
permalink: /2020/egzamin/1/
---

## 2020 Egzamin - Pierwszy termin

### Zadanie 1

<div>
W jednym kroku <em>spaceru po kracie</em> \(\mathbb{Z}^2\) z punktu \((x,y)\)
możemy przejść do \((x \pm 1, y)\) lub \((x, y \pm 1)\). Znajdź zwarty wzór na
liczbę spacerów złożonych z \(n\) kroków, które zaczynają się i kończą w punkcie
\((0,0)\).
</div>

<div data-collapse>
  <h4 class="collapsible">Rozwiązanie</h4>
  <div class="solution">
    <p>
      <p>
        Zauważmy, że ciąg złożny z \(L, P, G, D\) jest spacerem wtedy i tylko wtedy, gdy \(\#L\) = \(\#P\) oraz \(\#G\) = \(\#D\). Dzieje się tak, bo żeby zacząć i skończyć w \((0, 0)\) potrzebujemy tyle samo skrętów w prawo co lewo itd. 
      </p>
      <p>
        <em>Zliczanie</em>: 
        Wybierzmy połowę miejsc. W wybrane miejsca wstawmy \(L\). Ponownie wybierzmy połowę miejsc (z \(n\) - miejsca z dwóch wyborów mogą się pokrywać). W wybrane miejsca wstawiamy \(P\). Wybór miejsc rozumiemy podług tej tabelki (pierwsze miejsce reprezentuje pierwszy wybór, drugie - analogicznie):
        </p>
        <p>
          \(\_P = P\)
        </p>
        <p>
          \(LP = D\)
        </p>
          \(\_\_ = G\)
        <p>
          \(L\_ = L\)
        </p>

      <p>
        Czyli na przykład: \(n = 4\), pierwszy wybór: \(L\_L\_\). Drugi wybór: \(PP\_\_\). Sumarycznie: \(DPLG\).

        Twierdzę, że takie wybory zliczają spacery.
      </p>

    <p>
      <em>Prawidłowość wyboru</em>:

      \(n\) dowolne, z pierwszego wyboru mamy \(\frac{n}{2}\) \(L\), z drugiego \(\frac{n}{2}\) \(P\). Niech \(x\) to będzie liczba pokrywających się miejsc. Policzmy teraz liczbę poszczególnych kierunków:
      <p>
        \(\#L = \frac{n}{2} - x \) (\(\frac{n}{2}\) było na starcie, zabieramy \(x\), bo tyle się pokrywa)
      </p>

      <p>
        \(\#P = \frac{n}{2} - x\) (Skoro po drugim wyborze \(x\) miejsc się pokrywa, a wybieraliśmy z \(\frac{n}{2}\), to na \(\frac{n}{2} - x \) stoi samo \(P\))
      </p>

      <p>
        \(\#D = x\) (Bo \(x\) się pokrywa)
      </p>

      <p>
        \(\#G = x \) (Bo na \(\frac{n}{2}\) coś stoi z pierwszego wyboru, wiemy, że \(x\) się pokrywa z drugim, czyli z drugiego wyboru mamy \(\frac{n}{2} - x\) nowych miejsc [niepokrywających się z pierwszym wyborem]. Czyli \(\frac{n}{2} + \frac{n}{2} - x \) to liczba miejsc, na którym coś stoi. Odejmujemy od \(n\), żeby otrzymać liczbę miejsc pustych i wychodzi \(x\)).
      </p>

      <p>
        Czyli ten sposób zawsze wybiera prawidłowe spacery.
      </p>

    </p>

    <p>
      <em>Zlicza każdy spacer</em>:

      Niech \(S\) będzie dowolnym spacerem z zadania. \(A, B, C, D\) to odpowiednio zbiory pozycji \(L, P, G, D\) tego spaceru.

      Z pierwszego wyboru niech wszystkie \(L\) padną na pozycję z \(A\). To ustawia wszystkie \(L\) jak trzeba.

      Z drugiego, niech \(\|D\|\) \(P\) padnie na pozycję z \(D\). To ustawia wszystkie \(D\) jak trzeba. 

      Pozostałe \(P\) z drugiego wybour \((\frac{n}{2} - \|D\|\)) niech padną na puste pozycje. To ustawia \(P\) i zarazem \(G\).
    </p>

    <p>
      <em>Różnowartościowość wyboru:</em>
      Tabelka zdefiniowana na początku pozwala uzyskać dany skręt na dokładnie jeden sposób, więc dwa różne wybory muszą dać różne podziały.
    </p> 

    <p>
      <em> Wzór:  </em>
        <p>
          Dwa razy wybieramy połowę z \(n\): \(\binom{n}{\frac{n}{2}}^2\)
{'fraction_non_alphanumeric': 0.18196433791289096, 'fraction_numerical': 0.009938614440222157, 'mean_word_length': 2.1275137111517366, 'pattern_counts': {'":': 0, '<': 101, '<?xml version=': 0, '>': 101, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6323504', 'n_tokens_mistral': 3139, 'n_tokens_neox': 3122, 'n_words': 863}