It appears the Discord link I included in the video has expired. If you'd like to join, try this one instead: discord.gg/smuxnzZ5Zf. I've tried to set the link to never expire. Hopefully it works! Also, as @patdbus has pointed out in the comments, at 15:02 the green 3 and 4 on the right of the bottom strip and the left of the top strip should be swapped.
Tiling together shapes is a shockingly clever way to represent a Convolution, which is at the heart of what rolling two dice is about. The creativity to come up with this and apply it though is indeed absolutely genius.
@@Quargos yeah these solution are like, i well i mean its convolution/generating function so blah blah not surprising but to come up with these in the first place, no chance lol, I was confident in my way of generating function until I saw it involves complex numbers lol
I am irresistibly beaming at seeing my solution explained so clearly. When I saw my crappy tile drawings in your video I got unreasonably happy. It reminded me of my love for problem solving! PurpleMind, you have a fantastic ability at making things clear to anyone. I endeavor to learn from you and I look forward to your next video.
Be proud. I am awestruck by the creativity of your solution. This was a problem about probability, and potentially a problem about the factorizations of characteristic polynomials by looking at them over the complex numbers. You viewed the problem from precisely the right angle; you found the magical viewpoint through which the problem becomes completely visual, completely tangible, and damn near trivial when viewed from the vantage point you found. I aspire to reach the level of mathematical creativity you displayed here.
I was really amazed by the simplicity of the polynominal distribution solution... then the next guy just drew coloured shapes and completely smashed it
The fact that someone submitted an algorithm written (is it written? I guess not quite) in Scratch is honestly a massive chad move. Big respect, whoever you are Rose. Big respect. EDIT: oh wow. That last approach. Actually so creative and fun. I love it, one of the best math videos I've seen in a while!
That last method cements this video in my collection of the best maths videos on UA-cam. This is actually such an amazing idea for a video series, I imagine this channel will blow up eventually.
This was fun to be a part of. I remember how satisfying it was to find the different arrangements of the polynomial factors and getting 3 different solutions when I was only expecting 1. Really cool to see all of these approaches and how people expanded on the problem.
I was one of the submitters who proved the extended pattern, but the final solution is simply magical. It's so clear and illuminating and elegant. Well done
This video and video series are phenomenal. That final solution is actually amazing. I was happy to be a part of this video, keep doing what you're doing!
4:45 proud to be a member of team Refined Brute Force. I used a few different optimizations and was able to calculate 20 sided dice in a matter of minutes. But I enjoyed seeing the grid, tiling and polynomial answers, those feel like true solutions to this puzzle! It was great to see this come together.
Brute Force will always, eventually, find THE solution if one exists. But, alas, time = money, and thus Brute Force is often least fiscally responsible choice.
And THIS is why having diversity of thoughts is important holy crap. So many unique solutions, so many different scopes, challenges, and advantages posed by them. Just wow.
A simple way to minimise the total number of possible die combinations is by realising that if the distribution of the sum of 2 dies with n faces is the same as the normal distribution for 2 dies with n faces from 1 to n, then if you add all the faces of the 2 dies you will get the same sum as the sum of all faces of the 2 normal dies. This is because the average value for rolling will be the same since the distributions are equal and also the number of possibilities is the same, n^2 since all dies have the same number kf faces. In a 4 sided die the sum of all faces is 10 and doubling that gives 20, so it is only required to check combinations where the sum of all faces is exactly equal to 20, no less no more. Adding the restriction that the 2 dies must have at least 1 face containing the number 1 to get a 2 decreases the total number of possible combinations significantly. This can be used for any n sided dies, for a 6 sided die the sum should be 42, for a 8 sided die the sum should be 72, for a 12 sided die the sum shoyld be 156 and fianlly for a D20 the sym should be 420. The general formula for the sum is n*(n+1) for a n sided die. This should make the variables more dependent of each other and allow brute force algorithms to work on larger values.
I'm blown away by the creativity of the solution your viewers, makes you wonder how far can I progress in my ability to solve math problems. Is there an expectation for when the third episode is going to be posted? Can't wait to try it! It was so nice to see myself at the end credits, maybe some day my method will be discussed in the video itself.
Thanks so much! I'm not quite sure about the third episode right now. I may be making some other content first. Glad you enjoyed, and there's a high chance that your submission would be included in a future episode if you submit again -- I try to cover as many individuals as possible.
Electrical Engineer here. I pretty much took the same approach as the algebraic abstraction, and I'd like to share my way of thinking about it! We could create a sequence P[n], that states how many times the number n appears in any given cube. In a regular 6 sided dice, the sequence (starting with 0) is [0, 1, 1, 1, 1, 1, 1, 0, 0, ...] And the sequence corresponding to a pair of dice is calculated by the convolution operation (P*P)[n]. The convolution could also be described as a multiplications of the Z-transforms of the 2 sequences (similar to how a convolution of two functions in the time domain is equivalent to a multiplication of their laplace transforms). So all we need is to find two polynomials that multiply to the right polynimial
This may be one of the most fun math videos I have ever seen and the first time I have subscribed to a channel after seeing just one video. Great job. Love seeing the creativity of your community, and you present all of the topics here wonderfully
This is an awesome series! I also found the 1223 and 122334 pattern, then manually used it in the same way shown in the video to find solutions for 8, 10, and 12 before writing a python script to automate it. Totally will keep up with this! Also, the tiling solution was genius. That’s the sort of thinking that solves unsolved problems
I just randomly stumbled across this video, but I actually played around with this problem last year for a school project! I love these dice. I knew them as 'Sicherman Dice'. At the time I used the polynomial method using the cyclotomic polynomial thing to find the factors. I probably didnt have the most efficient solution, but it did work pretty well.
Going with the two 4-sided dice, you can speed up the process by elimination. One, and only one, of each dice's faces must be 1, because 1 + 1 = 2. That drops the possible outcomes to 7^6. Two of the faces across the remaining six must be 2, because either 1 + 2 and 2 + 1 or 1 + 2 and 1 + 2 = 3. That gives us 2 * 7^4 left to check. Still a bit of work, but far less daunting. We pick the one version that less like normal. 1 2 2 A 1 B C D But 7 can't be one of the numbers on the second die anymore, because 2 + 7 = 9 and two 4-sided regular dice only go up to 8. So, B, C, and D can not be 7. A can't be 1 or 2, so the lowest is 3, and that knocks out 6 for B, C, and D. We plug in and try. 1 2 2 3 1 B C D D then has to be 5: 1 2 2 3 1 B C 5 This solves 1 distribution of 2, 2 distributions of 3, 1 of 4, 1 of 6, 2 of 7 and 1 of 8. Meaning we need: Two more fours. Four fives. Two sixes. Try two 3s 1 2 2 3 1 3 3 5 2 3 3 4 4 5 5 6 4 5 5 6 6 7 7 8 The same principle can be had to find "alternative fair dice" for other sizes, but it would be a longer process. For 6 sided dice: 1 A B C D E 1 F G H I J 1 2 2 3 3 4 1 F G H I 8 2, 3, 3, 4, 4, 5, 9, 10, 10, 11, 11, 12 for far. Leaving us with one 4, three 5s, one 10, three 9s, and a full distribution in the middle.\ 1 2 2 3 3 4 1 3 G H I 8 This eliminates 4s, leaving one 5, three 6s, five 7s, five 8s, three 9s, one 10 1 2 2 3 3 4 1 3 G H 6 8 This eliminates 10s, and leaves one 5, three 6s, four 7s, three 8s, one 9. Leaving an obvious answer: 1 2 2 3 3 4 1 3 4 5 6 8 2, 3, 3, 4, 4, 5, 4, 5, 5, 6, 6, 7, 5, 6, 6, 7, 7, 8, 6, 7, 7, 8, 8, 9, 7, 8, 8, 9, 9, 10, 9, 10, 10, 11, 11, 12 And theoretically, a fair 8 sided dice set would be: 1 2 2 3 3 4 4 5 1 3 5 5 7 7 9 11
This was really lovely Between the problem itself, the presentation (and animation), viewer interaction, crediting, and the multiple different ideas thereof. Excited to see more of it
what an amazing video, i didn’t know what i was expecting when i clicked this video but the result was so much better. the creativity and how you displayed the solutions was amazing
the tiling solution is conceptually the same as a convolution. If we extend the problem a bit by making the dice complex and the dice continuous instead of discrete, you can do a bit of spectral witchcraft. Treat the target distribution as the magnitude of the frequency spectrum, and take the inverse discrete Fourier transform assuming the imaginary component in all cases is zero. Because the convolution of two signals in the frequency domain is equivalent to multiplying in the time domain, you can take your time series representation of the spectrum and divide it by whatever signal X that has nonzero terms, and by definition the frequency spectrum of the output Y convolved with the spectrum of X will be the target spectrum. It's a fair bit easier than the discrete case
A few observations could definitely cut down on the search space. I consider these to be self evident. A: There must always be exactly 1 "1" on each die. B: The highest number of both dice must be unique, and must sum to 2N. C: The order of numbers on a die does not matter D: The order of dice does not matter E: The total number of pips is equal to twice the sum of pips on a single "regular" die. Which is equal to (N² + N) pips for both dice. (even if the pips are represented as a number) From this corrolaries: The highest number on a die cannot be a 1. Therefore the highest number any die can have is 2N - 2. There are N-1 combinations of the maximum dice (2 through N). Exceeding N would reverse the dice order, which is unnecessary. There are N² - 3N - 2 pips to be assigned to the middle numbers on both dice. Each middle number must be inbetween 2 and 2N-1. 2*(N-2)*2 pips are locked into each middle number as it is at least 2. There are (N² - 7N + 6) pips free to distribute among 2n - 4 numbers. For a 8 sided die, there are 7 possible sets of maximum numbers and 14 pips to freely distribute among 12 middle numbers.
i used the ifft method and found a solution almost immediately but didn't send you my work because i wanted to make it more rigorous but time escaped me
Thought: the probability distribution for the sum of two variables drawn independently from two given probability distributions, is the convolution of those two distributions. If we take the Fourier transform of the target distribution, we need the Fourier transforms of the two distributions to multiply pointwise to the one of the target. Given the distribution for one of the dice, we can divide the Fourier transform of the target by the Fourier transform of the given one. If this involves any division of something non-zero by zero, the given one won’t work. Uhh… But then we have to somehow put in the “but we only have (e.g.) 8 equally likely sides on each of the dice” aspect to it… Maybe this isn’t a good approach… Edit: 7:15 : oh cool, it is a reasonable solution 11:26 : very nice! Giving all the solutions all at once!
4:20 Similarly, you can restrict the biggest numbers on the dice to add to 2n where n is the number of faces and not repeat, which would immediately restrict the numbers on one die to be strictly between 1 and n, which limits the possibilities for that die by a lot
The shape-filling method makes it obvious that dice with a prime number of sides can't have other solutions! How can you possibly hope to fill the big parallelogram with copies of a smaller shape, if the width of one row is prime? Other than the trivial solution, you don't!
Very interesting video, of which I'm quite surprised with the inverse FFT solution. I'd also check where dice can roll a '0' or even where single dice can roll negative numbers, because life isn't always positive, either. With a pen and paper exercise, it shows the results are exactly the same, at least for sets in with all dice in set A are increased by the value the dice in set B are decreased. Apparently this is also true for non integer values. They have to be all the same, though. E.g. A = (-4.5, -3.5, -2.5, -1.5, -0.5, 0.5) and B = (6.5, 7.5, 8.5, 9.5, 10.5, 11.5)
In general, if you add k to all the faces of die 1 and subtract k from all the faces of die 2, you'll get the same distribution because if D1 + D2 is the sum of the regular dice, the new sum is (D1 + k) + (D2 - k) = D1 + D2.
when factoring x+x²+x³+x⁴+x⁵+x⁶+x⁷+x⁸ you left a factor of 1+x⁴ which can be factored further into (1+√2x+x²)(1-√2x+x²). although you do have to get the two of them together, you can't necessarily know that unless finding them and proving so.
I can’t remember if this was stated in the video, but the highest face on each die cannot be a duplicate face. In addition, the highest face on each die must together add to the highest value of the distribution. And the highest face on each die must be no less than 3 under the highest value of the distribution Using the 2d4 as an example, the highest value is 8 so we can separate it into 2 pairs of dice to check, each having 4 faces filled in. We only have to check these two: 1xx5 & 1yy3 where 1
When you started showing the tile solution, i immediately thought about Convolutions. Wonder if those are applicable here, i am pretty sure they should be. Anyway, great video.
I never got around to e-mailing it, but there’s a pretty computationally cheap way to find it for dice with 2n sides. One die will of course follow the simple green die pattern, but the other die’s faces are each calculated with a simple 2-variable equation. I never got around to proving that it works (which is why I never sent it), but I tested it up to d1000 and it did
When I saw that tiling solution at the end I swore the words "conditional convolution" popped into my head. Honestly I don't think I have the rigor to go on with that tangent. while(stack is not invalid and not complete){ while (curr_index is not full{ drop stack at curr index} increment curr index} How you would mangle a convolution like that into mathematical notation is beyond me.
This was fun to try and solve, but I am now a bit disappointed that I didn't seem to get as far as some others. I calculated all the valid dice pairs for dice up to 200 sides, but it looks like another viewer, mark got to 300 (shown here: 12:23). What method did they use? I now wonder if there is a faster, more optimized method, or if they just spent more time on calculating it. I wonder how far this can be taken, and how good a solver can get. I've always gotten an exponential time complexity, or at least, it grows exponentially with the number of factors the polynomial has, but maybe that's just a result of the method.
Two things: 1. I believe Mark mentioned that he indeed took a very long time to compute his answers. 2. I'm not exactly sure how your solution works, but keep in mind that the polynomials we're trying to factor are special, not arbitrary polynomials (that is, they are x + x^2 + x^3 + ... + x^n). You may find this wikipedia page useful if you haven't seen it already: en.wikipedia.org/wiki/Cyclotomic_polynomial
I only watched the intro but I would probably use the same method from a paper I saw about find other pairs of dice that roll the same as a pair of a normal 6D by using polynomials.
I guess the last solution explains why there are no alternate solutions for prime numbers - you cannot split a prime-length base into multiple equally long parts. Of course what I would love to see is a proof that all solutions are representable as tilings.
Yeah, that would be cool. Not exactly sure how you would go about it (or if it's even true). It's clear that tilings represent solutions; but the other implication, not so much.
I thought this video was about finding a combination of dice that would allow you to have the same probability for each number. That would be useful for games.
Ted actually had a method involving a spreadsheet with the 6 sided trick dice, but that involved one of the dice having a lower max number. Here's the video if anyone is interested: ua-cam.com/video/urOkfsIRFlw/v-deo.html
When I first heard the problem I misunderstood two things: -all probabilities are the same -it's the same dice And then I proved that impossible for the four sided dice😂😅
Great video! I do have one question though, why are we ruling out dice with 0 as a possible sude value? Is it just because percentile dice typically use this as 10? I would think there could me a few more solutions, especially interesting solutions this wau
Good question -- the decision to allow 0 or not is essentially arbitrary. You get some cool results if you do include it (as you have mentioned), and you get some cool results if you don't. In particular, when you don't allow 0, the connection to prime numbers becomes more apparent, as otherwise every value of n (including prime values) would permit at least one alternate solution -- just subtract one from each face on the first die and add one to each face on the second.
First of all, it would be disingenuous to pretend that I came up with it. I knew about this technique already from other combinatorial problems. And anyway, the solution you see in the video was submitted by a viewer (@Polyamathematics on UA-cam -- who, by the way, makes fantastic videos!!). But how would one come up with this without prior knowledge? That's a tricky question. It's hard to pinpoint where a piece of mathematical insight get's its inspiration. But one thing for sure is that experience with a wide range of existing mathematical concepts can help prime your brain to think of a new connection. For example, if you had been working with polynomials and perhaps multiplying them together, you might more easily see a resemblance between that process and the probability distribution generated by rolling dice.
If you are familiar with generating functions and/or taken a combinatorics class then the idea of associating x^n with a corresponding possible choice value n would be likely something you would try after a bit of thinking
detail, but still. The patterns at 15:35 should be 1234 and 3456 rather than 1233 and 4456 - those are the columns they occupy and make this solution so simple and elegant..
I think this is a somewhat limited viewpoint. While it's true that there are some people who have a better inherent ability to do math, the extreme cases of this are very rare and most of what seems like natural facility can often be attributed to experience and dedication! I'd say if you work hard at growing your understanding, it's likely that in a year or two of learning you could find yourself looking back and viewing the others here as peers rather than superiors.
Good question! Firstly, note what I said in the pinned comment -- I made a mistake in my labeling of the faces on the green die for the third tiling example. But here's how it works: the faces on the green die are determined by the tile that we're using to fill up the overall shape. We start with a 1 in the bottom-left corner of the tile, and then each subsequent column gets the next integer (2, 3, 4, etc.) If a column is skipped then there is no green face with the number that would appear in that column. For the faces on the blue die, we need to look at how the eight copies of the tile fit together to fill up the target shape. The blue face for a particular copy of the tile is the column number of the leftmost part of the tile. For instance, in the first tiling example, the leftmost part of the tile with a blue face of 1 is in column 1, and the leftmost part of the tiles with a blue face of 5 are in column 5. Why this works should hopefully become clearer if you go and rewatch that section of the video. I think you should find it more intuitive after thinking about it for a little while :)
Isn't the last solution a sort of visual representation of inverse convolution/cross-correlation and as such a visual representation of the inverse FFT of a sort? Just interested if the two are basically the same
It appears the Discord link I included in the video has expired. If you'd like to join, try this one instead: discord.gg/smuxnzZ5Zf. I've tried to set the link to never expire. Hopefully it works!
Also, as @patdbus has pointed out in the comments, at 15:02 the green 3 and 4 on the right of the bottom strip and the left of the top strip should be swapped.
That tiling solution is so creative, I'm in awe. Looking forward to the next problem, hopefully I'll be a bit more inspired this time.
Glad you enjoyed! Thanks for watching.
Tiling together shapes is a shockingly clever way to represent a Convolution, which is at the heart of what rolling two dice is about. The creativity to come up with this and apply it though is indeed absolutely genius.
@@Quargos yeah these solution are like, i well i mean its convolution/generating function so blah blah not surprising but to come up with these in the first place, no chance lol, I was confident in my way of generating function until I saw it involves complex numbers lol
I am irresistibly beaming at seeing my solution explained so clearly. When I saw my crappy tile drawings in your video I got unreasonably happy. It reminded me of my love for problem solving!
PurpleMind, you have a fantastic ability at making things clear to anyone. I endeavor to learn from you and I look forward to your next video.
Thanks for the contribution! I had a lot of fun animating it.
I mean, turning a probability problem into a shape filling puzzle is a stroke of genius
Be proud. I am awestruck by the creativity of your solution. This was a problem about probability, and potentially a problem about the factorizations of characteristic polynomials by looking at them over the complex numbers. You viewed the problem from precisely the right angle; you found the magical viewpoint through which the problem becomes completely visual, completely tangible, and damn near trivial when viewed from the vantage point you found. I aspire to reach the level of mathematical creativity you displayed here.
Seriously, that approach was nothing short of genius. Its beauty made me emotional.
Very elegant and simple. Your proof really stood out and I love it
I was really amazed by the simplicity of the polynominal distribution solution... then the next guy just drew coloured shapes and completely smashed it
The fact that someone submitted an algorithm written (is it written? I guess not quite) in Scratch is honestly a massive chad move. Big respect, whoever you are Rose. Big respect. EDIT: oh wow. That last approach. Actually so creative and fun. I love it, one of the best math videos I've seen in a while!
Scratch is underrated :)
YoFeArIr
@@PurpleMindCSI love scratch
hate when people say its for babies
That last method cements this video in my collection of the best maths videos on UA-cam. This is actually such an amazing idea for a video series, I imagine this channel will blow up eventually.
Thanks so much! I really appreciate that.
This was fun to be a part of. I remember how satisfying it was to find the different arrangements of the polynomial factors and getting 3 different solutions when I was only expecting 1. Really cool to see all of these approaches and how people expanded on the problem.
Glad you enjoyed!
I was one of the submitters who proved the extended pattern, but the final solution is simply magical. It's so clear and illuminating and elegant. Well done
That's what I thought too! Glad you agree.
This video and video series are phenomenal. That final solution is actually amazing. I was happy to be a part of this video, keep doing what you're doing!
Thanks so much! You made a great contribution. Everyone go check out PolyaMath!! ^^^^^
4:45 proud to be a member of team Refined Brute Force. I used a few different optimizations and was able to calculate 20 sided dice in a matter of minutes. But I enjoyed seeing the grid, tiling and polynomial answers, those feel like true solutions to this puzzle! It was great to see this come together.
Glad you enjoyed!
Brute Force will always, eventually, find THE solution if one exists. But, alas, time = money, and thus Brute Force is often least fiscally responsible choice.
@@dumnor Lol
Woah! That shape solution is so creative!
That's what I thought, too!
And THIS is why having diversity of thoughts is important holy crap. So many unique solutions, so many different scopes, challenges, and advantages posed by them. Just wow.
Couldn't agree more!
A simple way to minimise the total number of possible die combinations is by realising that if the distribution of the sum of 2 dies with n faces is the same as the normal distribution for 2 dies with n faces from 1 to n, then if you add all the faces of the 2 dies you will get the same sum as the sum of all faces of the 2 normal dies. This is because the average value for rolling will be the same since the distributions are equal and also the number of possibilities is the same, n^2 since all dies have the same number kf faces. In a 4 sided die the sum of all faces is 10 and doubling that gives 20, so it is only required to check combinations where the sum of all faces is exactly equal to 20, no less no more. Adding the restriction that the 2 dies must have at least 1 face containing the number 1 to get a 2 decreases the total number of possible combinations significantly.
This can be used for any n sided dies, for a 6 sided die the sum should be 42, for a 8 sided die the sum should be 72, for a 12 sided die the sum shoyld be 156 and fianlly for a D20 the sym should be 420. The general formula for the sum is n*(n+1) for a n sided die. This should make the variables more dependent of each other and allow brute force algorithms to work on larger values.
Oh wow, what a great video, I didn’t realize this channel was so small until I looked afterwards, the quality is so amazing!
Thanks so much!
That tiling approach to solve this was amazing
I'm blown away by the creativity of the solution your viewers, makes you wonder how far can I progress in my ability to solve math problems.
Is there an expectation for when the third episode is going to be posted? Can't wait to try it!
It was so nice to see myself at the end credits, maybe some day my method will be discussed in the video itself.
Thanks so much! I'm not quite sure about the third episode right now. I may be making some other content first. Glad you enjoyed, and there's a high chance that your submission would be included in a future episode if you submit again -- I try to cover as many individuals as possible.
Electrical Engineer here. I pretty much took the same approach as the algebraic abstraction, and I'd like to share my way of thinking about it!
We could create a sequence P[n], that states how many times the number n appears in any given cube. In a regular 6 sided dice, the sequence (starting with 0) is
[0, 1, 1, 1, 1, 1, 1, 0, 0, ...]
And the sequence corresponding to a pair of dice is calculated by the convolution operation (P*P)[n].
The convolution could also be described as a multiplications of the Z-transforms of the 2 sequences (similar to how a convolution of two functions in the time domain is equivalent to a multiplication of their laplace transforms).
So all we need is to find two polynomials that multiply to the right polynimial
This may be one of the most fun math videos I have ever seen and the first time I have subscribed to a channel after seeing just one video. Great job. Love seeing the creativity of your community, and you present all of the topics here wonderfully
Thank you so much! I really appreciate that.
I just really love how you just go into all ways for too much amount of time
amazing! I love the tiling solution. I think like that so it feels so familiar even though I have never seen it before.
This is an awesome series! I also found the 1223 and 122334 pattern, then manually used it in the same way shown in the video to find solutions for 8, 10, and 12 before writing a python script to automate it. Totally will keep up with this!
Also, the tiling solution was genius. That’s the sort of thinking that solves unsolved problems
Thanks so much! Glad you liked the video.
I love seeing all the solutions these people came up with while I'm trying to even wrap my head around them
So cool to see everyone else’s solutions! I’m laughing at myself for using the FFT, in hindsight that was pretty overkill, but it worked!
If it works, it works :)
I was happy to be able to try out this problem!
Happy to hear it!
There were many solution techniques that I couldn't dream of! Glad I could contribute. Looking forward to the next challenge.
Thanks for the contribution!
Oh, this is such an interesting problem, and it's amazing to see all the community solutions to it.
Glad you thought so!
I am loving this channel!
You are doing something unique❤
You engage and include us directly into the content. Love it love it love it
Thanks so much!
The polynomial proof and the tiling proof are very pretty, beautiful stuff
I thought so too!
I just randomly stumbled across this video, but I actually played around with this problem last year for a school project! I love these dice. I knew them as 'Sicherman Dice'. At the time I used the polynomial method using the cyclotomic polynomial thing to find the factors. I probably didnt have the most efficient solution, but it did work pretty well.
Nice!
Going with the two 4-sided dice, you can speed up the process by elimination.
One, and only one, of each dice's faces must be 1, because 1 + 1 = 2. That drops the possible outcomes to 7^6.
Two of the faces across the remaining six must be 2, because either 1 + 2 and 2 + 1 or 1 + 2 and 1 + 2 = 3. That gives us 2 * 7^4 left to check. Still a bit of work, but far less daunting. We pick the one version that less like normal.
1 2 2 A
1 B C D
But 7 can't be one of the numbers on the second die anymore, because 2 + 7 = 9 and two 4-sided regular dice only go up to 8. So, B, C, and D can not be 7. A can't be 1 or 2, so the lowest is 3, and that knocks out 6 for B, C, and D. We plug in and try.
1 2 2 3
1 B C D
D then has to be 5:
1 2 2 3
1 B C 5
This solves 1 distribution of 2, 2 distributions of 3, 1 of 4, 1 of 6, 2 of 7 and 1 of 8. Meaning we need:
Two more fours.
Four fives.
Two sixes.
Try two 3s
1 2 2 3
1 3 3 5
2
3
3
4
4
5
5
6
4
5
5
6
6
7
7
8
The same principle can be had to find "alternative fair dice" for other sizes, but it would be a longer process.
For 6 sided dice:
1 A B C D E
1 F G H I J
1 2 2 3 3 4
1 F G H I 8
2, 3, 3, 4, 4, 5, 9, 10, 10, 11, 11, 12 for far. Leaving us with one 4, three 5s, one 10, three 9s, and a full distribution in the middle.\
1 2 2 3 3 4
1 3 G H I 8
This eliminates 4s, leaving one 5, three 6s, five 7s, five 8s, three 9s, one 10
1 2 2 3 3 4
1 3 G H 6 8
This eliminates 10s, and leaves one 5, three 6s, four 7s, three 8s, one 9.
Leaving an obvious answer:
1 2 2 3 3 4
1 3 4 5 6 8
2, 3, 3, 4, 4, 5, 4, 5, 5, 6, 6, 7, 5, 6, 6, 7, 7, 8, 6, 7, 7, 8, 8, 9, 7, 8, 8, 9, 9, 10, 9, 10, 10, 11, 11, 12
And theoretically, a fair 8 sided dice set would be:
1 2 2 3 3 4 4 5
1 3 5 5 7 7 9 11
This was really lovely
Between the problem itself, the presentation (and animation), viewer interaction, crediting, and the multiple different ideas thereof. Excited to see more of it
Thanks so much!
what an amazing video, i didn’t know what i was expecting when i clicked this video but the result was so much better. the creativity and how you displayed the solutions was amazing
Thanks so much!
the tiling solution is conceptually the same as a convolution.
If we extend the problem a bit by making the dice complex and the dice continuous instead of discrete, you can do a bit of spectral witchcraft.
Treat the target distribution as the magnitude of the frequency spectrum, and take the inverse discrete Fourier transform assuming the imaginary component in all cases is zero. Because the convolution of two signals in the frequency domain is equivalent to multiplying in the time domain, you can take your time series representation of the spectrum and divide it by whatever signal X that has nonzero terms, and by definition the frequency spectrum of the output Y convolved with the spectrum of X will be the target spectrum.
It's a fair bit easier than the discrete case
A few observations could definitely cut down on the search space. I consider these to be self evident.
A: There must always be exactly 1 "1" on each die.
B: The highest number of both dice must be unique, and must sum to 2N.
C: The order of numbers on a die does not matter
D: The order of dice does not matter
E: The total number of pips is equal to twice the sum of pips on a single "regular" die. Which is equal to (N² + N) pips for both dice. (even if the pips are represented as a number)
From this corrolaries:
The highest number on a die cannot be a 1. Therefore the highest number any die can have is 2N - 2.
There are N-1 combinations of the maximum dice (2 through N). Exceeding N would reverse the dice order, which is unnecessary.
There are N² - 3N - 2 pips to be assigned to the middle numbers on both dice.
Each middle number must be inbetween 2 and 2N-1.
2*(N-2)*2 pips are locked into each middle number as it is at least 2.
There are (N² - 7N + 6) pips free to distribute among 2n - 4 numbers.
For a 8 sided die, there are 7 possible sets of maximum numbers and 14 pips to freely distribute among 12 middle numbers.
Good observations!
Tetris Person NEEDS to be invested on. I mean, literally. Like a scholarship. Or a grant.
i used the ifft method and found a solution almost immediately but didn't send you my work because i wanted to make it more rigorous but time escaped me
I forgot this channel had so few subs. I'll definitely try the next problem!
Looking forward to it!
loved trying to solve the puzzle and this video! cant wait for the next one
Thanks so much!
that last solution is SO creative im actually impressed, i love these types of puzzles a lot
@@seazeiscool Glad to hear it!
A visual solution is always satisfying
I agree!
so neat to see all the different approaches! amazing video and community!
@@smtsjhr Thanks so much!
I'd love nothing more than to be able to speak to the person who came up with the "tetris" solution. That type of thinking is genius type thinking.
Thought: the probability distribution for the sum of two variables drawn independently from two given probability distributions, is the convolution of those two distributions.
If we take the Fourier transform of the target distribution, we need the Fourier transforms of the two distributions to multiply pointwise to the one of the target.
Given the distribution for one of the dice, we can divide the Fourier transform of the target by the Fourier transform of the given one. If this involves any division of something non-zero by zero, the given one won’t work.
Uhh…
But then we have to somehow put in the “but we only have (e.g.) 8 equally likely sides on each of the dice” aspect to it…
Maybe this isn’t a good approach…
Edit: 7:15 : oh cool, it is a reasonable solution
11:26 : very nice! Giving all the solutions all at once!
This has to be the most fascinating math video I've seen this year, just beautiful
Thanks so much!
The last one made my jaw drop, holy crap
Yeah, me too! I thought it was very neat.
8:55 I don't know who is Rose, but if she/he use Scratch, (s)he is a good personn.
4:20 Similarly, you can restrict the biggest numbers on the dice to add to 2n where n is the number of faces and not repeat, which would immediately restrict the numbers on one die to be strictly between 1 and n, which limits the possibilities for that die by a lot
Very true!
After watching the first couple minutes I did it by hand and then got to watch the video confirm the approach. Very fun
Nice!
The shape-filling method makes it obvious that dice with a prime number of sides can't have other solutions! How can you possibly hope to fill the big parallelogram with copies of a smaller shape, if the width of one row is prime? Other than the trivial solution, you don't!
Very interesting video, of which I'm quite surprised with the inverse FFT solution. I'd also check where dice can roll a '0' or even where single dice can roll negative numbers, because life isn't always positive, either. With a pen and paper exercise, it shows the results are exactly the same, at least for sets in with all dice in set A are increased by the value the dice in set B are decreased. Apparently this is also true for non integer values. They have to be all the same, though. E.g. A = (-4.5, -3.5, -2.5, -1.5, -0.5, 0.5) and B = (6.5, 7.5, 8.5, 9.5, 10.5, 11.5)
In general, if you add k to all the faces of die 1 and subtract k from all the faces of die 2, you'll get the same distribution because if D1 + D2 is the sum of the regular dice, the new sum is (D1 + k) + (D2 - k) = D1 + D2.
This problem actually looked so fun
Hope this series contenues
That's the plan!
@@PurpleMindCS yay
The series seems really interesting, and I can't wait for more videos!
Thanks so much! Glad you enjoyed.
omg i love the last solution that's truly elegant
Yeah, I really like that one too.
the goat returns
Lol thanks :)
13:00 Primes only hafe two factors(1 & n), witch is obvious and I think that plays in there.
Absolutely.
when factoring x+x²+x³+x⁴+x⁵+x⁶+x⁷+x⁸ you left a factor of 1+x⁴ which can be factored further into (1+√2x+x²)(1-√2x+x²). although you do have to get the two of them together, you can't necessarily know that unless finding them and proving so.
the last solution blows my mind so hard that I kinda want to make my own dice now
Do it
This channel is awesome.
Thanks so much!
I can’t remember if this was stated in the video, but the highest face on each die cannot be a duplicate face. In addition, the highest face on each die must together add to the highest value of the distribution. And the highest face on each die must be no less than 3 under the highest value of the distribution
Using the 2d4 as an example, the highest value is 8 so we can separate it into 2 pairs of dice to check, each having 4 faces filled in.
We only have to check these two:
1xx5 & 1yy3 where 1
Very true! I did not mention these particular constraints, and there are probably lots more similar ones that one can find.
When you started showing the tile solution, i immediately thought about Convolutions. Wonder if those are applicable here, i am pretty sure they should be. Anyway, great video.
Yes, essentially the tiles are simply a way to visualize a convolution!
I never got around to e-mailing it, but there’s a pretty computationally cheap way to find it for dice with 2n sides. One die will of course follow the simple green die pattern, but the other die’s faces are each calculated with a simple 2-variable equation. I never got around to proving that it works (which is why I never sent it), but I tested it up to d1000 and it did
I think it's likely that your program uses similar techniques to that of Rose from the video.
@@PurpleMindCSI didn’t see her technique for the second die, but we definitely followed a similar route.
12:46 I actually thought they were the Fibonacci numbers
Great video, though I wish you would have elaborated on the Fourier transform solution which was briefly mentioned..
Subscribed for tiles and vibes. Thanks!!
Thank you!
BRUTE FORCE BY HAND
Lol
Very cool!
Thank you!
I put on this video to fall asleep to but it was too entertaining
💀
When I saw that tiling solution at the end I swore the words "conditional convolution" popped into my head. Honestly I don't think I have the rigor to go on with that tangent.
while(stack is not invalid and not complete){
while (curr_index is not full{
drop stack at curr index}
increment curr index}
How you would mangle a convolution like that into mathematical notation is beyond me.
This was fun to try and solve, but I am now a bit disappointed that I didn't seem to get as far as some others. I calculated all the valid dice pairs for dice up to 200 sides, but it looks like another viewer, mark got to 300 (shown here: 12:23). What method did they use? I now wonder if there is a faster, more optimized method, or if they just spent more time on calculating it. I wonder how far this can be taken, and how good a solver can get. I've always gotten an exponential time complexity, or at least, it grows exponentially with the number of factors the polynomial has, but maybe that's just a result of the method.
Two things:
1. I believe Mark mentioned that he indeed took a very long time to compute his answers.
2. I'm not exactly sure how your solution works, but keep in mind that the polynomials we're trying to factor are special, not arbitrary polynomials (that is, they are x + x^2 + x^3 + ... + x^n). You may find this wikipedia page useful if you haven't seen it already: en.wikipedia.org/wiki/Cyclotomic_polynomial
I only watched the intro but I would probably use the same method from a paper I saw about find other pairs of dice that roll the same as a pair of a normal 6D by using polynomials.
Bro mind blow
W T F for the the last one. Crazy impressive
I like watching videos like this that have zero practical applications to me irl yet I watch anyway
Math is art.
I guess the last solution explains why there are no alternate solutions for prime numbers - you cannot split a prime-length base into multiple equally long parts. Of course what I would love to see is a proof that all solutions are representable as tilings.
Yeah, that would be cool. Not exactly sure how you would go about it (or if it's even true). It's clear that tilings represent solutions; but the other implication, not so much.
This should be in ap cs a classes
I thought this video was about finding a combination of dice that would allow you to have the same probability for each number. That would be useful for games.
9:49 I stuck here when doing the problem and have to use brute force to solve the algebra😂
Ted actually had a method involving a spreadsheet with the 6 sided trick dice, but that involved one of the dice having a lower max number. Here's the video if anyone is interested: ua-cam.com/video/urOkfsIRFlw/v-deo.html
Thanks for sharing!
When I first heard the problem I misunderstood two things:
-all probabilities are the same
-it's the same dice
And then I proved that impossible for the four sided dice😂😅
Lol
Great video! I do have one question though, why are we ruling out dice with 0 as a possible sude value? Is it just because percentile dice typically use this as 10? I would think there could me a few more solutions, especially interesting solutions this wau
Good question -- the decision to allow 0 or not is essentially arbitrary. You get some cool results if you do include it (as you have mentioned), and you get some cool results if you don't. In particular, when you don't allow 0, the connection to prime numbers becomes more apparent, as otherwise every value of n (including prime values) would permit at least one alternate solution -- just subtract one from each face on the first die and add one to each face on the second.
Now do it with a -1 sided dice.
Lol
That polynomial stuff is genius. How'd you come up with it?
First of all, it would be disingenuous to pretend that I came up with it. I knew about this technique already from other combinatorial problems. And anyway, the solution you see in the video was submitted by a viewer (@Polyamathematics on UA-cam -- who, by the way, makes fantastic videos!!).
But how would one come up with this without prior knowledge? That's a tricky question. It's hard to pinpoint where a piece of mathematical insight get's its inspiration. But one thing for sure is that experience with a wide range of existing mathematical concepts can help prime your brain to think of a new connection. For example, if you had been working with polynomials and perhaps multiplying them together, you might more easily see a resemblance between that process and the probability distribution generated by rolling dice.
If you are familiar with generating functions and/or taken a combinatorics class then the idea of associating x^n with a corresponding possible choice value n would be likely something you would try after a bit of thinking
@@ambiguousheadline8263 Indeed
Generating polynomials of that type, of order p where p is prime and all coefficients are equal to 1, cannot be factored.
Indeed
I'm putting this on my "watch later" list. See ya when the video becomes viral
Haha thanks :)
I'm not one to usually enjoy math but dice math is always fun for me
Glad you enjoyed!
very cool
Thank you!
detail, but still. The patterns at 15:35 should be 1234 and 3456 rather than 1233 and 4456 -
those are the columns they occupy and make this solution so simple and elegant..
Yes, that is true. See the pinned comment.
This makes me wonder how absurd the possibilities are when the limit of only having positive integers is removed.
Try it!
Anyone else ever tried to understand what the complex factors of the polynomial mean in a combinatorial sense?
It may be useful to think about complex conjugate pairs :)
i heard the music at the very start and thought all of my usb devices were disconnecting lmao
That's actually so funny, I never considered that XD.
Man, you are all way smarter than me.
I think this is a somewhat limited viewpoint. While it's true that there are some people who have a better inherent ability to do math, the extreme cases of this are very rare and most of what seems like natural facility can often be attributed to experience and dedication! I'd say if you work hard at growing your understanding, it's likely that in a year or two of learning you could find yourself looking back and viewing the others here as peers rather than superiors.
this seems like unlocking a combination lock...
Can you use these tacktics to make fair dices? Where each ouycome is distributed even?
Try it for yourself!
Now what if we remove the integer constraint, or if we allow more than 2 dice
Good question! I think you get some pretty interesting results here. Particularly if you remove both of those constraints at the same time.
how do we deduce the numbers on the faces from the tiles in the last solution?
Good question! Firstly, note what I said in the pinned comment -- I made a mistake in my labeling of the faces on the green die for the third tiling example.
But here's how it works: the faces on the green die are determined by the tile that we're using to fill up the overall shape. We start with a 1 in the bottom-left corner of the tile, and then each subsequent column gets the next integer (2, 3, 4, etc.) If a column is skipped then there is no green face with the number that would appear in that column.
For the faces on the blue die, we need to look at how the eight copies of the tile fit together to fill up the target shape. The blue face for a particular copy of the tile is the column number of the leftmost part of the tile. For instance, in the first tiling example, the leftmost part of the tile with a blue face of 1 is in column 1, and the leftmost part of the tiles with a blue face of 5 are in column 5.
Why this works should hopefully become clearer if you go and rewatch that section of the video. I think you should find it more intuitive after thinking about it for a little while :)
Honorable mention: I found several dice.
Nice!
Isn't the last solution a sort of visual representation of inverse convolution/cross-correlation and as such a visual representation of the inverse FFT of a sort? Just interested if the two are basically the same
I believe this is true. However I thought the visual representation of it was very interesting!
Regarding "there must be only one way to make two"; is it not possible for one die to have zero, and tge other two?
The problem constrains the values on each face to be positive integers (so not zero).
15:34 a 3 and a 4 seems to be swapped i think
You are very correct! Thanks for pointing that out. I'll make a pinned comment.
989 upvote is mine
Thanks so much!