MathDB

4

Part of 2004 Regional Olympiad - Republic of Srpska

Problems(3)

Regional Olympiad - Republic of Srpska 2004 Grade 9 Problem 4

Source: Regional Olympiad - Republic of Srpska 2004

9/19/2018
Set S={1,2,...,n}S=\{1,2,...,n\} is firstly divided on mm disjoint nonempty subsets, and then on m2m^2 disjoint nonempty subsets. Prove that some mm elements of set SS were after first division in same set, and after the second division were in mm different sets
SetscombinatoricsDivisiondisjointSubset
n-gon and congruences

Source: RS2004

3/20/2005
A convex nn-gon A1A2…AnA_1A_2\dots A_n (n>3)(n>3) is divided into triangles by non-intersecting diagonals. For every vertex the number of sides issuing from it is even, except for the vertices Ai1,Ai2,…,AikA_{i_1},A_{i_2},\dots,A_{i_k}, where 1≤i1<⋯<ik≤n1\leq i_1<\dots<i_k\leq n. Prove that kk is even and n≡i1−i2+⋯+ik−1−ik(mod3)n\equiv i_1-i_2+\dots+i_{k-1}-i_k\pmod3 if k>0k>0 and n\equiv0\pmod3\mbox{ for }k=0. Note that this leads to generalization of one recent Tournament of towns problem about triangulating of square.
modular arithmeticinductioncombinatorics proposedcombinatorics
kings tour and dominoes

Source: RS2004

3/20/2005
An 8×88\times8 chessboard is completely tiled by 2×12\times1 dominoes. Prove that there exist a king's tour of that chessboard such that every cell of the board is visited exactly once and such that king goes domino by domino, i.e. if king moves to the first cell of a domino, it must move to another cell in the next move. (King doesn't have to come back to the initial cell. King is an usual chess piece.)
combinatorics proposedcombinatorics