% 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.

4. feladatsor, javított változat

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

\end{header}


\feladat
Legyenek $a_1, a_2, \dots $ páronként relatív prím összetett számok. Mutassuk meg, hogy

$$ \sum_{n=1}^\infty \frac{1}{a_n}<\infty.$$



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

\feladat
(A feladat hibás.) % http://www.komal.hu/forum/forum.cgi?a=to&tid=7&st=25&dr=0&sp=1297
\newcommand{\lnko}[2]{(#1,#2)}
Legyen $ s_0 = 0 $, $ s_1 $ egész, 
és definiáljuk az $ {s_n} $ sorozatot a következő homogén lineáris rekurzióval:
$ s_{n+2} = A_0 s_{n} + A_1 s_{n+1} $, ahol $ A_0, A_1 $ egészek.
Bizonyítsuk be, hogy minden $ n, k $ egészre 
$$
\lnko{s_n}{s_k} = s_{\lnko nk}
$$
Ahol $ \lnko ab $ jelöli $ a $ és $ b $ legnagyobb közös osztóját.

Fontos speciális eset, ha $ s $ a Fibonacci-számok sorozata, illetve ha
$ s_n = 2^n - 1 $.


\feladat
Vegyünk három egybevágó téglalapot, melyek oldalainak hossza $2$ és $1+\sqrt{5}$
. Helyezzük el őket a térbeli koordinátarendszerben úgy, hogy a középpontja mindnek az origó legyen, az első az $xy$ síkba essen és hosszabbik oldala párhuzamos $x$-szel, a második az $yz$ síkba essen és hosszabbik oldala párhuzamos $y$-nal, a harmadik a $zx$ síkba essen és hosszabbik oldala párhuzamos $z$-vel. Mutassuk meg, hogy a három téglalap 12 csúcsa egy szabályos ikozaéder csúcsai.


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

{
\feladat
%\newcommand{\Ginom}[3]{\genfrac{[}{]}{}{}{#1}{#2}_{#3}}
\newcommand{\Ginom}[3]{G_{#1,#2}(#3)}
Tavaly beláttuk, hogy a 
$$
\Ginom nkq = 
    \frac{1 - q^n}{1 - q} \cdot \frac{1 - q^{n-1}}{1 - q^2} \cdots 
        \frac{1 - q^{n-k+1}}{1 - q^k}
$$
Gauss-féle binomiális együtthatók $ q $ polinomjai,
és teljesítik a következő rekurziót:
$$
\Ginom {n + 1}kq = \Ginom nkq + \Ginom n{k - 1}q q^{n-k+1}
$$

Vegyünk most fel a négyzetrácson egy $ k $ magas, és $ n - k $ széles téglalapot.
Tekintsük a $ k $ felfelé és $ n - k $ jobbra menő szakaszból álló
utakat a téglalap bal alsó csúcsából a jobb felső csúcsába. 
Jelölje $ c_{n,k,\alpha} $ 
ezen utak közül azoknak a számát, 
amelyek alatt a téglalapban $ \alpha $ egységnyi terület van.

Lássuk be, hogy
$$
\Ginom nkq = \sum_{0\le \alpha\le k(n-k)} c_{n,k,\alpha}\, q^\alpha
$$

}

\feladat
Bizonyítsuk be, hogy minden háromszögmentes gráf beágyazható részgráfként egy elég nagy Myczielski-gráfba. (Ez utóbbiak a következő módon származnak: $M_2$ egy két csúcsú gráf a két csúcs között éllel; $M_{n+1}$-et úgy képezzük, hogy felvesszük $M_n$ egy példányát, annak minden $v_i$ csúcsához egy új $u_i$ csúcsot, melyet összekötünk $v_i$ szomszédaival (de $v_i$-vel nem), végül felveszünk egy $w$ csúcsot, melyet összekötünk az összes $u_i$-vel.)



% nemneg trig. polinomok -------------------------------------------------------
% ambrus
% (megint)

\feladat
Legyen 
$$ 
g(\vartheta) = \lambda_0 + \lambda_1 \cos\vartheta + \mu_1 \cos\vartheta + \dots +
    \lambda_n \cos(n\vartheta) + \mu_n \sin(n\vartheta)
$$
valós trigonometrikus polinom ($ \lambda_k, \mu_k $ valósak).

Lássuk be, hogy ha $ 0 \le g(\vartheta) $ minden valós $ \vartheta $-ra, 
akkor felírható
$$
    g(\vartheta) = |h(e^{i\vartheta})|^2 
$$ 
alakban, valamely $ n $-edfokú $ h $ valós polinomra.



\end{document}
