All Questions
32
questions
1
vote
1
answer
182
views
Total number of distinct possible marks for given number of questions and marks (ZIO 2023 Q1)
Q. There is an exam with N problems. For each problem, a participant can either choose
to answer the problem, or skip the problem. If the participant chooses to answer the
problem and gets it correct, ...
- 11
1
vote
0
answers
48
views
Squared multiplicty minimization in multiple set choosing problem
The problem is the IOI 2007 competition's Sails problem. It has also appeared in Pranav A. Sriram Olympiad Combinatorics notes (Chapter 1 Exercise 14). I copied the problem description from Pranav. ...
- 11
1
vote
0
answers
95
views
Building a primitive programming language for solving math olympiad problem(TSTST 2015)
There was a 6th problem on USA TSTST 2015:
A Nim-style game is defined as follows. Two positive integers $k$ and
$n$ are specified, along with a finite set $S$ of $k$-tuples of
integers (not ...
- 61
2
votes
1
answer
139
views
HMMT 2014 #9, how many times has Lucky performed the procedure when there are 20 tails-up coins?
There is a heads up coin on every integer of the number line. Lucky is initially standing on the zero
point of the number line facing in the positive direction. Lucky performs the following procedure: ...
- 2,031
1
vote
1
answer
142
views
Sum of Product of Min, which is related to the Pentagonal number theorem.
The title looks a little bit weird. The problem comes from the Atcoder Beginner Contest 279-Ex: Sum of Prod of Min:
Problem: You are given positive integers $n$ and $m$. Here, it is guaranteed that $n ...
- 1,008
1
vote
1
answer
94
views
Repainting of chessboard with restrictions
Assume an $8\times 8$ chessboard with the usual coloring. You may
repaint all squares (a) of a row or column (b) of a $2\times 2$
square. The goal is to attain one black square. Can you reach the
...
- 17k
2
votes
0
answers
34
views
Astronomer watching planets in a solar system
There is exactly one astronomer on every planet of a certain system. He watches the closest planet. The number of the planets is odd and all of the distances are different. Prove that there one planet ...
- 162
2
votes
0
answers
166
views
Greedy algorithm minimizes the sum
There are $n$ positive numbers (not necessarily distinct). In every step, we
can select two numbers and replace each of it with the sum of the two
numbers. Prove that in any amount of steps, selecting ...
- 1,909
0
votes
1
answer
56
views
Number of ways of traversing a graph through all of its nodes?
A lift has $N$ stops ($1,2,3,4,...,N$), hence have $N(N-1)$ distinct rides of travelling from floor $A$ to floor $B$ such that $A\neq B$. How many arrangements of these rides form a continuous trip ...
- 51
1
vote
1
answer
770
views
Sorting an array using reverse
I ran into an Olympiad question recently, and one challenging question surprised me:
We have an array $A$ with $n$ elements. $\operatorname{Rev}(i, j)$ for $1 \leq i < j \leq n$ reverses subarray $...
15
votes
3
answers
946
views
Partition 100 people, 4 from each country into 4 groups with conditions
This is a problem from the $2005$ All-Russian Olympiad. Problem is as follows:
$100$ people from $25$ countries, four from each country, sit in a circle.
Prove that one may partition them onto $4$ ...
- 381
1
vote
1
answer
87
views
An optimization problem to find the consecutive day subset with maximum value - ZIO $2006$, P$1$
Hello everybody! The above problem is a combinatorics problem I got wrong. :( This is ZIO $2006$, P$1$.
For the first part, I got as answer: $3$ which is wrong. What I did to try my value which I ...
- 779
2
votes
1
answer
105
views
determine the least number of rounds that needs to be played so that every child is satisfied
A group of N children, who are numbered 1, 2, . . . , N, want to play hide and seek. In a single round of hide and seek, there will one seeker, and N −1 hiders. Children like to hide and not seek and ...
- 49
0
votes
2
answers
113
views
ways of expressing T as the sum of four elements of S. [closed]
In this task you will give a sequence of numbers $S$ of length $N$. Every element
will be greater than or equal to 1. We write $S[i]$ to refer to the $i$-th element of the
sequence. For example $S = (...
- 49
0
votes
1
answer
149
views
the number of 1’s in it is at least as much as the number of 0’s
You are given a list of $0$’s and $1$’s: $B[1]$, $B[2]$, . . . , $B[N]$. A sublist of this list is
any contiguous segment of elements—i.e., $A[i]$, $A[i + 1]$, . . . , $A[j]$, for some $i$ and $j$.
A ...
- 49
5
votes
1
answer
163
views
Minimal number of questions to identify a subset
This is a curiosity question.
Recently I stumbled across the following problem :
Given three integers $k,m, n$ such that $m+k\leq n$. A friend chooses a subset $S\subseteq\lbrace1,\ldots,N\rbrace$...
- 13.8k
22
votes
6
answers
539
views
Proving surjectivity of some map from a power set to a subset of integers.
We assign to every element $i$ from $N=\{1,2,...,n\}$ a positive integer $a_i$. Suppose $$a_1+a_2+...+a_n = 2n-2$$ then prove that map $T: \mathcal{P}(N) \to \{1,2,...,2n-2\}$ defined with $$T(X) = \...
- 90.7k
9
votes
3
answers
535
views
What is the largest possible number of moves that can be taken to color the whole grid?
Consider a $10\times 10$ grid. On every move, we color $4$ unit squares that lie in the intersection of some two rows and two columns. A move is allowed if at least one of the $4$ squares is ...
- 90.7k
2
votes
2
answers
223
views
Greedy algorithm in matching students to juries that they like with an upper bound number of students each jury can check
Recently I solved this following problem using greedy algorithm.
There are $100$ students who participate at exam.Also there are $25$ members of jury.Each student is checked by one jury.Known that ...
- 4,102
1
vote
1
answer
1k
views
Sum over all contiguous partitions of an array
Consider an array $A$ of length $n$. We can split $A$ into contiguous segments called pieces and store them as another array $B$ . For example , if $A = [1,2,3]$, we have the following arrays of ...
- 13
1
vote
1
answer
283
views
Showing there exists a sequence that majorizes another
The exact quantity of gas needed for a car to complete a single loop around a track is distrubuted among $n$ containers placed along the track. Show that there exists a point from which the car can ...
- 1,408
5
votes
1
answer
2k
views
Match off points into $N$ red/blue pairs with straight lines connecting pairs, so that none of lines we draw intersect
Suppose we are given $2N$ points in the plane (we may assume that no $3$ are collinear). Assume that $N$ of these points are colored red, and $N$ points are colored blue. Can we match off the points ...
user268197
7
votes
2
answers
3k
views
Given $2n$ points in the plane, prove we can connect them with $n$ nonintersecting segments
Given $2n$ points in the plane such that no three points lie on one line. Prove that it is possible to draw $n$ segments such that each segment connects a pair of these points and no two segments ...
- 1,408
4
votes
2
answers
1k
views
Algorithm to uniquely determine a number using two adjacent digits
(Russia)
Arutyun and Amayak perform a magic trick as follows. A spectator writes down on a board a sequence of $N$ (decimal) digits. Amayak covers two adjacent digits by a black disc. Then Arutyun ...
- 3,914
1
vote
1
answer
2k
views
Making all row sums and column sums non-negative by a sequence of moves
Real numbers are written on an $m\times n$ board. At each step, you are allowed to change the sign of every number of a row or of a column. Prove that by a sequence of such steps, you can always make ...
- 3,914
2
votes
1
answer
133
views
Find different sequences of game to find winner
Alice and Bob are having a racing competition to see who is the best runner. They don't want to decide this in a single race, so they choose a number N which is the minimum number of points one of ...
- 272
1
vote
1
answer
342
views
Count ways to distribute candies
N students sit in a line, and each of them must be given at least one candy. Teacher wants to distribute the candies in such a way that the product of the number of candies any two adjacent students ...
- 272
0
votes
1
answer
1k
views
Minimum number of moves to equalize a list
Given a list of $n$ integers. In one move we can either decrease exactly one element by $1,2$ or $5$. What is the minimum number of moves required to equalize the list?
For example: If the list is $2,...
- 1
1
vote
1
answer
377
views
No of labeled trees with n nodes such that certain pairs of labels are not adjacent.
What is the number of trees possible with $n$ nodes where the $i$th and $(i+1)$th node are not adjacent to each other for $i \in \left[0,n-1\right)$ and $$i/2 = (i+1)/2.$$
(integer division) (nodes ...
- 21
4
votes
1
answer
893
views
Card Shuffling [SPOJ]
The original question is posted on SPOJ, and included below:
Here is an algorithm for shuffling N cards:
1) The cards are divided into K equal piles, where K is a factor of N.
2) The ...
- 183
4
votes
6
answers
5k
views
Finding the Heavy Coin by weighing twice
Suppose you have $100$ coins. $96$ of them are heavy and $4$ of them are light. Nothing is known regarding the proportion of their weights. You want to find at least one genuine (heavy) coin. You are ...
anonymous
6
votes
5
answers
2k
views
Least wasteful use of stamps to achieve a given postage
You have sheets of $42$-cent stamps and
$29$-cent stamps, but you need at least
$\$3.20$ to mail a package. What is the
least amount you can make with the $42$-
and $29$-cent stamps that is ...
- 36.6k