Showing posts with label maximal principle. Show all posts
Showing posts with label maximal principle. Show all posts
Saturday, April 21, 2018
Collinear marbles
From OSP SMA 2018.
On a 200x200 checkerboard, we place red and blue marbles, at most 1 marble per cell. Two marbles are considered "collinear" if they are on the same column or row. For each red marble, there are exactly 5 collinear blue marbles, and for each blue marble, there are exactly 5 collinear red marbles. Find the maximum number of marbles on the board.
Labels:
chebysev,
chess board,
Combinatorics,
maximal principle,
rearrangement
Tuesday, October 10, 2017
symmetric 2 variable function
Suppose $S = \{1,2,\dots,n\}$ and $f: S \times S \to R$ satisfies the following:
$$f(i,j) + f(j,i) = 0 \forall i,j \in S$$
Now for any two number $i,j$, we say that $i$ is superior to $j$ if there exists a $k$ (not necessarily distinct from $i,j$) such that $f(i,k) + f(k,j) \geq 0$.
Show that there exists a number $x \in S$ such that $x$ is superior to all elements of $S$.
Labels:
Algebra,
Combinatorics,
function,
graph,
graph theory,
induction,
maximal principle,
strong induction
Subscribe to:
Posts (Atom)