% Pólya--Szegő feladatsor, Zsbán Ambrus

% deklarációk --------------------------------------------------

\documentclass[a4paper,10pt]{article}
\usepackage[latin2]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[magyar]{babel}
\pagestyle{empty}
\usepackage{amsmath}

\count1 0
\def\feladat{\global\advance\count1 1\bigskip\indent{\bf\the\count1. }}

\newenvironment{header}%
	{\begin{center}\bfseries}%
	{\end{center}\bigskip}

% fejléc -------------------------------------------------------------

\begin{document}

\begin{header}

Pólya--Szegő szeminárium 4.

5. feladatsor, javított változat

% LC_TIME=hu_HU date "+%Y. %B %e."
2005. október 17.

\end{header}


\feladat 
Bizonyítsuk be, hogy egy összefüggő gráfnak van olyan csúcsa, amit elhagyva összefüggő marad. Mutassuk meg azt is, hogy legalább két ilyen csúcs van, és mutassunk olyan gráfot, aminek pontosan két ilyen csúcsa van.

\feladat
Legyenek a $G$ gráf csúcsai az $n$ hosszú $0-1$-sorozatok, és két csúcs között akkor fut él, ha a sorozatok pontosan egy jegyben térnek el. (Ez az $n$-dimenziós egységkocka.) Milyen $n$-ekre van $G$-nek Hamilton-köre?


% fibonacci gcd -----------------------------------------------------------
% ambrus

\feladat
Egy szabályos hatoldalú kockával (minden oldal valószínűsége $1/6$) addig dobálunk, amíg ki nem jön egymás után 6 különböző szám (tehát pl. 14135246-nál megállunk 8 dobás után). Számítsuk ki a dobásaink számának várható értékét.



% Gauss-féle binom együtthatók mint polinomok együtthatói -----------------------------------
% ambrus

\feladat
Egy futballmérkőzésen $ n $ ember egyszerre a levegőbe hajítja a
kalapját, majd néhány másodperccel később mindenki elkap egyet.
Ettől a kalapok véletlenszerűen megkeverednek.

Lássuk be, hogy annak a valószínűsége, hogy pontosan $ k $ ember
kapja vissza a saját kalapját,
$$
\sum_{0\le l\le n-k} (-1)^l \frac{1}{k!\,l!}
$$

Hová tart ez a valószínűség, ha $ k = 0 $ és $ n \to \infty $?


%\newcommand{\Ginom}[3]{\genfrac{[}{]}{}{}{#1}{#2}_{#3}}

\feladat
Adottak a (nem feltétlenül különböző)
$ x_0, \dots, x_n; y_0, \dots, y_n $ valós számok.
Bizonyítandó, hogy ezek egyértelműen meghatározzák a legfeljebb
$ n $-edfokú $ P $ polinomot, ha
$$
P^{(k)}(x_k) = y_k
$$
teljesül minden $ k \leq n$-re.



\feladat
$x,y \in \{1,2,\dots, k\}^n$-re legyen $x>y$, ha $x$ minden jegye legalább akkora, mint $y$ megfelelő jegye, és legalább egy helyen szigorúan nagyobb (így definiáltunk egy részbenrendezést). Legfeljebb hány elem választható ki $\{1,2,\dots, k\}^n$-ből úgy, hogy ne legyen köztük kettő, melyek közül az egyik nagyobb, mint a másik?

\end{document}
