TITTLE: Mathematics on the chessboard AUTHOR: Jiří Šperl DEPARTMENT: The Department of mathematics and the teaching of mathematics SUPERVISOR: RNDr. Antonín Jančařík, Ph.D. ABSTRACT: The main subject of my thesis is mathematical problems on the chessboard using chess pieces. The work aims to demonstrate how a secondary school student would approach and solve several typical mathematical tasks of this nature. Consequently, it outlines ways to incorporate chessboard mathematical problems and exercises in mathematical classes. Moreover, the thesis includes a compact collection of solved problems on the chessboard that can serve as an inspiring source of unconventional mathematical tasks in conventional mathematical education. My own mathematical research forms a major part of the thesis. The research was conducted as a series of tests in three school classes. In order to achieve a high de- gree of objectivity classes of students with different specializations were selected to take part in the tests. The participating classes were also of different age groups. The theoretical part of the thesis takes a look at the past of the subject and presents several interesting historical problems concerning the mathematics on the chess- board. Last but not least, the thesis contains a discussion of solutions of the...

Many complicated problems have simple or at least understandable version, which can be pleasant to listen to and to think about. This work presents the reader with an interesting problem about hats, which, as it turns out, surprises with a number of variations, diversity of procedures and unexpected results. Work will (hopefully) serve as entertaining mathematical literature for anyone who wants to look at these problems, or as a good source of logical problems of this kind. The first part is therefore written in a relaxed language and style, problems are set in one (perhaps overly fairy-tale) story. Mathematics hidden behind problem solving is presented in the second part. 1

The topic of this diploma thesis is the edge distance labeling problem with specified parametres p, q and λ. We found a dychotomy for p = 2 and q = 1. So the problem is polynomial if λ ≤ 4 and it is NP-complete for λ > 4. The boundary is shifted by one prior to the vertex distance labeling problem, which has already been solved. Polynomial cases are characterized as some special paths and cycles with a few additional vertices. To show NP-completeness we use a well-known NP-complete problem of Monotone not all equal 3-SAT. That section has four parts: One for odd λ, one for even λ and two more reductions for λ = 5 and λ = 6. 1

We give an overview of recent progress in the research of hypergraph jumps -- a problem from extremal combinatorics. The number $\alpha \in [0, 1)$ is a jump for $r$ if for any $\epsilon > 0$ and any integer $m \ge r$ any $r$-graph with $N > N(\epsilon, m)$ vertices and at least $(\alpha + \epsilon) {N \choose r}$ edges contains a subgraph with $m$ vertices and at least $(\alpha + c) {m \choose r}$ edges, where $c := c(\alpha)$ does depend only on $\alpha$. Baber and Talbot \cite{Baber} recently gave first examples of jumps for $r = 3$ in the interval $[2/9, 1)$. Their result uses the framework of flag algebras \cite{Raz07} and involves solving a semidefinite optimization problem. A software implementation of their method is a part of this work.

In this thesis, we study hash functions. We focus mainly on the famous Merkle-Damg˚ard construction and its generalisation. We show that even this generalised construction is not resistant to multicollision attacks. Combinatorics on words plays a fundamental role in the construction of our attack. We prove that regularities unavoidably appear in long words with bounded number of symbol occurences. We present our original results concerning regularities in long words. We lower some earlier published estimates, thus reducing the comlexity of the attack. Our results show that generalised iterated hash functions are interesting rather from the theoretical than practical point of view. 1

Darbe tiriamas kėlinių, derinių, poaibių ir Grėjaus kodų generavimo algoritmų sudėtingumas. Atliekama algoritmų analizė. Tyrimo tikslams sukurta programa realizuojanti minėtus algoritmus. / The complexity research of permutations, combinations, subsets and Gray codes generating algorithms is provided in this paper. Algorithms are analyzed and implemented in the application developed for research purposes.

Disertacijoje nagrinėjamos aritmetinės prigimties aibių, tokių kaip sumų aibė, poaibių sumų aibė ar Sidon aibė, savybės bei aritmetinę struktūrą atspindintys dydžiai, tokie kaip adityvioji energija ar maksimali reprezentacinės funkcijos reikšmė. Disertacijos mokslinė problema yra šių aibių, tenkinančių ekstremalias kombinatorine prasme sąlygas, egzistavimo, dydžio ir struktūros nustatymas. / In the dissertation various phenomena and concepts of arithmetic nature, such as sumsets, additive energy and Sidon sets are investigated. The main problem of the dissertation is finding extremal (in the combinatorial sense) sets, their size and structure.

Disertacijoje nagrinėjamos aritmetinės prigimties aibių, tokių kaip sumų aibė, poaibių sumų aibė ar Sidon aibė, savybės bei aritmetinę struktūrą atspindintys dydžiai, tokie kaip adityvioji energija ar maksimali reprezentacinės funkcijos reikšmė. Disertacijos mokslinė problema yra šių aibių, tenkinančių ekstremalias kombinatorine prasme sąlygas, egzistavimo, dydžio ir struktūros nustatymas. / In the dissertation various phenomena and concepts of arithmetic nature, such as sumsets, additive energy and Sidon sets are investigated. The main problem of the dissertation is finding extremal (in the combinatorial sense) sets, their size and structure.

