Distinguishing cases, find the number of ordered triplets (x, y, z) of positive integers such that Let be the number of such triplets for n. We can get a first recursive formula by noticing that if and then . From this we deduce that as one can easily check that the cases where at least […]
Category: Combinatorics
Seemingly Difficult, But Not Really
There are 12 red balls, 15 white balls and 17 black balls in a box. A person extracts all the balls, one at a time. What’s the probability that all the red balls will be extracted before the white balls and that all the white balls will be extracted before the black balls? There are […]
Quarantine And Bijections
Now the majority of Italy is in lockdown again. So, why not spend some time doing combinatorics. Today’s subject is bashing sums without having to do any calculation. Let’s say we have this sum: One way to do it would be differentiating , then multiplying the result by x and differentiating again. Then we get […]
Problem 7, Combinatorics
I proposed this problem in the last mathematical competition hosted on the Italian ‘gasmatematica’ website. The numbers from 000 to 999 must be put into some boxes, numbered from 00 to 99. If the label of a box is equal to a number with one digit removed, then the number can be put in that […]
An Application Of Burnside’s Lemma
Burnside’s Lemma is a very nice tool I had the occasion to use in the Mathematical Olympiads to solve some Combinatorics problems. It says that, given a finite group acting on a set , and, for each : let be the elements of invariant by . Then the number of orbits is equal to: May […]
A Constructive Combinatorics Proof
There is a positive integer in each square of a rectangular table. In each move, you may double each number in a row or subtract 1 from each number in a column. Can you arrive to a situation where there are only zeros on the table? How Should These Kind Of Problems Be Approached In […]
A Problem From Stanford Mathematics Tournament 2008 (Team Test)
Daphne is in a maze of tunnels shown below. She enters at A, and at each intersection, chooses a direction randomly (including possibly turning around). Once Daphne reaches an exit, she will not return into the tunnels. What is the probability that she will exit at A? The Idea At first, I will denote by […]
Combinatorial Extremization
The best combinatorics book I’ve read so far is ‘Combinatorial Extremization’, by Yuefeng Feng. The book is divided into 13 chapters. Each of them covers a particular combinatorial technique you can use to solve your problems. Some of them are easy to understand, but in general, the level of difficulty of this book is quite […]
Old Problem With Generating Functions
A similar problem to this one is the one that initiated me to the art of using the generating functions, I’ll tell you a version which has less calculations to make. If you roll a complete set of DnD dice, in how many ways can you obtain 13 as sum of their results? Just for […]
A Very Notorious Problem, But In 3D
I’ve already made an article on the 2D version of this problem, if you want to check it out before this one, you can visit https://www.mattiagiuri.com/2020/04/21/a-very-notorious-problem/. Now, the 3D version says: if you have 3 reals x, y, z chosen randomly between 0 and 1, what’s the probability that It’s important to notice that any […]