To try everything Brilliant has to offer-free-for a full 30 days, visit brilliant.org/AnotherRoof/ . The first 200 of you will get 20% off Brilliant’s annual premium subscription.
That fact that you can remove some many of the variables in the beggining transforming the problem and that the solution is basiclly diophantine Equations is just so beautiful
I'm so impressed with how this channel has grown since its first SoME video a year or two back. This stuff is seriously higher quality than a lot of very popular math channels, and with deeper and more interesting theory. Thank you for all this!
Before there were DVDs, there was a similar problem. In cheap versions of breakout (balls bouncing against walls) on early home computers (e.g. ZX81/spectrum) the ball moved by an integer number of pixels left/right and an integer up/down. In these versions the ball bounced off the bat with the same angle of reflection as incidence. This meant that sometimes it was not possible to clear a board as there were some bricks that could never be hit with certain ball angles. Oh the problems of youth!
I'm not sure which cheap versions of breakout you are referring to? But in this ZX81 version you could in fact control the angle of reflection by controlling the exact location the ball hit the bat as you can see in this video: czcams.com/video/ZOH4qAqhXvo/video.html Which I believe was fairly standard behaviour for such games
Great video! Loved the live action visuals. Your explanation of the Euclidean algorithm avoided a lot of the leaps of faith I made in mine. And simplifying to a lattice is a brilliant way to make the numbers easier. I think your assumption that the logo always hits a wall perfectly doesn't lose any generality, because even if a logo 'crosses' the wall a bit, it will still bounce back on the next frame, making the setup equivalent to a lattice one tile longer. You can confirm this a bit with the simulation I made for my video (which I believe I can't link without my comment being auto-removed by CZcams). If you use the default settings but set the X speed to 7 so that crossing a wall is more obvious, you can see that a screen width of anywhere between 395 and 401 leads to the exact same path!
Ahh yes, you're absolutely right! I did all my working out before watching yours, and when you did it as "a bounce is on the first frame when it hits the edge or *passes* the edge" I was jealous that you didn't have to make that assumption! And I think you're right that no generality is lost. Link is in the description to this video for those who want to watch, it's great!
When I was a little nerdling (3rd form, if I recall correctly), it was in the days before VCR's, to say nothing of DVD's. But I wondered about this exact problem, thinking in terms of a billiard table with m diamonds on one edge and n on another. Bless my mathematics teacher! She showed me the argument involving modular arithmetic, and taught me the _extended_ Euclidean algorithm. I think I managed then to prove most of the results in your video. I'd credit Mrs Smith for the fact that I'm a (semi-retired, applied) mathematician today.
What I find so interesting about this video is the way you use mathematics to tackle this issue. I expected that someone had dumped the firmware code of an old DVD player (I bet you could probably find an old Apex brand DVD player firmware somewhere online, the Apex players were very interesting products that would play basically anything you put on a disc no matter what format it was in, ignoring region locks and other things they were 'supposed to' not do) and you'd be going through their actual algorithm. That's just how I'd tackle it as a software person.
@@bingxiling9154also because CRT’s have better effective resolution than flat screen displays, so while the jump from VHS to DVD was a bigger jump in quality, the jump from CRT to LCD undid a great deal of that image quality improvement. If you had a top line HD CRT TV, you would have seen a massive improvement when going to DVD from VHS.
Thanks for this. I've always mentally did this with any kind of rectangular grid (e.g. ceiling tiles), (Hi, ADHD!) but I never thought about starting in an arbitrary place, but always at a corner. I knew it always had to end in a corner, but never knew how to predict which of the other three it would be. Now I do!
I always thought that the DVD screensaver would always hit the corner eventually because of what they were designed to do The purpose of a screensaver is that, to save the screen. The animations that play prevent a static image being shown on a display, by constantly refreshes all of the pixels, thus preventing or delaying burn in, where static images that are displayed for long enough would still be seen when that image wasn't displayed. This was a problem on older TVs, and has come back with OLEDs. Some OLED TVs have features that will shift the image by a few pixels every so often to prevent burn in. So for the DVD screensaver to do this job, it should cover the entire screen, which it would require it to hit the top corner pixels. However, I might be wrong on that, and the DVD one specifically, or depending on the implementation may not always hit the corner. Or the animation would start in the same place and direction, so it would always hit, whereas the video wonders about some arbitrary 'DVD like' screensaver. I am also only 10 minutes in when writing this, so if it is addressed later, my bad
The timing of this video is fantastic considering ive just finished a module on elementary number theory in one of my math courses in university, so this is both a lovely way to see it applied, and a nice refresher of the more fundamental ideas. I really love your method of explaining stuff, and it usually complements the more "university" like explanations I usually have, while still being rigorous and in depth enough to not just be a cursory look into the topic that is more common on CZcams
I've been wondering how to go about solving and lo and behold, this video was recommended to me! What's awesome is that I technically already knew about Bezout's Identity, I just never know how to apply it until now! This video was awesome!! 💯
12:32 The simplest solution with integer k_1, k_2 for this equation is k_1 = 6, k_2 = 1. 12*6 - 51*1 = 72 - 51 = 21. P.S: General solution is k_1 = 17n - 11, k_2 = 4n - 3, where n is a integer.
Just had to pause at 28:16 and point out I don't think I have seen anyone motivate the "discovery" of the Euclidean algorithm (with proof to boot) quite so well. And never once mentioning the scary word "algorithm". Thanks for showing another way to teach this algorithm!
I love this, applying ultra maths to some minor trivial nostalgia, to reveal beautiful patterns or simplicity. I wonder if the designers of the screensaver had any idea of this maths - it does seem that x and y were set peculiarly to create a long period.
10:26 Here's another way to explain this: When on an edge, the logo is bouncing rather than traveling in a direction. In other words, the logo only visits the edge once, but it visits other nodes twice. So, the points not on the edge are doubled. But there are two edges, so that halves the period. (Note that corners are intersections of edges.) So, it's (1+2(n-2)+1)/2 = n-1
I'm just starting the video, but it is awesome to see that I am not the only crazy person (lol) that wondered about all the variables that influenced the corner alignment of the logo, and if there was an infinite number of guaranteed corner bounces
I think in reality, the box speeds up or slows down as it collides with a wall in order to synchronize the collision with a drawframe. It calculations position, realizes theres a collision, calculates collision point, and then moves the box to that collision point. I dont think theres a step then to see how far it moved, and then completing the rest of the motion trajectory to make the movement stay the same length
The reason infinitely many solutions exist to the Diophantine equation: if we are trying to find a and b such that ax+by=c. then we can do the process in the video to get one working solution, then we take the homogenous case. if ax+by=0, then solving is trivial, ax=-by, so find you could use the lcm of x and y, but an example solution (although there are many) could be a=y and b=-x. once you have this solution, notice that you can add it to your original problem without changing anything. if a1 and b1 solve the homogeneous case, then adding any integer multiple of them to the original shouldn't have an effect on the final value, if ax+by=c then ax+by+a1x+b1y=c+0. and simplifying gives (a+a1)x+(b+b1)y=c which is another solution. you can repeat this process by adding in the homogenous case again yeilding another new solution. do this infinitely many times to yeild infinite possible solutions.
AH! My Brain! You're talking about graphics with 0,0 at the bottom left. A bunch of time writing software the does graphics makes me think in terms of 0,0 at the upper left with positive y going down any time pixels are in play.
Sorry about that -- you won't believe how many times I changed my mind about this! You can see later in the video my spreadsheet has the coordinates running downwards. In the end, I decided that more people were familiar with the Cartesian Plane and how coordinates work there but I spent a long time deciding! Hope it isn't too distracting and enjoy the video!
Off the cuff thoughts, method of treatment is like a specific case of fixed step finite difference with specific (periodic) boundary conditions (and initial conditions) for the motion of a rectangular projectile with perfectly elastic collisions. It is essentially a potentially nonergodic system in general. For certain initial conditions and screen aspect ratios you can have highly localized trajectories. If the ratio of the horizontal and vertical speeds have a rational relationship to the aspect ratio I would expect only a local part of the screen to be covered.
This is a nonergodic system in general. And if you want it to repeat exactly in a finite time you want nonergodicity and the right initial condition! This is like saying the Poincare recurrence time is finite! Which requires the resonance between the x and y degrees of freedom you discovered. Occurs in many nonlinear dynamical systems in mathematics, chemistry and physics. Dynamic billiards are well studied: en.wikipedia.org/wiki/Dynamical_billiards (And using the finite difference approach: en.wikipedia.org/wiki/Arithmetic_billiards), blogs.ams.org/visualinsight/2016/11/15/bunimovich-stadium/.
gonna add a bit of an extra difficulty to the problem.. assume the anchor point is always at the corner of the DVD logo and not the center. if the logo is at the top left quarter of the screen it is anchored at the top left of the DVD logo and so forth. this means that the size of the logo greatly affects the point on which it bounces off the edge of the screen.
Just started watching, guessing the first step is gonna be to look at the representation where the logo never bounces, it just passes through the screen into a reflected version of itself, and we make a big grid of these reflections.
Sir, what a way to explain. Respect for that and very interesting topics. I also respect the fact that you did most of it manually, even though most people uses manim. Thank you
Having done the mathematics of Countdown, another good math game deep dive could be the 24 Game, where you have 4 numbers and have to reach 24 via the basic 4 operators. It's a classic for kids, so I'd love to see the a big dive into the maths of it all.
I wonder if there's a simpler way to solve this using the "infinite trees" problem. If you point a laser through a grid of trees from the origin, you're guaranteed to come arbitrarily close to one of the trees, since any angle can be approximated more and more precise fractions. Then maybe you could make alterations in the proof of that to adjust for the starting position on either the x or y intercept. There's probably some technical reason why these aren't similar problems, but the solution to the tree problem would give insight into the solution of this one, provided we allow a tiny bit of imprecision, maybe the caveat being the measly accuracy of human eyes allowing near-corner-hits with some level of allowed variance.
I think you're right! I briefly looked into this while planning my video, but decided against bringing it up as I didn't like the idea of introducing yet another problem, especially when I try to make the videos for a broadish audience. Thanks for watching!
@6:41 “Mathematicians have a name for this type of structure, by the way; a lattice.” Well, lattice theorists don’t restrict themselves to integer points in the plane or even in any other Euclidean space, so you’re not accessing best terminology. This kind of lattice is better referred to as a Gaussian integer lattice because it’s in a plane, and so the elements of the lattice can be viewed as Gaussian integers (complex numbers with integer real and imaginary parts). In fact, you’re locating your grid so that it’ corner is the zero element of the complex plane, and so it’s better described as a finite initial segment of ‘positive’ cone of the Gaussian integers, and the more general notion is that it’s the ‘positive’ cone of a lattice-ordered group. If you analyze the approach, I expect there are some interesting related results in the theory of lattice-ordered groups with similar arguments, and so that this result you demonstrate will be a special case of such results. Your argument uses periodic extensions that are still contained in the ‘positive’ cone of the Gaussian integers, so that’s where I’d think someone should look if they want to learn the deeper results. …
bro, I am thinking about this since I did some crude graphics animations in 320x200 (256 color) VGA graphics. Would a pixel bouncing in 45° fill the screen? What if I add a little bit of randomness? And what do I do if I hit exactly the corner, as seemingly I have to go the way back, rotating by 180°
In certain areas of wireless network research it is common to put devices into a square and let them move about it. One often used model is the "random waypoint model" but this is not a good model as shown in the paper "random waypoint considered harmful". A better model starts at a random point, moving at a random direction at a fixed speed, perfectly reflecting at each wall. Like the subject of the video - assuming a point object. It's easy to show this gives a random distribution in the x coordinate, and a random distribution in the y coordinate. But does it produce a uniform distribution across the square? Clearly not always - if you start on a long diagonal aiming at a corner on that diagonal then you will never leave that diagonal. And some other special cases can be constructed. But does it produce a uniform distribution across the square almost always? If so, or if not, is this a published result? Is this therefore a good model, or should it also be considered harmful?
I did a school math project on this a few months ago My project was a totally different scope but it was interesting to see how closely our ideas aligned Great video
My answers at the start is it’s not necessarily going to hit the corner. It will either hit the corner or be a repeating circuit of some sort. Though in practicality I imagine it’s basically always gonna be in corner mode.
This video reminds me of the genius pannenkoek's Watch for Rolling Rocks in 0.5 A Presses "But first, we need to talk about parallel universes" SM64 video.
8:16 Another way to solve the bouncing problem is by flipping the position instead of the direction. In this case, you should flip the position around the center of the board. Equivalently, you can flip the board
Playing with an oled screen and Arduino I ended coding something like this, but I didn’t move it more pixels, just increased the refresh speed, when reached certain position it reverses one axis .
15:12 That definition works for natural numbers. However, there's no largest common divisor of 0 and 0 by the usual comparison. There is if we compare by divisibility or in my way. (The latter is like comparing by absolute value except 0 is larger than all other numbers.) These methods of comparison aren't exactly orderings of integer. In them, n and -n are considered the same. So, you'd need to define it as the nonnegative one (or in another similar way)
quick question, do solutions exist for x*k1 + y*k2 = any common divisor of (x,y)? You gave a reason that went like: if gcd(x,y) = d, then we can write the Diophantine equation x*k1 + y*k2 = m as d(x/d * k1 + y/d * k2) = m and so if m isn't a multiple of d then no solutions exist. Can we just use the same argument for any common divisor of x,y? Thus if m is a multiple of any common divisor of x,y then a solution to x*k1 + y*k2 = m exists?
I actually coded a clock that bounced like the dvd logo using JS, though due to a bug, I accidently made it hit only the bottom corners and the top center.
In a real sense, there's only 1 direction. If the path starts in the negative direction, just flip the whole starting point in X (both position and vector).
The euclidean algorithm explanation was a bit cumbursome and backwards. Usually people start by saying that using the algorithm, you can find the gcd(a,b), and only then people explain, that in the process we get a solution for an equation. I had to explain all the little facts about polynomials today, and it stood out to me, that number theory and polynomials are awfully similar. Then I remembered about the Rieman hypothesis and it all made sense
In graphics programming the vertical axis almost always increases as you go downwards, rather than upwards like the math convention. This is probably because the horizontal lines of CRT displays are drawn one at a time starting from the top, so the top line is line 0. So what I'm saying is the DVD Logo thinks your graph is upside down
Hello, thanks for watching! I've responded to a previous comment about this but yeah, I went back and forth on which direction to label the y-axis. Initially I had it the graphical direction but eventually settled on the mathematical convention as I thought that was more intuitive for more viewers. Luckily it doesn't matter, but it made some parts tricky as all my early notes had it the other way around!
I understand that you just went and had fun with this. But the problem isn't nearly as complicated since screens aren't arbitrarily shaped and sized. I actually thought you where going to go towards how they would have guaranteed that the logo covers as much surface as possible. Because as a screensaver in the era of CRT it's main purpose is a burnin countermeasure. And you eventually did show the coprime behaviour near the end really quickly.
This is similar to Euclid’s orchard problem which is equivalent to solutions of Pythagrean triples or equivalent to finding all rational points of a circle a^2 + b^2 = c^2 (a/c)^2 + (b/c)^2 = 1. These rational solutions and all their multiples can be derived from Hilbert’s theorem 90. The corners of the square with length x and width y have rational slope x/y. If the starting point chosen is a multiple to the rational solution described by corner, the logo will hit the corner. Though this is algebraic, there is a some periodicity appearing in it that is really difficult to explain in general at least coming from the algebraic side.
Actually it's not if one knows how to relate things and substitute. What do I mean by this? We can use the slope-intercept of a line formula y = mx+b where the slope m is defined as rise/run (y2-y1)/(x2-x1) and b is the y-intercept. This is a basic algebraic linear equation. We can the rewrite the slope formula as dy/dx. Now, we can take the basic sine and cosine functions from their right triangle definitions: sine = opp/hyp and cosine = adj / hyp. We can use the relationship of this right triangle in standard form where the angle theta is the angle that is between the line y = mx+b and the +x-axis. With that we can see that within the slope formula dy/dx is exactly equivalent to sin(t)/cos(t). In other words dy = sin(t) and dx = cos(t). Therefore the slope of a linear equation is equivalent to tan(t). With that we can substitute and rewrite the slope-intercept form of a line as y = (sin(t)/cos(t))*x + b or simply y = x*tan(t) + b. This is why we are able to see periodicity within the linear relationships. Also for any number N that is rotated by either +/- 180 degrees or +/- PI radians it is the same exact thing as multiplying it by -1. Why? Well if we multiply 1 by -1 we get -1. What is the dot product of 180 degrees? It is -1. And arccos(-1) is either PI radians or 180 degrees. There's more to it than just that. Just from the simple expression of 1+1=2 which is basic algebraic arithmetic, this simple expression is in fact a linear transformation. This transformation of adding one to itself without realizing it is in fact the unit circle with its center located at the point (1,0). If we take the general definition of an arbitrary circle (X-h)^2 + (Y-k^2) = r^2 where (X,Y) is any point on its circumference, (h,k) is its center point, and r is its radius. We can see that this is a specialized version of the Pythagorean Theorem A^2 + B^2 = C^2. The definition of the unit circle located at the origin is X^2 + Y^2 = 1. The only difference here with the simple expression of 1+1 = 2 is that the unit circle is translated 1 unit to the right with its center at (1,0). If we take this expression and substitute it into the equation of the circle we end up with this: (X-1)^2 + (Y-0)^2 = 1. We can then take this and use algebra to simplify it and to solve for it in terms of Y. (x-1)^2 +y^2 = 1 x^2 - 2x + 1 + y^2 = 1 - 1 -1 x^2 - 2x +y^2 = 0 -x^2 + 2x = -x^2 + 2x y^2 = -x^2 + 2x sqrt(y^2) = sqrt(-x^2 + 2x) Oh wait a minute we have the square root of a negative number... Where did that come from? Yup complex numbers are embedded within 1+1 = 2. Why? Because the multiplication of i is a rotation of 90 degrees or PI/2 radians. Euler's formula and identity shows this in greater detail! In truth, all of these properties aren't just embedded within 1+1 = 2. They are embedded within the numbers themselves. If we take the expression or equation y = x which is an equivalence or identity expression which can be written as the function f(x) = x, this is still a linear equation and there is still a linear relationship of any given number x with itself. This line has a slope of 1, and a y-intercept of 0. A slope of 1 is the same as 1 = tan(t) which is 45 degrees or PI/4 radians. All fields of mathematics are related. It doesn't matter if it's Algebra, Geometry, Trigonometry, Calculus, Probability, Statistics, even Logic or Boolean Algebra. Within Boolean Algebra the OR gate is relative to addition and the AND gate is relative to multiplication. When you get into circuitry with the context or abstraction of logic gates and we use boolean algebra we can simplify things through the use of either The Product of Sums or the Sums of Products. More than just that, but Boolean Algebra and Logic itself has a direct connection with Log2 arithmetic. And Logarithms are Algebraic. Even our understanding of physics, and chemistry is rooted within mathematics. Why and how is everything related? Simply because of motion which is a transformation. Neither Energy or Matter can be created or destroyed they can only be transferred or transformed. There's also a direct connection between these, number and group theory, information theory, and fractal geometry. It may not be evident at first but for every linear transformation (moving along a straight line), there is always an implied rotation. This is something that isn't necessarily taught in schools or universities, however it is an underlying pattern that I've recognized that is always present. When you walk a straight path, your legs are swinging at an angle within the socket of your hip joint. When a bird flies through the sky and their wings are flapping in the air, they are rotating. It is to my understanding that you can not have linear transformations without some form of rotation and vice versa. They are interdependent of each other. Once you have one, you have the other. Otherwise we wouldn't be able to have reflections or symmetry. Just some food for thought! There is periodicity in y = x, never mind a + b = c. If there was no periodicity then there would be no identity. Just wanted to shed some light into the matter because it is quite sound. John 1:1-5, Genesis 1:1-5
@@skilz8098 Euclid’s orchard is viewing a square lattice of rational points from the origin. The angle θ of the slope as described is the inverse tangent since tan θ = opposite/hypothenuse. The rotation is given by exp(iθ) with angle θ in radians. The dot product of two perpendicular vectors is always zero. 1+1 = 2 is a linear transformation but I don’t find its reoccurring mentioning here too relevant. It is not standard to have the origin not at (0,0) when considering coordinates on a plane. It will shift any calculation if it’s not. The square root isn’t additive so this additional shift doesn’t derive it. It is easier to consider the complex numbers on the plane in their exponential form. Integers are a subset of the reals which is a subset of the complex numbers. Complex numbers can be written in exponential form z = r*exp(iθ) which is a succinct and useful way to describe the polar vectors that describe each point of the lattice in question. All mathematical fields are related and there are theorems which describe some of the relationships. Applied mathematics does solve many problems such as finding when exactly the DVD logo will hit the corner. Circular motion does propel most real world things forward. I think there are groups which are understood through symmetry that have faithfully representations as the orthogonal group which describes rotations but I’m not sure if it holds in general. It was something to think about and ponder. Functional equations do equal themselves and this is sometimes called their identity. You are very faithful. I was thinking more of Langlands program which equates periodic functions to algebraic expressions in a general way but was not coming up with anything then. Euler’s formula exp(ix) = cos(x) + i*sin(x), roots of unity, and their Fourier series is more of what I was after.
@@Jaylooker Nicely stated. Yet it's the purity of math and the relationships of numbers that intrigues me. Especially when we consider how a simple equation or expression can generate an infinite complex structure with amazing beauty such as the Mandelbrot Set, and that's just the tip of the iceberg.
@@skilz8098 Then study math and do some of the practice problems. Studying Fourier analysis and harmonic analysis may interest you because of the periodic functions they describe.
@@Jaylooker I've written my own 3D Graphics / Physics Simulation in C++ using DirectX 10-11 / OpenGL 3.x. I started to learn Vulkan a bit too. I even worked on doing a 6502 NES emulator. I'm quite familiar with the math and physics! I've done a little bit of 3D Audio Processing as well.
I wonder if any DVD firmware programmer SOMEHOW had too much time on their hand and implemented "subpixels" or letting the DVD logo move in "fractional numbers". That would have thrown EVERY researcher of this phenomenon for a loop.
Would you consider not having background music to make it easier for us with poor hearing? There may be a motivation for having background sound and i would curiosity hear it.
To try everything Brilliant has to offer-free-for a full 30 days, visit brilliant.org/AnotherRoof/ . The first 200 of you will get 20% off Brilliant’s annual premium subscription.
I had no idea that the DVD logo problem had anything to do with Bezout's identity! (The extended Euclidean algorithm finds your x and y!)
i already have brilliant premium lololol
Amazing video
That fact that you can remove some many of the variables in the beggining transforming the problem and that the solution is basiclly diophantine Equations is just so beautiful
"Diophantine equations are just integers, they're just basic, right?"
Right?
I don't think I can express how excited I am to see a dvd logo hit a corner (edit: was not disappointed)
Omg it's Not David I love your videos!
Glad we all agree that the Screensaver is the best tool for agreement
Hi David
How many times did he uhmmmm?
Are you david?
I'm so impressed with how this channel has grown since its first SoME video a year or two back. This stuff is seriously higher quality than a lot of very popular math channels, and with deeper and more interesting theory. Thank you for all this!
Before there were DVDs, there was a similar problem. In cheap versions of breakout (balls bouncing against walls) on early home computers (e.g. ZX81/spectrum) the ball moved by an integer number of pixels left/right and an integer up/down. In these versions the ball bounced off the bat with the same angle of reflection as incidence. This meant that sometimes it was not possible to clear a board as there were some bricks that could never be hit with certain ball angles. Oh the problems of youth!
Amazing, wish I'd known that before making the video as I'd have mentioned it for sure!
I'm not sure which cheap versions of breakout you are referring to?
But in this ZX81 version you could in fact control the angle of reflection by controlling the exact location the ball hit the bat as you can see in this video:
czcams.com/video/ZOH4qAqhXvo/video.html
Which I believe was fairly standard behaviour for such games
Great video! Loved the live action visuals. Your explanation of the Euclidean algorithm avoided a lot of the leaps of faith I made in mine. And simplifying to a lattice is a brilliant way to make the numbers easier.
I think your assumption that the logo always hits a wall perfectly doesn't lose any generality, because even if a logo 'crosses' the wall a bit, it will still bounce back on the next frame, making the setup equivalent to a lattice one tile longer. You can confirm this a bit with the simulation I made for my video (which I believe I can't link without my comment being auto-removed by CZcams). If you use the default settings but set the X speed to 7 so that crossing a wall is more obvious, you can see that a screen width of anywhere between 395 and 401 leads to the exact same path!
Ahh yes, you're absolutely right! I did all my working out before watching yours, and when you did it as "a bounce is on the first frame when it hits the edge or *passes* the edge" I was jealous that you didn't have to make that assumption! And I think you're right that no generality is lost.
Link is in the description to this video for those who want to watch, it's great!
When I was a little nerdling (3rd form, if I recall correctly), it was in the days before VCR's, to say nothing of DVD's. But I wondered about this exact problem, thinking in terms of a billiard table with m diamonds on one edge and n on another. Bless my mathematics teacher! She showed me the argument involving modular arithmetic, and taught me the _extended_ Euclidean algorithm. I think I managed then to prove most of the results in your video. I'd credit Mrs Smith for the fact that I'm a (semi-retired, applied) mathematician today.
Thanks for sharing that story, can't beat a good maths teacher 🙂
exactly, was thinking the whole video about the eea and the linear combination of (s,t) that it gives, which is the solution to the problem
Alex doing a 45 minute deep dive into the math of the DVD screensaver? Ohh god yes, I am so here for this.
What I find so interesting about this video is the way you use mathematics to tackle this issue. I expected that someone had dumped the firmware code of an old DVD player (I bet you could probably find an old Apex brand DVD player firmware somewhere online, the Apex players were very interesting products that would play basically anything you put on a disc no matter what format it was in, ignoring region locks and other things they were 'supposed to' not do) and you'd be going through their actual algorithm. That's just how I'd tackle it as a software person.
🎶 "Still waiiiting for the DVD looogooo / to hit the corner of my TVvvv" 🎶
Haha I was thinking the same thing
Jazz Emu immediately entered my head too!
„My eyes are now crrrrrispy to the touch.“ 🎵
How tf does this channel only has 43K subscribers? This channel is criminally underrated
i know right? this is some 3blue1brown level stuff
It just got one more!
Dude, VHS to DVD was a massive improvement. 1080p to 4k is barely noticeable.
dvd to blu ray was way more noticeable imo, maybe because tvs just got better
@@bingxiling9154also because CRT’s have better effective resolution than flat screen displays, so while the jump from VHS to DVD was a bigger jump in quality, the jump from CRT to LCD undid a great deal of that image quality improvement. If you had a top line HD CRT TV, you would have seen a massive improvement when going to DVD from VHS.
This video is going to be a guaranteed hit.
I like the direction the video went, just haven't worked out whether it's the right one yet.
@@KusaneHexakuis that a corner case?
this video is a coprime
Thanks for this. I've always mentally did this with any kind of rectangular grid (e.g. ceiling tiles), (Hi, ADHD!) but I never thought about starting in an arbitrary place, but always at a corner. I knew it always had to end in a corner, but never knew how to predict which of the other three it would be. Now I do!
I always thought that the DVD screensaver would always hit the corner eventually because of what they were designed to do
The purpose of a screensaver is that, to save the screen. The animations that play prevent a static image being shown on a display, by constantly refreshes all of the pixels, thus preventing or delaying burn in, where static images that are displayed for long enough would still be seen when that image wasn't displayed. This was a problem on older TVs, and has come back with OLEDs. Some OLED TVs have features that will shift the image by a few pixels every so often to prevent burn in. So for the DVD screensaver to do this job, it should cover the entire screen, which it would require it to hit the top corner pixels.
However, I might be wrong on that, and the DVD one specifically, or depending on the implementation may not always hit the corner. Or the animation would start in the same place and direction, so it would always hit, whereas the video wonders about some arbitrary 'DVD like' screensaver. I am also only 10 minutes in when writing this, so if it is addressed later, my bad
When you peeled that rectangle off the page I fainted.
Woah, the editing with the stop motion sticky note was slick.
Now THAT'S what I've been wanting from this channel !
The timing of this video is fantastic considering ive just finished a module on elementary number theory in one of my math courses in university, so this is both a lovely way to see it applied, and a nice refresher of the more fundamental ideas. I really love your method of explaining stuff, and it usually complements the more "university" like explanations I usually have, while still being rigorous and in depth enough to not just be a cursory look into the topic that is more common on CZcams
I'm so glad this channel exists. Doing the work that needs done.
You had me at all your DVD acronyms in your intro. Amazing.
I like a lot of the fun wordplay used in this video, you clearly were having fun writing the script!
The editing was top notch!
This is brilliant! Great script, great presentation, great maths! Congratulations!
1:00 This dude is SPITTIN BARS
I've been wondering how to go about solving and lo and behold, this video was recommended to me! What's awesome is that I technically already knew about Bezout's Identity, I just never know how to apply it until now! This video was awesome!! 💯
This guy just brings us nostalgia by presenting childhood math-related curiosities.
12:32 The simplest solution with integer k_1, k_2 for this equation is k_1 = 6, k_2 = 1. 12*6 - 51*1 = 72 - 51 = 21.
P.S: General solution is k_1 = 17n - 11, k_2 = 4n - 3, where n is a integer.
That was an incredible and beautiful exploration, both fascinating and hilarious!
Just had to pause at 28:16 and point out I don't think I have seen anyone motivate the "discovery" of the Euclidean algorithm (with proof to boot) quite so well. And never once mentioning the scary word "algorithm". Thanks for showing another way to teach this algorithm!
spittin bars in the intro AND answering a ton of questions i've never bothered to research... thank you
I love this, applying ultra maths to some minor trivial nostalgia, to reveal beautiful patterns or simplicity. I wonder if the designers of the screensaver had any idea of this maths - it does seem that x and y were set peculiarly to create a long period.
10:26 Here's another way to explain this: When on an edge, the logo is bouncing rather than traveling in a direction. In other words, the logo only visits the edge once, but it visits other nodes twice. So, the points not on the edge are doubled. But there are two edges, so that halves the period. (Note that corners are intersections of edges.) So, it's (1+2(n-2)+1)/2 = n-1
I'm just starting the video, but it is awesome to see that I am not the only crazy person (lol) that wondered about all the variables that influenced the corner alignment of the logo, and if there was an infinite number of guaranteed corner bounces
Still haven't watched the video, but "Is it ergodic?" is the first thing that comes to mind
Exactly. And it is not in general. And if you want it to repeat exactly in a finite time you want nonergodicity and the right initial condition!
CORNER CORNER CORNER CORNER CORNER CORNER COOORNER... (Doug hit the corner)
It's weird that you hate the iphones with "bites taken out of them" because I think they're all top notch.
Nice 👌
Just came from the new dougdoug vid so I stumbled across this at the perfect time
I think in reality, the box speeds up or slows down as it collides with a wall in order to synchronize the collision with a drawframe. It calculations position, realizes theres a collision, calculates collision point, and then moves the box to that collision point. I dont think theres a step then to see how far it moved, and then completing the rest of the motion trajectory to make the movement stay the same length
The reason infinitely many solutions exist to the Diophantine equation: if we are trying to find a and b such that ax+by=c. then we can do the process in the video to get one working solution, then we take the homogenous case. if ax+by=0, then solving is trivial, ax=-by, so find you could use the lcm of x and y, but an example solution (although there are many) could be a=y and b=-x. once you have this solution, notice that you can add it to your original problem without changing anything. if a1 and b1 solve the homogeneous case, then adding any integer multiple of them to the original shouldn't have an effect on the final value, if ax+by=c then ax+by+a1x+b1y=c+0. and simplifying gives (a+a1)x+(b+b1)y=c which is another solution. you can repeat this process by adding in the homogenous case again yeilding another new solution. do this infinitely many times to yeild infinite possible solutions.
1:00 I CANT HANDLE THE WORDPLAY ITS TOO GOOD. JUST BE MY DAD ALREADY.
AH! My Brain! You're talking about graphics with 0,0 at the bottom left. A bunch of time writing software the does graphics makes me think in terms of 0,0 at the upper left with positive y going down any time pixels are in play.
Sorry about that -- you won't believe how many times I changed my mind about this! You can see later in the video my spreadsheet has the coordinates running downwards. In the end, I decided that more people were familiar with the Cartesian Plane and how coordinates work there but I spent a long time deciding! Hope it isn't too distracting and enjoy the video!
Seeing the logo hit the corner is _almost_ as exciting as seeing another video from AnotherRoof in my inbox!
I want to come to your parties! Sounds incredible to go to a party and discuss the maths of whether the DVD logo will hit a corner!
I have never had a video tell me to take a break before. Thank you.
I hope you came back for the good stuff!
Amazing video! I didn’t really understand all the simplifications at the start, but the actual math was explained really well
Off the cuff thoughts, method of treatment is like a specific case of fixed step finite difference with specific (periodic) boundary conditions (and initial conditions) for the motion of a rectangular projectile with perfectly elastic collisions. It is essentially a potentially nonergodic system in general. For certain initial conditions and screen aspect ratios you can have highly localized trajectories. If the ratio of the horizontal and vertical speeds have a rational relationship to the aspect ratio I would expect only a local part of the screen to be covered.
This is a nonergodic system in general. And if you want it to repeat exactly in a finite time you want nonergodicity and the right initial condition! This is like saying the Poincare recurrence time is finite! Which requires the resonance between the x and y degrees of freedom you discovered. Occurs in many nonlinear dynamical systems in mathematics, chemistry and physics. Dynamic billiards are well studied: en.wikipedia.org/wiki/Dynamical_billiards (And using the finite difference approach: en.wikipedia.org/wiki/Arithmetic_billiards), blogs.ams.org/visualinsight/2016/11/15/bunimovich-stadium/.
That video is so well constructed and the content is amazing. Thank you. Do more. ❤️🥰
gonna add a bit of an extra difficulty to the problem.. assume the anchor point is always at the corner of the DVD logo and not the center.
if the logo is at the top left quarter of the screen it is anchored at the top left of the DVD logo and so forth.
this means that the size of the logo greatly affects the point on which it bounces off the edge of the screen.
Just started watching, guessing the first step is gonna be to look at the representation where the logo never bounces, it just passes through the screen into a reflected version of itself, and we make a big grid of these reflections.
This is such an interesting and well made video!!
Sir, what a way to explain. Respect for that and very interesting topics. I also respect the fact that you did most of it manually, even though most people uses manim. Thank you
omg... waiting for it to hit the corner! thank you for this :D
I like the physical "building blocks" that you present the theorems in
Having done the mathematics of Countdown, another good math game deep dive could be the 24 Game, where you have 4 numbers and have to reach 24 via the basic 4 operators. It's a classic for kids, so I'd love to see the a big dive into the maths of it all.
I wonder if there's a simpler way to solve this using the "infinite trees" problem. If you point a laser through a grid of trees from the origin, you're guaranteed to come arbitrarily close to one of the trees, since any angle can be approximated more and more precise fractions. Then maybe you could make alterations in the proof of that to adjust for the starting position on either the x or y intercept. There's probably some technical reason why these aren't similar problems, but the solution to the tree problem would give insight into the solution of this one, provided we allow a tiny bit of imprecision, maybe the caveat being the measly accuracy of human eyes allowing near-corner-hits with some level of allowed variance.
I think you're right! I briefly looked into this while planning my video, but decided against bringing it up as I didn't like the idea of introducing yet another problem, especially when I try to make the videos for a broadish audience. Thanks for watching!
@6:41
“Mathematicians have a name for this type of structure, by the way; a lattice.”
Well, lattice theorists don’t restrict themselves to integer points in the plane or even in any other Euclidean space, so you’re not accessing best terminology. This kind of lattice is better referred to as a Gaussian integer lattice because it’s in a plane, and so the elements of the lattice can be viewed as Gaussian integers (complex numbers with integer real and imaginary parts). In fact, you’re locating your grid so that it’ corner is the zero element of the complex plane, and so it’s better described as a finite initial segment of ‘positive’ cone of the Gaussian integers, and the more general notion is that it’s the ‘positive’ cone of a lattice-ordered group. If you analyze the approach, I expect there are some interesting related results in the theory of lattice-ordered groups with similar arguments, and so that this result you demonstrate will be a special case of such results.
Your argument uses periodic extensions that are still contained in the ‘positive’ cone of the Gaussian integers, so that’s where I’d think someone should look if they want to learn the deeper results.
…
Great video! I was just looking at the euclidean algorithm a few days ago, now i understand it even better! 👍
Literally ur best video
bro, I am thinking about this since I did some crude graphics animations in 320x200 (256 color) VGA graphics. Would a pixel bouncing in 45° fill the screen? What if I add a little bit of randomness? And what do I do if I hit exactly the corner, as seemingly I have to go the way back, rotating by 180°
Where is the Google Sheets version of the spreadsheet?
In certain areas of wireless network research it is common to put devices into a square and let them move about it. One often used model is the "random waypoint model" but this is not a good model as shown in the paper "random waypoint considered harmful". A better model starts at a random point, moving at a random direction at a fixed speed, perfectly reflecting at each wall. Like the subject of the video - assuming a point object. It's easy to show this gives a random distribution in the x coordinate, and a random distribution in the y coordinate. But does it produce a uniform distribution across the square? Clearly not always - if you start on a long diagonal aiming at a corner on that diagonal then you will never leave that diagonal. And some other special cases can be constructed. But does it produce a uniform distribution across the square almost always? If so, or if not, is this a published result? Is this therefore a good model, or should it also be considered harmful?
You are doing the lord's work here my good man.
I did a school math project on this a few months ago
My project was a totally different scope but it was interesting to see how closely our ideas aligned
Great video
This is a really great video. Nice work here
that springs back memories of learning how to chunk multithreaded matrix operations
When did you upgrade your video editing skills 😮. This feels like a big step up. Great video in general.
I believe DVDs are based on technology from the french show Des chiffres et des lettres
i love your sense of humor
Came for the content, stayed for the puns
My answers at the start is it’s not necessarily going to hit the corner. It will either hit the corner or be a repeating circuit of some sort. Though in practicality I imagine it’s basically always gonna be in corner mode.
Where was this video when I was learning discrete math last semester, it would have helped so much 😭
This video reminds me of the genius pannenkoek's Watch for Rolling Rocks in 0.5 A Presses "But first, we need to talk about parallel universes" SM64 video.
"But first, we have to talk about parallel universes"
The a level further pure 2 syllabus tells you how to solve this type of diophantine equation, nice to see some fun applications with it.
I wish I watched this video during my discrete math class, this actually makes sense
All the most fun mathematics comes from asking a silly question and finding a serious answer
I solved this problem nefore, although it was not the DVD screensaver but another screensaver, that made me think about this.
8:16 Another way to solve the bouncing problem is by flipping the position instead of the direction. In this case, you should flip the position around the center of the board. Equivalently, you can flip the board
Playing with an oled screen and Arduino I ended coding something like this, but I didn’t move it more pixels, just increased the refresh speed, when reached certain position it reverses one axis .
15:12 That definition works for natural numbers. However, there's no largest common divisor of 0 and 0 by the usual comparison. There is if we compare by divisibility or in my way. (The latter is like comparing by absolute value except 0 is larger than all other numbers.) These methods of comparison aren't exactly orderings of integer. In them, n and -n are considered the same. So, you'd need to define it as the nonnegative one (or in another similar way)
quick question, do solutions exist for x*k1 + y*k2 = any common divisor of (x,y)? You gave a reason that went like:
if gcd(x,y) = d, then we can write the Diophantine equation x*k1 + y*k2 = m as d(x/d * k1 + y/d * k2) = m and so if m isn't a multiple of d then no solutions exist. Can we just use the same argument for any common divisor of x,y? Thus if m is a multiple of any common divisor of x,y then a solution to x*k1 + y*k2 = m exists?
No, think about the 12p+8q=2 case... If there were any such p and q, then 4 (the gcd) would divide 2 (your m), and it doesn't.
10:06 missed opportunity for the Mario file select music
42:24 so satisfying
1:00 Just a lyrical genius
I actually coded a clock that bounced like the dvd logo using JS, though due to a bug, I accidently made it hit only the bottom corners and the top center.
In a real sense, there's only 1 direction. If the path starts in the negative direction, just flip the whole starting point in X (both position and vector).
The euclidean algorithm explanation was a bit cumbursome and backwards. Usually people start by saying that using the algorithm, you can find the gcd(a,b), and only then people explain, that in the process we get a solution for an equation.
I had to explain all the little facts about polynomials today, and it stood out to me, that number theory and polynomials are awfully similar. Then I remembered about the Rieman hypothesis and it all made sense
How does this work with CRT monitors that dont have pixels the same way and are not uniform?
thank you for your effort and this vid ❤❤
In graphics programming the vertical axis almost always increases as you go downwards, rather than upwards like the math convention. This is probably because the horizontal lines of CRT displays are drawn one at a time starting from the top, so the top line is line 0.
So what I'm saying is the DVD Logo thinks your graph is upside down
Hello, thanks for watching! I've responded to a previous comment about this but yeah, I went back and forth on which direction to label the y-axis. Initially I had it the graphical direction but eventually settled on the mathematical convention as I thought that was more intuitive for more viewers. Luckily it doesn't matter, but it made some parts tricky as all my early notes had it the other way around!
@@AnotherRoof Oh yeah either way is fine I just wanted to joke about it
I understand that you just went and had fun with this. But the problem isn't nearly as complicated since screens aren't arbitrarily shaped and sized.
I actually thought you where going to go towards how they would have guaranteed that the logo covers as much surface as possible. Because as a screensaver in the era of CRT it's main purpose is a burnin countermeasure. And you eventually did show the coprime behaviour near the end really quickly.
Beautiful! Thank you
Another great video from Another Roof.
This is similar to Euclid’s orchard problem which is equivalent to solutions of Pythagrean triples or equivalent to finding all rational points of a circle a^2 + b^2 = c^2 (a/c)^2 + (b/c)^2 = 1. These rational solutions and all their multiples can be derived from Hilbert’s theorem 90. The corners of the square with length x and width y have rational slope x/y. If the starting point chosen is a multiple to the rational solution described by corner, the logo will hit the corner.
Though this is algebraic, there is a some periodicity appearing in it that is really difficult to explain in general at least coming from the algebraic side.
Actually it's not if one knows how to relate things and substitute. What do I mean by this? We can use the slope-intercept of a line formula y = mx+b where the slope m is defined as rise/run (y2-y1)/(x2-x1) and b is the y-intercept. This is a basic algebraic linear equation. We can the rewrite the slope formula as dy/dx.
Now, we can take the basic sine and cosine functions from their right triangle definitions: sine = opp/hyp and cosine = adj / hyp. We can use the relationship of this right triangle in standard form where the angle theta is the angle that is between the line y = mx+b and the +x-axis. With that we can see that within the slope formula dy/dx is exactly equivalent to sin(t)/cos(t). In other words dy = sin(t) and dx = cos(t). Therefore the slope of a linear equation is equivalent to tan(t). With that we can substitute and rewrite the slope-intercept form of a line as y = (sin(t)/cos(t))*x + b or simply y = x*tan(t) + b.
This is why we are able to see periodicity within the linear relationships.
Also for any number N that is rotated by either +/- 180 degrees or +/- PI radians it is the same exact thing as multiplying it by -1. Why? Well if we multiply 1 by -1 we get -1. What is the dot product of 180 degrees? It is -1. And arccos(-1) is either PI radians or 180 degrees.
There's more to it than just that. Just from the simple expression of 1+1=2 which is basic algebraic arithmetic, this simple expression is in fact a linear transformation. This transformation of adding one to itself without realizing it is in fact the unit circle with its center located at the point (1,0). If we take the general definition of an arbitrary circle (X-h)^2 + (Y-k^2) = r^2 where (X,Y) is any point on its circumference, (h,k) is its center point, and r is its radius. We can see that this is a specialized version of the Pythagorean Theorem A^2 + B^2 = C^2. The definition of the unit circle located at the origin is X^2 + Y^2 = 1. The only difference here with the simple expression of 1+1 = 2 is that the unit circle is translated 1 unit to the right with its center at (1,0). If we take this expression and substitute it into the equation of the circle we end up with this: (X-1)^2 + (Y-0)^2 = 1. We can then take this and use algebra to simplify it and to solve for it in terms of Y.
(x-1)^2 +y^2 = 1
x^2 - 2x + 1 + y^2 = 1
- 1 -1
x^2 - 2x +y^2 = 0
-x^2 + 2x = -x^2 + 2x
y^2 = -x^2 + 2x
sqrt(y^2) = sqrt(-x^2 + 2x)
Oh wait a minute we have the square root of a negative number... Where did that come from? Yup complex numbers are embedded within 1+1 = 2. Why? Because the multiplication of i is a rotation of 90 degrees or PI/2 radians. Euler's formula and identity shows this in greater detail!
In truth, all of these properties aren't just embedded within 1+1 = 2. They are embedded within the numbers themselves.
If we take the expression or equation y = x which is an equivalence or identity expression which can be written as the function f(x) = x, this is still a linear equation and there is still a linear relationship of any given number x with itself. This line has a slope of 1, and a y-intercept of 0. A slope of 1 is the same as 1 = tan(t) which is 45 degrees or PI/4 radians. All fields of mathematics are related. It doesn't matter if it's Algebra, Geometry, Trigonometry, Calculus, Probability, Statistics, even Logic or Boolean Algebra. Within Boolean Algebra the OR gate is relative to addition and the AND gate is relative to multiplication.
When you get into circuitry with the context or abstraction of logic gates and we use boolean algebra we can simplify things through the use of either The Product of Sums or the Sums of Products. More than just that, but Boolean Algebra and Logic itself has a direct connection with Log2 arithmetic. And Logarithms are Algebraic. Even our understanding of physics, and chemistry is rooted within mathematics. Why and how is everything related? Simply because of motion which is a transformation. Neither Energy or Matter can be created or destroyed they can only be transferred or transformed. There's also a direct connection between these, number and group theory, information theory, and fractal geometry.
It may not be evident at first but for every linear transformation (moving along a straight line), there is always an implied rotation. This is something that isn't necessarily taught in schools or universities, however it is an underlying pattern that I've recognized that is always present. When you walk a straight path, your legs are swinging at an angle within the socket of your hip joint. When a bird flies through the sky and their wings are flapping in the air, they are rotating. It is to my understanding that you can not have linear transformations without some form of rotation and vice versa. They are interdependent of each other. Once you have one, you have the other. Otherwise we wouldn't be able to have reflections or symmetry.
Just some food for thought! There is periodicity in y = x, never mind a + b = c. If there was no periodicity then there would be no identity. Just wanted to shed some light into the matter because it is quite sound. John 1:1-5, Genesis 1:1-5
@@skilz8098 Euclid’s orchard is viewing a square lattice of rational points from the origin.
The angle θ of the slope as described is the inverse tangent since tan θ = opposite/hypothenuse.
The rotation is given by exp(iθ) with angle θ in radians. The dot product of two perpendicular vectors is always zero.
1+1 = 2 is a linear transformation but I don’t find its reoccurring mentioning here too relevant. It is not standard to have the origin not at (0,0) when considering coordinates on a plane. It will shift any calculation if it’s not. The square root isn’t additive so this additional shift doesn’t derive it. It is easier to consider the complex numbers on the plane in their exponential form.
Integers are a subset of the reals which is a subset of the complex numbers. Complex numbers can be written in exponential form z = r*exp(iθ) which is a succinct and useful way to describe the polar vectors that describe each point of the lattice in question.
All mathematical fields are related and there are theorems which describe some of the relationships. Applied mathematics does solve many problems such as finding when exactly the DVD logo will hit the corner.
Circular motion does propel most real world things forward. I think there are groups which are understood through symmetry that have faithfully representations as the orthogonal group which describes rotations but I’m not sure if it holds in general.
It was something to think about and ponder. Functional equations do equal themselves and this is sometimes called their identity. You are very faithful.
I was thinking more of Langlands program which equates periodic functions to algebraic expressions in a general way but was not coming up with anything then. Euler’s formula exp(ix) = cos(x) + i*sin(x), roots of unity, and their Fourier series is more of what I was after.
@@Jaylooker Nicely stated. Yet it's the purity of math and the relationships of numbers that intrigues me. Especially when we consider how a simple equation or expression can generate an infinite complex structure with amazing beauty such as the Mandelbrot Set, and that's just the tip of the iceberg.
@@skilz8098 Then study math and do some of the practice problems. Studying Fourier analysis and harmonic analysis may interest you because of the periodic functions they describe.
@@Jaylooker I've written my own 3D Graphics / Physics Simulation in C++ using DirectX 10-11 / OpenGL 3.x. I started to learn Vulkan a bit too. I even worked on doing a 6502 NES emulator. I'm quite familiar with the math and physics! I've done a little bit of 3D Audio Processing as well.
As a DVD logo i can confirm i like it when i bounce into the corner
9:40 wow… I had no idea that the DVD Logo had parallel universes, just like Super Mario 64. I wonder which came first? 🤔
At about 10:00 I noticed what other problem we are turning this into
E: I was wrong, we didnt go into infinite screen sizes
I wonder if any DVD firmware programmer SOMEHOW had too much time on their hand and implemented "subpixels" or letting the DVD logo move in "fractional numbers". That would have thrown EVERY researcher of this phenomenon for a loop.
Would you consider not having background music to make it easier for us with poor hearing?
There may be a motivation for having background sound and i would curiosity hear it.