The purpose of the dissertation is to prove universal tight bounds for deviation from the mean probability inequalities for functions of random variables. Universal bounds shows that they are uniform with respect to some class of distributions and quantity of variables and other parameters. The bounds are called tight, if we can construct a sequence of random variables, such that the upper bounds are achieved. Such inequalities are useful for example in insurance mathematics, for constructing effective algorithms. We extend the results for Lipschitz functions on general probability metric spaces. / Disertacijos darbo tikslas – įrodyti universalias tiksliąsias nelygybes atsitiktinių dydžių funkcijų nukrypimo nuo vidurkio tikimybėms. Universalios nelygybės pažymi, kad jos yra tolygios pagal tam tikras bendras skirstinių klases ir pagal atsitiktinių dydžių kiekį, kartais ir pagal kitus parametrus. Nelygybės vadinamos tiksliosiomis, jeigu pavyksta sukonstruoti atsitiktinių dydžių seką, kuriai nelygybės virsta lygybėmis. Tokios nelygybės labai naudingos, pavyzdžiui, draudimo matematikoje, konstruojant efektyvius algoritmus. Disertaciją sudaro šeši skyriai. Pirmasis skyrius yra įvadas, kuriame neformaliai pristatomas disertacijoje tiriamas objektas, pateikiamas bendras darbo aprašymas ir motyvacija. Detalesnė kitų autorių rezultatų apžvalga pateikiama atskirai kiekviename skyriuje. Antrasis skyrius skirtas atvejui, kai atsitiktiniai dydžiai yra aprėžti ir simetriniai. Trečiajame skyriuje įrodomos nelygybės atsitiktiniams dydžiams, tenkinantiems dispersijos aprėžtumo sąlygą. Ketvirtajame skyriuje nagrinėjamos sąlyginai aprėžtų atsitiktinių dydžių sumos. Penktajame skyriuje tiriamos atsitiktinių dydžių sekos, sudarančios martingalą arba supermartingalą, ir joms gaunamos universaliosios tikimybinės nelygybės ir sukonstruojama nehomogeninė Markovo grandinė, kuri yra martingalas, ir kuriai minėtos nelygybės virsta lygybėmis. Šeštajame skyriuje rezultatai yra apibendrinami atsitiktinių dydžių sekos Lipšico funkcijoms.

Disertacijos darbo tikslas – įrodyti universalias tiksliąsias nelygybes atsitiktinių dydžių funkcijų nukrypimo nuo vidurkio tikimybėms. Universalios nelygybės pažymi, kad jos yra tolygios pagal tam tikras bendras skirstinių klases ir pagal atsitiktinių dydžių kiekį, kartais ir pagal kitus parametrus. Nelygybės vadinamos tiksliosiomis, jeigu pavyksta sukonstruoti atsitiktinių dydžių seką, kuriai nelygybės virsta lygybėmis. Tokios nelygybės labai naudingos, pavyzdžiui, draudimo matematikoje, konstruojant efektyvius algoritmus. Disertaciją sudaro šeši skyriai. Pirmasis skyrius yra įvadas, kuriame neformaliai pristatomas disertacijoje tiriamas objektas, pateikiamas bendras darbo aprašymas ir motyvacija. Detalesnė kitų autorių rezultatų apžvalga pateikiama atskirai kiekviename skyriuje. Antrasis skyrius skirtas atvejui, kai atsitiktiniai dydžiai yra aprėžti ir simetriniai. Trečiajame skyriuje įrodomos nelygybės atsitiktiniams dydžiams, tenkinantiems dispersijos aprėžtumo sąlygą. Ketvirtajame skyriuje nagrinėjamos sąlyginai aprėžtų atsitiktinių dydžių sumos. Penktajame skyriuje tiriamos atsitiktinių dydžių sekos, sudarančios martingalą arba supermartingalą, ir joms gaunamos universaliosios tikimybinės nelygybės ir sukonstruojama nehomogeninė Markovo grandinė, kuri yra martingalas, ir kuriai minėtos nelygybės virsta lygybėmis. Šeštajame skyriuje rezultatai yra apibendrinami atsitiktinių dydžių sekos Lipšico funkcijoms. / The purpose of the dissertation is to prove universal tight bounds for deviation from the mean probability inequalities for functions of random variables. Universal bounds shows that they are uniform with respect to some class of distributions and quantity of variables and other parameters. The bounds are called tight, if we can construct a sequence of random variables, such that the upper bounds are achieved. Such inequalities are useful for example in insurance mathematics, for constructing effective algorithms. We extend the results for Lipschitz functions on general probability metric spaces.