All Questions
8
questions
0
votes
0
answers
48
views
Optimal Strategy for Identifying Lighter Balls: A Balance Scale Puzzle
There are n balls, among which m balls are lighter (and equally light with each other). We have a balance scale; how many times must we weigh at least, in order to find these m lighter balls? We ...
2
votes
0
answers
104
views
Number of three-tuples such that $c_1a_1 + c_2a_2 + c_3a_3 = n$ and $c_1 \ge c_2 \ge c_3$
I'm trying to figure out how to find the number of three tuples that sum up to $n$ when each element has a weight of $c_i$. In other words, how many combinations are there of $(a_1, a_2, a_3)$ such ...
- 141
1
vote
2
answers
177
views
proof of diamond lemma
I am trying to prove the diamond lemma: Suppose we have two elementary cancellations of a word
$w$
then there exists some $w'$ such that there are (possibly trivial) cancellations
The diamond lemma,
...
- 39
0
votes
1
answer
320
views
The walking ants problem expansion.
Preface
The following problem, I suppose, most of you have read in recreational math quiz books. It is stated as following:
On a stick, there are $4n+1$ ants, with $2n$ ants at one pole of the stick ...
- 1,288
1
vote
2
answers
139
views
Transforming a combinatorics question to a binary system question.
Preface
This is a quite interesting question that I have come across some earlier years in my Olympiad training. Due to my bad memories and notebook record, I failed to trace back where I found this ...
- 1,288
4
votes
1
answer
659
views
Algorithm for Generating Well-Formed Formulas in Polish Notation
I am trying to write an algorithm that constructs only well-formed formulas in PN. I have some list of symbols for binary connectives, unary connectives, and propositional variables (trying to make ...
- 117
0
votes
1
answer
47
views
The approximability of different NP-hard problems
I'm fairly new to the topic Computational Complexity and had the following question (I therefore apologies before hand for any poorly stated terminology).
Suppose i have two optimization problems $A$...
- 1,146
20
votes
3
answers
1k
views
Finding the Robot [closed]
There are five boxes in a row. There is robot in any one of these five boxes. Every morning I can open and check a box (one only). In the night, the robot moves to an adjacent box. It is compulsory ...
- 827