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 AA and a family F\mathcal{F} of subsets of AA such that every set in F\mathcal{F} contains more than one element, consider a partition of AA such that no set in F\mathcal{F} is a subset of any of the pieces of the partition of AA. 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 nn 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 S(x,y)=k=0xy(xky)\displaystyle S(x,y)=\sum_{k=0}^{\frac{x}{y}}\binom{x}{ky}, where yxy|x.

If I'm not mistaken, these should be correct: S(n,1)=2nS(n,1)=2^n S(n,2)=2n1S(n,2)=2^{n-1} S(n,3)=k=1n22n2kS(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)=?k=1n22n2kaiS(n,b)\stackrel{?}{=}\sum_{k=1}^{\lfloor\frac{n}{2}\rfloor}2^{n-2k}a_i where aia_i is the ithi^\text{th} coefficient of the generating function xFb(x)\displaystyle\frac{x}{F_b(x)}, where Fb(x)F_b(x) is a Fibonacci polynomial.

4) Partition maxima

Let Ja(m,k)J_a(m,k) be the number of ways to partition kk into ordered aa-tuples such that the maximum of the tuples is mm. Find a formula for Ja(m,k)J_a(m,k).

This is as far as I got:

J2(m,k)={2if mk<2m1if k=2m0otherwiseJ_2(m,k)=\begin{cases} 2 &\mbox{if } m \leq k < 2m \\ 1 &\mbox{if } k=2m \\ 0 &\mbox{otherwise} \end{cases}

J3(m,k)={3(km+1)if mk<2m3(3mk)if 2mk<3m1if k=3m0otherwiseJ_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)F(a,b) as the number of paths from the top-left corner to position (a,b)(a,b), where (0,0)(0,0) is the top-left corner and (m,n)(m,n) is the bottom-right corner (m(m is the horizontal position starting from the left, nn is the vertical position starting from the top). Define F(0,0)=1F(0,0)=1, and F(c,d)=0F(c,d)=0 for any point (c,d)(c,d) outside of the grid.

We can easily derive the recurrence relation F(a,b)=F(a,b1)+F(a1,b)+F(a1,b+1)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+1m+1 first-order linear recurrences, which can collapse into a (m+1)th(m+1)^{\text{th}}-order linear recurrence so that F(a,0)F(a,0) is defined in terms of F(a1,0),F(a2,0),F(a3,0),,F(a(m+1),0)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)th(m+1)^{\text{th}}-degree polynomial, which poses obvious problems for m4m\ge 4.

Pardon the poor explanation. Hopefully this is somewhat comprehensible.

Note by Kerry Soderdahl
5 years, 3 months ago

No vote yet
1 vote

  Easy Math Editor

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.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 1

paragraph 2

paragraph 1

paragraph 2

[example link]( 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×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}


Sort by:

Top Newest

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 ω=e2πi/y\omega = e^{2\pi i/y}; consider k=0y1(1+ωk)x\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,ka,m,k: number of partitions of kk to aa nonnegative integers, minus those where at least one of them is greater than mm, plus those where at least two of them are greater than mm, minus those where at least three of them are greater than mm, and so on.

Question 5 is this when you shift the columns down:

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.

Ivan Koswara - 5 years, 3 months ago

Log in to reply

For question 3, I am getting

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

Where w=e2iπ/5w=e^{2i \pi /5}

I'll update you if I find a better closed form

Julian Poon - 5 years, 3 months ago

Log in to reply

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,sinkπn \cos , \sin \frac{ k \pi } { n } .

Calvin Lin Staff - 5 years, 3 months ago

Log in to reply

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

Calvin Lin Staff - 5 years, 3 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...