I don't think I'm smart enough to solve any of these problems in the near future. I'd be very interested if anybody happens to know how to solve these.

1) Picky partitonsGiven a set \(A\) and a family \(\mathcal{F}\) of subsets of \(A\) such that every set in \(\mathcal{F}\) contains more than one element, consider a partition of \(A\) such that no set in \(\mathcal{F}\) is a subset of any of the pieces of the partition of \(A\). How many of these partitions are possible, and what is the minimum cardinality of these partitions?

2) Rolling polyhedraA polyhedron is placed onto a plane. The polyhedron will repeatedly roll over along one of the edges of the face against the plane. The edge is chosen before each roll randomly (independently and uniformly). After \(n\) rolls, what is the probability that it will rest on the same face that it started on? (Also, what is the probability it will return to its original position?)

I don't think this problem has a general solution, however I solved it for regular tetrahedra, cubes, octahedra and dodecahedra, and I suspect that there is a reasonably simple solution for all uniform polyhedra.

3) Partial combination sumsFind a formula for \(\displaystyle S(x,y)=\sum_{k=0}^{\frac{x}{y}}\binom{x}{ky}\), where \(y|x\).

If I'm not mistaken, these should be correct: \[S(n,1)=2^n\] \[S(n,2)=2^{n-1}\] \[S(n,3)=\sum_{k=1}^{\lfloor\frac{n}{2}\rfloor}2^{n-2k}\]

The third result was from this problem.

I worked on this several weeks ago. I lost the details, but I remember coming up with a (probably incorrect) result that was something like this:

\[S(n,b)\stackrel{?}{=}\sum_{k=1}^{\lfloor\frac{n}{2}\rfloor}2^{n-2k}a_i\] where \(a_i\) is the \(i^\text{th}\) coefficient of the generating function \(\displaystyle\frac{x}{F_b(x)}\), where \(F_b(x)\) is a Fibonacci polynomial.

4) Partition maximaLet \(J_a(m,k)\) be the number of ways to partition \(k\) into ordered \(a\)-tuples such that the maximum of the tuples is \(m\). Find a formula for \(J_a(m,k)\).

This is as far as I got:

\[J_2(m,k)=\begin{cases} 2 &\mbox{if } m \leq k < 2m \\ 1 &\mbox{if } k=2m \\ 0 &\mbox{otherwise} \end{cases}\]

\[J_3(m,k)=\begin{cases} 3(k-m+1) &\mbox{if } m \leq k < 2m \\ 3(3m-k) &\mbox{if } 2m \leq k < 3m \\ 1 &\mbox{if } k=3m \\ 0 &\mbox{otherwise} \end{cases}\]

5) Some bigger gridsGeneralize this problem for all such rectangular grids.

Define \(F(a,b)\) as the number of paths from the top-left corner to position \((a,b)\), where \((0,0)\) is the top-left corner and \((m,n)\) is the bottom-right corner \((m\) is the horizontal position starting from the left, \(n\) is the vertical position starting from the top). Define \(F(0,0)=1\), and \(F(c,d)=0\) for any point \((c,d)\) outside of the grid.

We can easily derive the recurrence relation \(F(a,b)=F(a,b-1)+F(a-1,b)+F(a-1,b+1)\). It is possible to write this as a system of \(m+1\) first-order linear recurrences, which can collapse into a \((m+1)^{\text{th}}\)-order linear recurrence so that \(F(a,0)\) is defined in terms of \(F(a-1,0), F(a-2,0), F(a-3,0), \ldots , F(a-(m+1),0)\).

I couldn't figure out how to come to this final recurrence except by lots of tedious substitutions within the system of recurrences. If I do find the final recurrence, the only way I know how to find an explicit formula is by factoring a \((m+1)^{\text{th}}\)-degree polynomial, which poses obvious problems for \(m\ge 4\).

Pardon the poor explanation. Hopefully this is somewhat comprehensible.

## Comments

Sort by:

TopNewestI don't have any idea for Question 1 yet.

The first part of Question 2 is solvable by a Markov chain. The second part depends heavily on the polyhedron, but in most cases I believe it's just "what's the probability that the second half of the journey is the perfect reverse of the first". It's when things are symmetrical and "good" that said second problem is interesting.

Question 3 is solvable by using complex numbers and binomial theorem. Let \(\omega = e^{2\pi i/y}\); consider \(\sum_{k=0}^{y-1} (1 + \omega^k)^x\).

It's easy to solve Question 4 by Principle of Inclusion-Exclusion for any \(a,m,k\): number of partitions of \(k\) to \(a\) nonnegative integers, minus those where at least one of them is greater than \(m\), plus those where at least two of them are greater than \(m\), minus those where at least three of them are greater than \(m\), and so on.

Question 5 is this when you shift the columns down:

Since there doesn't seem to be any closed formula written there, it's safe to say there's no closed formula known yet. – Ivan Koswara · 1 year, 5 months ago

Log in to reply

Great list of questions! Let me know what progress you are making. – Calvin Lin Staff · 1 year, 5 months ago

Log in to reply

For question 3, I am getting

\[S\left(a,b\right)=\frac{1}{b}\sum _{m=1}^b\left(1+w^m\right)^a\]

Where \(w=e^{2i \pi /5}\)

I'll update you if I find a better closed form – Julian Poon · 1 year, 5 months ago

Log in to reply

– Calvin Lin Staff · 1 year, 5 months ago

Yup, that's essentially it. You could do slightly better with some trigonometric substitutions and applying Euler's theorem, so that you can get a closed form for it in terms of \( \cos , \sin \frac{ k \pi } { n } \).Log in to reply