# My unsolved problems

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 partitons

Given 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 polyhedra

A 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 sums

Find 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 maxima

Let $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 grids

Generalize 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. Note by Kerry Soderdahl
4 years, 6 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

I 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:

 1 2 3 4 5 1 1 2 1 4 6 1 6 16 22 1 8 30 68 90 

Since there doesn't seem to be any closed formula written there, it's safe to say there's no closed formula known yet.

- 4 years, 6 months ago

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

- 4 years, 6 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 }$.

Staff - 4 years, 6 months ago

Great list of questions! Let me know what progress you are making.

Staff - 4 years, 6 months ago