Tagged Questions

80 views

The rows continue to be different to each other

In each position of an $n \times n$ matrix there is a number. We know that all the rows of the matrix are different from each other. Show that we can delete a column so that the rows of the matrix ...
84 views

A graph on the cities of a country

In some country several pairs of cities are connected by direct two-way flights. It is possible to go from any city to any other by a sequence of flights. The distance between two cities is ...
40 views

Partition Graph Challenging Question

I want to find in which of the following Graph, the edges cannot partitioned to triangles? Km,n,r means 3-Partite Complete Graph with m, n, and r sections. a) K7 b) K12 c) K3,3,3 d) K5,5,5 i ...
66 views

Cutting a chessboard into domino pieces!

A friend of mine gave me this problem from a european olympiad: Suppose we have a $8\times8$ chessboard. Each edge has a number; the number of ways of dividing this chessboard into $1\times2$ and ...
232 views

A game on a graph

Alice and Bob play a game on a complete graph ${G}$ with $2014$ vertices. They take moves in turn with Alice beginning. At each move Alice directs one undirected edge of $G$. At each move Bob chooses ...
41 views

Relabelling players in a tournament

BdMO 2014 $n$ players take part in a chess tournament where each player plays with all others only once and the only outcomes of the games are win and loss.Prove that it is possible,after the ...
192 views

The library with 999 books.

In the town of Capibara there is a library with books in 999 themes. Since Capibara is an international town they have books in various languages. We know that for every language we can find exactly ...
100 views

In a party with 2000 persons, determine # of people who know everyone

In a party with 2000 persons, among any set of four there is at least one person who knows each of the other three. There are three people who are not mutually acquainted with each other. How many ...
128 views

Checkers on a Chessboard

Given 2k pieces on a k by k chessboard, prove that there is always a sequence of pieces $K_1, K_2 \ldots K_{2n}$ such that $K_1$ and $K_2$ are in the same row, $K_2$ and $K_3$ are in the same column, ...
75 views

Graph theory problem with friends

There are 9 people and for every 3 people, 2 of them are mutual friends. Please show that there exist 4 people out of the 9 who are all mutual friends.
247 views

(Olympiad) Minimum number of pairs of friends.

I gave up, my approaches didn't work (induction, pigeon-hole, parity; though obviously there's a good chance I didn't use them cleverly): In a group of 12 people, every pair of them has a common ...