7
votes
1answer
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 ...
3
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
15
votes
2answers
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 ...
2
votes
1answer
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 ...
3
votes
1answer
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 ...
0
votes
1answer
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 ...
2
votes
2answers
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, ...
1
vote
1answer
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.
9
votes
1answer
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 ...
3
votes
3answers
593 views

Graph theory resource for mathematical Olympiads

I would like to learn a bit of Graph theory for mathematical Olympiads.Can anyone please point out a resource from where I can learn it? Here's my background: I have limited knowledge of linear ...
10
votes
2answers
617 views

Seating friends around a dinner table

This problem came from a Putnam problem solving seminar. If each person in a group of n people is a friend of at least half the people in the group, then show that it is possible to seat the n ...