1
vote
1answer
24 views

Recurrence relation and combinatorics

I am reading p.4 of the article http://mercercountymathcircle.files.wordpress.com/2014/03/recurrence_relations.pdf which consider the following problem: Find the units digit of ...
9
votes
1answer
89 views

Blocking lines of length $5$ in a $7 \times 8$ matrix; how can we know the solutions have a specific form?

A friend shared with me the following puzzle he encountered in a Chinese math competition: In a $7 \times 8$ matrix, we place tokens so that any straight line of length $5$ (horizontal, vertical, ...
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
2answers
29 views

Find value of $n$ with given conditions

The 4-digit positive number $n$'s digit sum is $20$. The sum of the first two digits is $11$, the sum of the first and the last digit as well. The first digit is the last digit $+3$. What is the ...
0
votes
0answers
179 views

Distributing cards among players

Moderator Note: This is a current contest question on codechef.com. N players sit around a round table. There are $n \cdot m$ cards with unique numbers of range $1\ldots n\cdot m$. Each player ...
2
votes
0answers
41 views

Number of queries required to find the function.

this is a slight variation to question $3$ of the Nordic mathematical olympiad of 2010.(in short that one deals with bijections and this one deals with any kind of function).We have 2010 buttons and ...
3
votes
0answers
58 views

A function on sets which is constant for all permutations

Let $U=\{1, 2,\ldots, 2014\}$. For positive integers $a$, $b$, $c$ we denote by $f(a, b, c)$ the number of ordered 6-tuples of sets $(X_1,X_2,X_3,Y_1,Y_2,Y_3)$ satisfying the following conditions: ...
3
votes
1answer
42 views

A bijection defined on the set of configuration of lamps

Consider $n$ lamps clockwise numbered from $1$ to $n$ on a circle. Let $\xi$ to be a configuration where $0 \le \ell \le n$ random lamps are turned on. A cool procedure consists in perform, ...
1
vote
5answers
55 views

Possible arrangements of marbles in bags?

I've come across a question on a math test asking, "How many different ways can you put a dozen identical marbles into six bags so that each bag has atleat one marble in it?". I would imagine that ...
2
votes
1answer
72 views

Ratio of sum in black and white squares

For even positive integer $n$ we put all numbers $1,2,...,n^2$ into the squares of an $n\times n$ chessboard (each number appears once and only once). Let $S_1$ be the sum of the numbers put in the ...
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
233 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
31 views

Existence of sets with four common elements among 16000 sets.

In the Duma there are $1600$ delegates, who have formed $16000$ committees of $80$ persons each. Prove that one can find two committees having no fewer than four common members. Source: All-Russian ...
2
votes
2answers
91 views

Number of non-decreasing sequences

How do I find the number of non-decreasing sequences of length $N$, such that all number in the sequences lie in the range $[a, b]$. Also, the frequency of the most frequently occurring element should ...
4
votes
2answers
419 views

simple games with cute winning strategies?

Im thinking of games of two players ($A$ goes first and $B$ second) like the following: There are 35 chips in a table, during each turn a player can remove 1,2,3 or 4 chips. Prove player $B$ can ...
0
votes
1answer
32 views

Complex Combinatorics Hexagon/Triangle Contest Problem

The problem is as follows: The six sides of convex hexagon $A_1A_2A_3A_4 A_5A_6 $ are colored red. Each of the diagonals of the hexagon is colored either red or blue. Compute the number of colorings ...
2
votes
1answer
68 views

Prove that a sequence of $11$ numbers always contains six numbers summing up to a multiple of $6$.

Prove that a sequence of $11$ numbers always contains six numbers summing up to a multiple of $6$. This is a problem from a selection to IMO 2014. I like thinking about this problem, it is ...
1
vote
2answers
67 views

From any list of $131$ positive integers with prime factor at most $41$, $4$ can always be chosen such that their product is a perfect square

Author's note:I don't want the whole answer,but a guide as to how I should think about this problem. BdMO 2010 In a set of $131$ natural numbers, no number has a prime factor greater than 42. ...
-1
votes
1answer
93 views

2014 USAMO Problem :with Points Collinear iff Sum is Constant

Prove that there exists an infinite set of points $$ \dots, \; P_{-3}, \; P_{-2},\; P_{-1},\; P_0,\; P_1,\; P_2,\; P_3,\; \dots $$ in the plane with the following property: For any three distinct ...
1
vote
1answer
43 views

How many different right triangles are possible with the shorter side of odd length?

I was trying to solve this problem but unable to figure it out completely. I thing number of was odd integer $n$ can be the side of right triangle is number of factor of $\frac{n^2}{2}$. Can some one ...
4
votes
1answer
50 views

Lines covering points on napkin

Suppose we place a $100\times 100$ napkin on an infinite lattice plane. What is the minimum number of lines that can always cover all the lattice points lying inside or on the border of the napkin, no ...
0
votes
1answer
21 views

Bound the Number of Acute-angled Triangles

I encounter the following problem with solution. But I do not quite understand the argument for 5, 10 points and eventually 100 points. Can someone elucidate the details? Problem In a plane there ...
1
vote
1answer
63 views

How many zeros does this expression end in?

How many zeroes does $$\frac{50!}{2^95^5}$$ end in?
1
vote
1answer
53 views

a spider has 1 sock and 1 shoe for each leg. then find out the the total possibilities.

a spider has one sock and one shoe for each of its 8 legs.in how many different orders can the spider put on its shocks and shoes; assuming that on each leg ;the shock must be put on before the shoe? ...
0
votes
3answers
83 views

$1-x+x^2-x^3+. . .-x^{17}=a_0+a_1y+a_2y^2+. . .+a_{17}y^{17},y=x+1$

This is a previous AIME question. $1-x+x^2-x^3+. . .-x^{17}=a_0+a_1y+a_2y^2+. . .+a_{17}y^{17},y=x+1$. Then what is $a_{17}$? Is anything wrong with the following method? $1-x+x^2-x^3+. . ...
3
votes
2answers
144 views

Find the number of series

Find the number of series $(a_1,..., a_{2n})$ that have terms from ${\{0,...9\}}$ so that: $$ 11|\sum_{i=1}^{n}a_i-\sum_{i=n+1}^{2n}a_i $$ (this is not a homework) There is a similar problem ...
10
votes
1answer
109 views

Question concerning finite intersecting sets

Let $\{X_i\}_{i=1}^{\infty}$, $\{Y_j\}_{j=1}^{\infty}$ be finite sets of cardinality at most $n$. If for any finite $F$, there are $i,j \in \mathbb{N}$ such that $F \cap X_i \cap Y_j = \emptyset$, ...
2
votes
4answers
68 views

determining the amount of total questions needed in a game given the probabilty

I'm creating a game and can't seem to quite figure this out - driving me crazy. There are 8 questions in my game You can play the game an unlimited amount of times the test bank doesn't change. so ...
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 ...
1
vote
2answers
137 views

A counting problem using Burnside's lemma

Suppose we have 12 objects (say, 6 indistinguishable black ones and 6 indistinguishable white ones). How many seatings at a round table can we form from them? The answer is $80$, but how could this ...
4
votes
1answer
129 views

If one eats $100$ chocolates in $58$ days,then he must be eating exactly 15 chocolates in some consecutive days

BdMO 2014 Nationals $X$ eats 100 chocolates in 58 days,eating at least 1 chocolate per day.Prove that,in some consecutive days,she ate exactly 15 chocolates. I tried using the pigeonhole ...
1
vote
0answers
242 views

Finding the number of arrangement of N people of different height such that K of them are visible from front

Moderator Note: This is a current contest question on codechef.com. [Initially, I had asked this question in stackoverflow, but someone suggested to post it here, and hence this question is ...
2
votes
1answer
48 views

AIME 1986:different sequences of coin tosses

AIME 1986 Problem-13 In a sequence of coin tosses, one can keep a record of instances in which a tail is immediately followed by a head, a head is immediately followed by a head, and etc. We ...
1
vote
1answer
63 views

Choosing $2n-1$ points from $n\times n$ grid such that $3$ points always form a right triangle

NOTE: Looking for a hint,not the whole solution. BdMO 2012 Nationals Secondary Consider a $n×n$ grid of points. Prove that no matter how we choose $2n-1$ points from these, there will always ...
0
votes
2answers
62 views

Choosing people around a circular table

There are 20 people around a circular table.We have to choose $3$ of them such that at least $2$ of them are sitting together.In how many ways can this be done? Number of ways of choosing 3 people ...
5
votes
1answer
167 views

Sequence where the sum of digits of all numbers is 7

BdMO 2014 We define a sequence starting with $a_1=7,a_2=16,\ldots,\,$ such that the sum of digits of all numbers of the sequence is $7$ and if $m>n$,then $a_m>a_n$ i.e. all such numbers are ...
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 ...
1
vote
1answer
31 views

Compute number of points having same property

I have been given a cuboid which has either green or red color for each point (integer coordinates) in it. I am also given another cuboid whose lower left corner is (x1, y1, z1) and upper right corner ...
1
vote
2answers
105 views

$7$ points inside a circle at equal distances

BdMO 2014 There are $7$ points on a circle.Any 2 consecutive points are at equal distance from one another.How many acute angled triangles can you form taking any 3 of these points? I believe ...
1
vote
0answers
44 views

Separating points on a plane

BdMO 2011 There are $25$ points on a plane, no three of which lie on a line. Find the minimum number of lines needed to separate them from one another. Can we assume that the points lie on a ...
1
vote
1answer
63 views

Arranging red and blue tiles in a line with at least 1 blue tile between any 2 red tiles

BdMO 2010 Nationals: Tom and Jerry have $8$ blue tiles and $6$ red tiles.They want to arrange them in a straight line so that between any $2$ red tiles there is always at least $1$ blue tile.In ...
1
vote
1answer
61 views

math contest ranking problem?

A math contest is held among 4 middle schools. Each school enters a team of 3 students. The 12 contestants are ranked from 1 (best performance) to 12 (worst performance). The team that has the overall ...
4
votes
2answers
123 views

Cute coloring problem on a board

Suppose we color an $n\times n$ square board using $n$ colors exactly $n$ times each. Prove that there is either a column or a row containing at least $\lceil \sqrt n \rceil$ different colors. A ...
7
votes
1answer
122 views

South Africa National Olympiad 2000 (Tile 4xn rectangle using 2x1 tiles)

Let $A_n$ be the number of ways to tile a $4×n$ rectangle using $2×1$ tiles. Prove that $A_n$ is divisible by 2 if and only if $A_n$ is divisible by 3. My attempt: Define basic shapes A, B and C, ...
2
votes
1answer
76 views

How to prove $\binom{2n}{n}\frac{1}{n+1} = \prod \limits_{i = 2}^n \frac{2i-1}{i+1} $?

How to prove this closed form involving Catalan numbers? $$\binom{2n}{n}\frac{1}{n+1} = \prod \limits_{i = 2}^n \frac{2 \times (2i-1)}{i+1} $$ I have seen this being used here. Not sure how to derive ...
8
votes
3answers
284 views

A problem with 26 distinct positive integers

I am trying to solve the following problem. Assume that we are given 26 distinct positive integers. Show that either there exist 6 of them $x_1<x_2<x_3<x_4<x_5<x_6$, with $x_1$ ...
2
votes
1answer
64 views

Travelling to the point of origin without using the same road twice

BdMO 2013 Secondary: There are $n$ cities in a country. Between any two cities there is at most one road. Suppose that the total number of roads is $n$. Prove that there is a city such that ...
7
votes
1answer
202 views

Korean Math Olympiad (Construct rectangle)

Prove that an $m$ × $n$ rectangle can be constructed using copies of the following shape if and only if $mn$ is a multiple of 8 where $m$ > 1 and $n$ > 1. My solution: starting from 2 × 4 and 3 × 8 ...
12
votes
2answers
481 views

If 1 boy knows r girls and 1 girl knows r boys ,then number of boys=girls

Yet another question from BdMO 2013 Nationals: In a class,every boy knows $r$ number of girls and every girl knows $r$ number of boys.Show that there are equal number of boys and girls[Assume that ...
2
votes
0answers
93 views

Rearranging numbered cards to reverse their order

I have been thinking about this question for a long time, but I can't solve it. Here is the question: We have $9$ cards, with numbers one to nine written on them (in the order $1, 2, \ldots , 9$). ...