So I was hesitating to write how much I like this channel since everybody is telling you that anyway, but other creators keep persuading me that it is still important for you to hear these words. And you deserve all the praise you can get. I have studied a very math-heavy field in college (physics), so most of the educational channels on math on youtube don't really cut it for me in the sense that I either already know the topics they cover, or they don't go into enough detail or it's plain boring, but not these series though. Every video is well written, deep and on an interesting topic, and you explain everything in such a way that even schoolchildren would understand it perfectly. And then you also engage with the audience in the most thought and curiosity provoking way possible! You have talent for this stuff and please continue making these videos! This channel is fantastic!
You eloquently put what I have been trying to word. "...math-heavy field in college (physics), so most of the educational channels on math on youtube don't really cut it for me in the sense that I either already know the topics they cover, or they don't go into enough detail or it's plain boring, but not these series though."
I don't understand your comment. The proof is not trivial, so I'll give you the benefit of the doubt and presume you're not saying it is. She never said it was trivial, but rather referred to it as a challenge problem.
+Steve's Mathy Stuff He was quoting a sentence that it is quite often found in math books. Sometimes the authors state it even if the proof is not easy at all, but simply because... they cannot be bothered :) The intent was totally sarcastic then.
OK. I have encountered the statement in texts, but only when the proof was trivial but tedious. Now I have to try to find a non-tedious proof for the small triangle lemma.
Dear Dr. Houston-Edwards, we need more people like you on Earth, or perhaps we need more visibility for educators like yourself. Thank you for putting forth the time and effort to share your love of mathematics, as well as to the the rest of the crew. Thank you.
In your proof that planar graphs have Euler characteristic 2, I think you missed a step. Since we're allowing loops on a single vertex, we need to consider whether the edge we pick is a loop or not. If it's not, the logic works fine -- contraction of that edge removes one edge and one node, and we're fine. But if it's a loop, contraction of that edge removes one edge *and one face*! This is still fine (faces and edges can cancel out too), but the argument is subtly different between the two cases. Personally, I would have focused strictly on straight-line planar graphs, which can't have loops to begin with. The base case is just as clean if not cleaner. Barring that, we could show that every planar graph with loops can be reduced to one with the same Euler characteristic but without loops; the proof would proceed exactly as before.
Jonathan Castello Yeah, the error became glaring when it was claimed any such polygon could be broken into small triangles. Triangles have straight edges. Anything curved, such as a loop, creates a contradiction. Or we can even go so far as to call the contradiction an actual falsification. At least a falsification of the way it was presented, which may be the only problem. Words have meaning, even in maths.
@Snatch n Grab: Ah, no, polygons always have straight edges. There's no problem there. Polygons are a specific kind of planar graph, and the Euler characteristic of *any* planar graph is 2, whether or not it has straight edges. The problem is one of rigor, not accuracy. All of the theorems presented are true.
There’s also the fact that contracting an edge of a triangle removes one node, two edges and one face which also ends up working fine but is another case that was missed.
at 3:40, if you contract an edge that is part of a triangle, it removes the face but also merges two edges leaving the Euler characteristic the same but you missed that in the video. minor detail but it needed pointing out
3:25 "When we contacted the edge we removed one edge and one vertex so the Euler characteristic didn't change." This assumes there is only 1 edge between those two vertices. In the case where there are k edges between the vertices, then you remove k edges, 1 vertex, and k-1 faces. However, since 1-k+(k-1)=0 the Euler characteristic is still unchanged.
I saw this popup on my chrome app and I had my stoner friends over and I was acted like it was no biggo but you know, I love this show and lööve it when you upload, couldn't wait till they left, checked their busses and everything 10 times just to see this, now I'm stoned too so here we go
6:14 Assume that two of the points of the triangle lie on a line of slope m. Then they are (m^2)+1 units apart. The third point can go either one of the two parallel lines closest to the line with the original two points. A little geometry shows that both of these lines are exactly 1/((m^2)+1) units away from the original, so we have a triangle with base (m^2)+1 and height 1/((m^2)+1), which just has area 1/((m^2)+1) * ((m^2)+1) / 2 = 1/2. Also, awesome video thanks for sharing!
not really sure where you’re getting (m^2)+1 from if you take for example the points (0,0) and (4,3), then there are no other points on the line segment connecting them, which has a slope of 3/4 but those two points are a distant of 5 apart, not (4/3)^2+1
If maths fails you, you could try archimedes. Extend the surface in the third dimension to give a volume. Submerge it in a bath. Measure the volume of water displaced and divide by the thickness. Run naked down the street shouting eureka (optional). Works for any shape.
I am really glad that you are doing this channel. People need to have a better understanding of what mathematics is about. That said, you forgot to argue/mention that the graph obtained by contracting an edge is still planar.
1:43 *connected Also, I enjoy more the other proof. We prove the formula for rectangles, then for right triangles, then for any triangles, and then for any polygon using triangulation
Around 3:35 - for a graph like a triangle you can't merge two vertices without also destroying a face. Of course the Euler characteristic doesn't change because you also merged two edges into one, but it is not obvious (at least for me) why that would always be the case. Hence, why when every pair of connected vertices destroys a face when merged, it must also be the case that exactly one pair of edges is also merged? Is the triangle the only case?
3:28 This proof is wrong. 1. She assumes no faces are affected by the collapsing of an edge, which can happen if you pick a different one from her example graph. 2. She does not use the fact that the graph is planer, so in theory this holds for all graphs.
1. If you pick one of the sides of the triangle to be removed, then the triangle collapses and the number of faces reduces by one. But, not only are you removing one edge, but the collapse leads to two edges becoming one, so one EXTRA edge is inadvertently lost in the process. So the formula continues to hold! 2. Good point. I don't know how this issue is resolved.
@@jpchaitu I am not sure if my reasoning is correct, but I am thinking that in case of nonplanar graphs, you wouldn't start from n=1 (you can't generate a nonplanar graph with 1 vertex) but with n= 5 ( I believe the simplest nonplanar graphs have 5 vertices). In that case, you would see that the Euler's characteristic is not 2 so the theorem doesn't hold for nonplanar graphs.
@Hassan Akhtar Reading my commen back, 2 does not make sense. But I still think 1 does. For example, if you contract an edge in a triangle, the number of faces drops from 2 to 1.
Showing that the triangles in 6:14 all have the same area is quite simple, because you can turn them into one another using transformations that don't change the area of the object. These transformations are moving, turning and shearing. First, you move and turn the triangle on the top left so that one it's sides exactly matches one of the other two. Let's call this side a, the one you just used to align the triangles. After that, shear the point that is NOT a vertex connected to a so that it matches the triangle we are looking for (shearing is done by moving the vertex or corner parallel to an edge that it is not connected to). The fact that turning and moving doesn't change the area of the triangle is easy, because you can either just shift your 'camera' again to match the original triangle, or show that the formula for the area of a triangle still holds true. Shearing is a bit more trickier, but can be done graphically. It's probably easier to show it using a square. Take one side of the square, call it a, for example. The side opposite of a is the one we want to shear, let's call it c. Now, shearing would be done by moving c parallel to a. Draw a new c' that is the sheared version of the edge c you want to have, and draw the square using c' over the one using c, so you have to overlapping squares with one shared edge, a. Notice something? The difference between the two squares is visible as two triangles. If you were precise enough with your drawing, the two triangles are the exact same, they're just flipped. This means that you can actually visualise shearing as taking one triangle away on one side and adding the exact same triangle back on on the other side, meaning that you didn't change the net area; you just subtracted and added the exact same area on the original area.
3:38 correct me if I am wrong but aren't you also missing the possible case where an edge, two vertices and a face is contracted also preserving the relationship?
I know that there are easier solutions (I found one myself), but I want to share this overkill-solution using Minkowski's lattice point theorem: W.l.o.g. we may assume coordinates, such that in the triangle ABC A=(0|0). What I want to do first is noting that the area of a lattice-point-triangle is a multiple of 1/2. This can be shown by first doubling it to a parallelogram and then slicing and shifting to make it a rectangle. Now, if the triangle has an area bigger than 1/2, its area must be at least 1. Were doing the following: First, we reflect the triangle at the midpoint of AB yielding C'. Then we reflect this triangle at the midpoint of AC' yielding B'. Since the triangles ABC, AC'B and AB'C' are congruent, the angles CAB, BAC' and C'AB' add up to 180°, hence C,A and B' are on one line and |CA|=|B'A|. Therefore, B' and C are reflections of each other at A. With this in mind, we can reflect the quadrilateral CB'C'B at A, which gives (together with this quadrilateral) a convex hexagon of area at least 6 (since it consists of 6 triangles) symmetric around A. If we now scale this down to a similar hexagon of area 5>4, this does not contain any of the original vertex points. By the lattice point theorem, this hexagon contains at least one lattice point apart from A. Hence, at least one of the six triangles contains a nottrivial lattice point. Now we prove that all six triangles (hence the original one) contain a lattice point: Since the mid of AB is the arithmetic mean of two integers, its coordinates are multiples of 1/2. Reflecting a lattice point at a point of which the coordinates are a multiple of 1/2 will also yield a lattice point, because (a,b)+2(x/2-a,y/2-b)=(x-a,y-b) hence this applies also to the reflected points. Reflecting back we get a lattice point in every triangle.
If you think this is interesting, look up the shoelace formula. It also allows you to easily calculate the area of a polygon, but it doesn't even need integer coordinates! It works on any arbitrary polygon and is so simple an 8 year old could apply it. If you look closely, you'll see that it uses similar principles.
I have used the fact that the 2*area of a polygon is the sum of the cross product (not the magnitude of the cross product) of the vectors to each successive vertices around the perimeter of the polygon closing with the last vertices to the first in a counterclockwise direction. This of course works for non integers. It seems it would be trivial to use this to prove that for integer points this sum simplifies to Picks theorem shown in this video.
For any triangle that does not have any integer lattice points inside it, so base and height will always be 1 each. Area = 1/2 * base * height = 1/2 * 1 * 1 = 1/2
Nice! I have two remarks about all this. [REVISION: 3 remarks.] 1. At around 1:40 - 1:50 - Not ****quite**** (I'm making a pinch gesture with thumb and forefinger) true as you've stated it (for the plane, of course). Yes, that formula will always give 2 for a *connected* graph. For a graph of p mutually disconnected pieces, the formula is: v - e + f - p = 1 . . . an extension of Euler's formula which is equally beautiful, I believe, as the original form. This version also applies to the null graph, with v = e = p = 0, f = 1 (default face consisting of the whole plane). 2. In proving the formula for the Euler characteristic, it seems to me that you have considerably more work to do than you've shown here. I would say you have 3 steps; namely, to show that: A. It's true for the base case [which you've done, although, I would have started with a lone vertex, (v,e,f) = (1,0,0)] B. Adding any single, or minimal set, of elements [and there are multiple ways of doing that], preserves the formula C. Any finite, connected graph can be constructed this way. You evidently have more cards here than you're showing, given the constraints of time, and of keeping the viewer-attention train from getting sidetracked; but can you fill in some gaps here, and explain how to prove that your construction method can build any connected planar graph? New, 3rd remark. 3. In a recent comment thread, in my back-and-forth with Czeckie, the starting comment being by Ruben, it has been established that your method of proof falls short, as it fails to cover some cases, which Czeckie has supplied. There are any number of triangles, which, taken as the polygon whose area is to be subjected to Pick's Theorem, cannot be tesselated into "small triangles" that satisfy your conditions as you've illustrated them, but can be so tesselated, taking the conditions as you've stated them. Namely, when a "small triangle" has a unit grid segment as one side (this was true of all your illustrated examples), it is easily shown that its area = ½. [Call this special case a "small grid-segment triangle"] But when a "small triangle" doesn't have a unit grid segment as one side, it is far from easily shown. And such a triangle can't be partitioned into small grid-segment triangles. A simple example (due to Czeckie) of a polygon which can't be tesselated into small grid-segment triangles is the triangle: (0,0), (1,0), (2,3) . . . . i=1, b=3, A = i + ½b - 1 = 3/2 Two examples Czeckie gives of small triangles which aren't small grid-segment triangles are: (0,0), (1,1), (3,2) . . . . i=0, b=3, A = i + ½b - 1 = ½ (0,0), (9,4), (20,9) . . . i=0, b=3, A = i + ½b - 1 = ½ With infinitely many possible triangles such as these last two, which touch or enclose only the 3 grid points at their vertices, and so, fit the definition of "small triangle," how do you show that Pick's Theorem holds for them all?
about the 3rd remark. I don't think the proof is wrong. The examples I've provided were to show that your "small grid-segment triangle" is insufficient. Your last sentence is the main thing, but Kelsey is aware this is the thing that needs to be proved. She stated it that way. And I don't know the answer and it pains me greatly. I'm sweeping this comment section up and down an haven't find any correct proof. My own attempts are not working. I can prove, that any grid triangle with area 0.5 is a small triangle, but it is the other direction what we need for proving the Pick's theorem.
Well, yes, I'll concede that the proof is not wrong; but it, or her presentation of it at least, is incomplete; and I see that you, like I, have been unable to seal off the proof of that lemma.
I have! I don't feel like writing down all the details, but basically what's needed is to enclose the small triangle into a rectangle (like this imgur.com/WZdDDw2) and the cut out blue parts will be right triangles or rectangles. You can prove pick's theorem for these two shapes. Then the true area of the rectangle is 0.5 greater than that of blue bits. I'm just leaving it here as a hint/program. I'm sure you are curious enough to supply the details :)
Can you extrapolate this to find determine the area of a circle (as you take the density of the lattice field to infinity... or the size of your object if you prefer). I'd be curious if that works.
3:45 and what about faces? (I know, but you didn't say it) by contracting two vertices that outline a face with two edges, the result is one less face and vertex, and two less edges, net zero change.
An endless hallway *would* ensure sufficient distance between greenscreen and subject to avoid the green light reflecting back on the subject. Of course, since the end of an endless hallway is infinitely far away, that makes lighting it rather challenging.
No greenscreen hair usually means excellent lighting. Or an endless hallway. (I'd like to see the proof on being able to construct an endless hallway in finite time.)
Yes, supertasks allow you, in the abstract, to do an infinite amount of work in finite time. Math doesn't have any issues with that, but physics certainly does. ;)
With the induction proof, doesn't that rely on the contracted edge not also changing the number of faces? What if the graph of N+1 vertices had no vertices that could be contracted without changing the number of faces?
It may be crucial to add the following to the induction step: since there are at least 2 vertices, there exists an edge that is not a loop; when contracting the two vertices at the end of this edge, any other parallel edges are retained as loops - they are not removed from the graph. otherwise things aren't correct.
When stating the Euler formula, you forgot to mention that the planar graph must be connected. For example, consider a graph composed of 2 verticies and no edges. This has a characteristic of 3.
In your proof that planar graphs have Euler characteristic 2, i think you missed the step that all graphs having a Euler char. of 2 are planar graphs. The reverse direction is missing to be shown? Without that, the question could be, if other non planar graphs could have also E. char of 2 ? I might miss something here, but someone please correct me if I am wrong.
0:40 going a bit over the moon mentioning "trigonometry". Segmentation is more than enough. Without pick's, you circumscribe the problematic spikes with parallelograms (A rectangle is a parallelogram) and those inscribed triangles are half the area of their circumscribed parallelograms! Then the interior is only made of simple rectangles you can add. It's still tedious though. You can also use the area of a triangle when it's a bit tougher. You can even use it everywhere!
Not all planar graphs have Euler's Characteristic 2, the theorem only holds for connected graphs. for example the first graph you showed, you can split it in the middle to get 2 k3 s , they have the same number of edges, and faces but one more vertex.
The more general formula for planar graphs is v - e + f - p = 1 where (v,e,f) = (vertices, edges, faces) , as before, and p = number of mutually disconnected pieces For the usual case of a single connected graph, p=1, and you get the form she showed.
ffggddss that is true, and the poof is by looking at each connected part of the graph, summing up the equations and subtracting the number of additional tines the infinite face was counted
ffggddss that is actually incorrect, the formula turns out to be v - e + f + p - 1 = 2p you can check it, I checked yours, which Turned out to be false
The demonstration at about 3:30 does take into account the number of faces when reducing the number of vertices as if F was meaningless: it is always a sign something is wrong when you don't take into account one variable. So here is the counter example to the proof: how do you reduce a triangle? In this case, you remove 1 vertex, 2 edges, and 1 face. Ok, Euler formula still valid but the demonstration is not.
Once you know small triangles have area 1/2, just add up all their interior angles to find out how many there are: 360 degrees per interior point, plus about 180 degrees per point on the boundary, but you need to subtract 360 degrees because you went around once! Now divide by 180 degrees to get the number of small triangles and multiply by 1/2 to get the total area. Much more elegant than all that algebraic manipulation shown in the video.
What a coincidence! I am taking a course right now about lattice polytopes and Ehrhart theory, and Pick's theorem was used as a motivating example at the beginning of the course. Get out of my brain, Infinite Series!
Hey I just found out that over at Space Time they set up a reddit forum. I was hoping that one will be set up for Infinite series, as I would be very active on that forum. I love the open-minded culture and community that the PBS videos have currently. I would love to throw my ideas about dividing by zero, infinities/infinitesimals, and the MUH at the diehard Infinite Series community. Any super-fans here agree?
0:30 It seems pretty obvious to me that the worst one needs to do for that shape is divide a bunch of rectangles by 2. Even the acute angled bits can be described as one such half-rectangle minus another. The easiest manner of getting the area probably involves an averaging between squares filled and squares "touched" (with some probable counting shenanigans around acute angles and multiply touched squares). 4:50 Not quite what I was expecting, but it looks familiar. It likely works out to more simply describe the minor mess I was thinking of earlier (especially considering the division by two). 6:15 Yeah, accidentally did that while staring at the sharper acute angles about the first polygon (n*m/2 - n*(m-1)/2 = 1/2). 6:47 *Oh.*
I have a question for the Pi episode. Can we prove that there can exist at least one kind of number system where pi does work like it does in our number system? With respect to value, or relationship with the other components of mathematics ?
6:23 "It's always possible to do this." Why? I don't see any obvious reason this should be true. As a matter of fact, i have an example for which it seems to be impossible to do this: Take a 4x4 grid of points and connect points (0,0), (3,2) and (2,3) to form a triangle. How can you cut this figure into "small triangles"? It is worth noting that the ultimate theorem still holds.
The plane are all 2D pairs of real numbers, so all ar eof the form (a,b) with a,b being any real numbers. If you only allow integes for a and b, you get the integer lattice
didn't finish the challenge yet , next week an exam but : i picked a three different point , one of them (0,0) the other are random with the condition of the Y coordinates are strictly positive because the other case is already treated (same height +same base => 1/2); the proof is to suppose that the area is 1/2 and there is a point inside the triangle with an integer coordinates which lead to - the area of the initial triangle is strictly greater than 1/2 which is an absurd using 3 inequalities that describe the position of a random point inside the triangle relatively to each side + and knowing that the area of the triangle X2.Y3 - Y2.X3 = 1 where (X2,Y2) , (X3,Y3) are the coordinates of the other edges of the triangle
It is not exactly hard as a triangle all has the base and height of 1 (each small triangle is the result of connecting the dots just beside it) So, the area is (1/2)(1)(1) = 1/2
The proof of the challenge question. Are all small triangles (triangles whose interior and edges contain at most three points) necessarily or area 1/2? First, consider a triangle drawn on a grid. For simplicity and without loss of generality, we will assume the base of the triangle is made up of the points (0,0), and (0, 1). A small triangle can be found by simply drawing the remaining to sides so that they intersect on a vertex at some point (1, y) where y is positive (once again for simplicity and without loss of generality). Any triangle will have a base of one and a height of one. So the triangle will have area 1/2. Consider the same base, but a different point drawn further in the grid (x > 1). For example, for x = 2, the slope of the line that makes up the edge between (2, n) and (0,0) would be (n+1)/2 for some integer n. The function that defines this line is f(x) = (n+1)x/2 or x(n/2 + 1/2). The second line between (0, 1) (2, n) would be x(n/2). When x = 1, the distance along y between these lines is (n/2 + 1/2) - (n/2) = 1/2. Now consider two possibilities. Suppose n is even. Then n/2 + 1/2 must lie exactly 1/2 unit from an integer point in the column of points x = 1. This means that the other line must lie upon that point. Therefore if n is even, the triangle is not small. Now suppose n is odd. Then n/2 + 1/2 must be an integer. Therefore the triangle is not small. So no small triangle can have a third point lie upon x = 2. A similar argument can be used for x = k where k is an integer. A further note is that pick's theorem works for any figure that has points whose coordinates are rational. For that, you can simply scale the grid by k where k is the LCD of all points in the graph. The area of each small triangle will be 1/2k. This theorem cannot be extended to the reals (or at least I can't think of a why to do it).
This isn't a question about this video, but a different math question Is it possible to have a truly random number generator where one would never be able to state the probabilities of what the next number could be?
testpage That gives me a number between 1 and whatever number I choose, with an equal likelihood of each number. I know the probability of each number. I want to know if one could exist where the probability could not be known.
If you randomized the probability of any particular number for every new number, you get the same result as a normal random number generator. Just like if you randomly picked and flipped two oppositely weighted coins; the end result will be the same. If the probability is randomized and it keeps that same probability for every new number, yes, you could do this with discrete numbers between 0 and 1, but after enough numbers you could figure out the current probability.
AltisiaK Atmospheric noise is non deterministic, but it still gives an even probability for every number. I can write a formula to find the odds for what my result will be. I'm looking for a random number generator where the result is completely unpredictable. (Note: I'm not literally looking for one, I'm just curious if such a thing could mathematically exist)
Yes, it is possible. The dissection here is such that we need to use all of the dots. You can do it however you like. Always connect a point to some other two points that already are adjacent to some edge. And just continue. As long as there is a triangle that contains a grid point in it's interior or somewhere at the perimeter except for its vertices, you can use the point to dissect the said triangle. At some point, you will end up with only "small triangles".
Thank you. Your proposed method of triangularizing is not complete though. It is possible that there is a shape that has no interor point and all of its points are vertices (not contained in an edge). Sometimes you get shapes where it is not possible to pick a random point and then connect it to some other two points that already are adjacent to some edge. (example: In a non-convex quadrilateral one cannot pick one of the pointy ends to construct a small triangle with your method). Intuitively the statement is obvious. I however was unable to strictly prove it and/or come up with an algorithm.
6:15 Basically: This portion of the proof is left to the student as an exercise. Ah, and here I'd thought I'd never think of that phrase again. Well, at least in this case it's for fun, not a grade.
Celso Rosa pretty much. Most computer graphics break everything into triangles and them use projection to map anything 3D to 2D. Different algorithms them fill in pixels. Simplest way is to fill in all pixels strictly within triangles, but this creates jagged and rough edges (which things like antialiasing help with)
In the induction proof, the argument that contracting an edge will result in the loss of an edge and a vertex is flawed, your own picture shows why this argument is not universally true, since I have a counter-example showing that you can select a random edge to contract and it will not result into losing just an edge and a vertex. If you contract one of the top vertexes you'll lose 2 edges, 1 vertex and 1 face. The relation is maintained, but you can't say that by contracting and edge the euler caracteristic will not change because you only lose an edge and a vertex, because that's not always the case, as shown in the example above. I mean, the relation still holds, but you can't say that contracting an edge will always lead to the loss of just an edge and a vertex and use it in an induction proof. I love this channel, and by no means I want to sound harsh or anything like that. I'm just pointing out the issue with the argument used in the induction proof. Cheers from Brazil.
This method is actually not the simplest for a computer. You have to count the interior vertices, which isn't trivial, it's not O(n). If I'm correct, the area of an arbitrary polygon can be computed as follows, in O(n) with n being the number of vertices. Pick any point p on the plane. Form all n triangles with p and each ordered edge of the polygon taken clockwise. Blindly sum the areas of those triangles, if the triangle is counter clockwise its area is negative.
For this to work, wouldn't the polygon need to be convex and p need to be inside the shape? Just curious cause I was searching for a solution to this problem some time ago.
Nope, the cool thing is that the negative triangles take care of this. If you go "back" at some time, you subtract that area instead of adding it, which will compensate for any excessive area you added or will add with positive triangles. I don't have a formal proof of this, however it looks fairly logical if you verify it on some shapes and we also looked at this in our computational geometry class in uni last year, so I'm fairly confident it's true. ;-) As for how to do this practically: Take a pivot point P (I'd personally pick P_0, automatically makes the areas generally normal, prevents some numerical stuff like catastrophic cancellation). Iterate through the vertices counter-clockwise, call these vertices P_i and P_i+1. sum += cross_product(PP_i, PP_i+1)[2]/2 Cross products have some nice properties in computational geometry, even in 2D. We're working in the XY-plane, so all cross products will be pure Z vectors so they're really just scalars. It also automatically deals with the sign and furthermore are great for calculating areas without going all-in with analytical geometry, since it represents the area of the corresponding parallelogram: en.wikipedia.org/wiki/Cross_product#Geometric_meaning P.S.: It's worth noting though that this doesn't work for self-intersecting polygons. However, since usually we can assume the polygon is "simple" (I think it's called something like that) this method will work as it, unlike some other algorithms from computational geometry, doesn't care about convexity. :) Edit: Seems to be correct, found out this is a centuries-old algorithm, in fact: en.wikipedia.org/wiki/Shoelace_formula
This is similar to my solution using the 0.5* the sum of the cross project of the vectors to the vertices of the polygon sweeping counter clockwise direction closing with the last vertices to the first. Don't use the magnitude as the sign of the out of plane vector will correct add or subtract the area as necessary. The half the final magnitude of the sum will be the the area. Try it and look at the values as you go around and you will see how the cross product flips from positive to negative when the leading vector switches order in the cross product.
Spirals? I was just wondering about this - how mathematically you can go from a helix to a spiral? - Apparently it's all in the maths (I'm British, so I don't sat "Math" - but I do say "Lego" instead of "Legos"?... yeh, anyway..) when dealing with quantum physics. I'm still trying to get my head around it, but supposedly particles are manifestations of fields - and that's all they really are... when talking about whether they are a wave or a particle, they are actually part of a field. What I'm trying to get my head around is that a particle is only a particle when it is observed (which is usually some distance away from the particle and considering a large enough region of space to observe it in - I think? - because of quantum 'fuzziness' about the particles exact location but also - I think? - becuase when you observe close up you are observing the field more than the particle... I think a particle is a macro phenomena). Anyway, now I've cleared up that I am confused :P Particles move around like particles but they interact with each other like waves. A particle also has mass (unlike the 'bosons' that make up a field - edit; not true for W and Z that make up the electron and Higgs) and does have a location in space (when it is 'observed'). A wave though is basically a spiral though isn't it? - A spiral has a point location (the centre of the spiral), whereas as a wave doesn't have a centre (it has a perspective - formed by a helix - that seems to reach a point far off if we view it down the length of the wave - so that it looks like a spiral if viewed in 2 dimensions i.e. with one eye closed). I was just wondering about this - how mathematically you can go from a helix to a spiral? I have actually kind of done this (in my own amature way of not really knowing what I was doing..) by mapping spirals onto a sphere to form a helix... I also found that with multiple spirals you can form patterns either 2 dimensionally on the spheres surfce, or 3 dimensionally with the helical patterns (using the same 2 dimension spirals)... way out of my league but, maybe the relationship is better understood with Lie Groups rather than constructing a geometry you can draw clumsily on a football (sorry - soccer ball).
I genuinely find the topics covered in this channel fascinating, however it's interesting to me how math phobic I am. I watch every episode of Infinite Series all the way through but my palms are sweaty and I feel physically anxious/avoidant by the mid-point, every time. The whole experience is a bit unnerving...youtube maths causing fight or flight response!
Your wording of induction ("if it holds for a graph with N vertices, it holds for N+1"") in 2:33 is a bit misleading. I would rather say "if it holds for all graphs with N vertices, it holds for N+1". Not a big deal, but I suppose this would be a more "correct" version of the same statement.
6:14 for the triangle being half the area of the square Here's a pure Geometric Proof by stitching and slicing: imgur.com/gallery/dEdkn The proof easily extends to rectangles.
Alright, finally the lemma. Small triangle can be embedded into a rectangle and cut up the rest into rectangles and/or right triangles. Something like this imgur.com/WZdDDw2. Then you have to prove Pick's theorem for these two simple shapes and using some counting and algebra you will deduce, that the small triangle have area 0.5.
Metaknightmare217 all points that the polygon intersects. So, vertices and also points that lie on the lines. In her example shape, it appears to have 7 vertices, but it also passes through two other points on those vertical and horizontal sections. So b = 9 for that shape.
So I was hesitating to write how much I like this channel since everybody is telling you that anyway, but other creators keep persuading me that it is still important for you to hear these words. And you deserve all the praise you can get. I have studied a very math-heavy field in college (physics), so most of the educational channels on math on youtube don't really cut it for me in the sense that I either already know the topics they cover, or they don't go into enough detail or it's plain boring, but not these series though. Every video is well written, deep and on an interesting topic, and you explain everything in such a way that even schoolchildren would understand it perfectly. And then you also engage with the audience in the most thought and curiosity provoking way possible! You have talent for this stuff and please continue making these videos! This channel is fantastic!
You eloquently put what I have been trying to word. "...math-heavy field in college (physics), so most of the educational channels on math on youtube don't really cut it for me in the sense that I either already know the topics they cover, or they don't go into enough detail or it's plain boring, but not these series though."
I had the privilege of being one of a dozen students proving conjectures with Paul Erdos. That man saw around corners.
Really? thats impressive
Wow!
Tell us more!
Do you have any stories about working with him? I, and I'm sure many others as well, would love to hear them!
+George Steele, as says +Patrick Blee : can you tell us any stories ?
6:14 The answer is trivial and is left as an exercise for the reader.
Pure gold ahah
I don't understand your comment. The proof is not trivial, so I'll give you the benefit of the doubt and presume you're not saying it is. She never said it was trivial, but rather referred to it as a challenge problem.
DocThorium, I have a brilliant proof for the statement, but this margin is too small to contain it.
+Steve's Mathy Stuff He was quoting a sentence that it is quite often found in math books. Sometimes the authors state it even if the proof is not easy at all, but simply because... they cannot be bothered :)
The intent was totally sarcastic then.
OK. I have encountered the statement in texts, but only when the proof was trivial but tedious. Now I have to try to find a non-tedious proof for the small triangle lemma.
This channel is awesome. I hope these don't get defunded
I think PBS is getting fully defunded in the latest budget
Well shit, I greatly enjoy these. Also PBS being defunded means less Crash Course too, right?
who knows, i hope there's a way they can survive without that money but i don't know to what extent they survive on donations etc
+DonaldoTrumpez Trump its gonna be a seriously cool future, godspeed usa
Done ✅
A new episode of PBS infinite series is now one of the highlights of my week. Keep em coming!
well theyre now dead rly sry
Dear Dr. Houston-Edwards, we need more people like you on Earth, or perhaps we need more visibility for educators like yourself. Thank you for putting forth the time and effort to share your love of mathematics, as well as to the the rest of the crew.
Thank you.
In your proof that planar graphs have Euler characteristic 2, I think you missed a step. Since we're allowing loops on a single vertex, we need to consider whether the edge we pick is a loop or not. If it's not, the logic works fine -- contraction of that edge removes one edge and one node, and we're fine. But if it's a loop, contraction of that edge removes one edge *and one face*! This is still fine (faces and edges can cancel out too), but the argument is subtly different between the two cases.
Personally, I would have focused strictly on straight-line planar graphs, which can't have loops to begin with. The base case is just as clean if not cleaner. Barring that, we could show that every planar graph with loops can be reduced to one with the same Euler characteristic but without loops; the proof would proceed exactly as before.
Jonathan Castello I'm glad you noticed that! nice explanation too!
Jonathan Castello Yeah, the error became glaring when it was claimed any such polygon could be broken into small triangles. Triangles have straight edges. Anything curved, such as a loop, creates a contradiction. Or we can even go so far as to call the contradiction an actual falsification. At least a falsification of the way it was presented, which may be the only problem. Words have meaning, even in maths.
@Snatch n Grab: Ah, no, polygons always have straight edges. There's no problem there. Polygons are a specific kind of planar graph, and the Euler characteristic of *any* planar graph is 2, whether or not it has straight edges.
The problem is one of rigor, not accuracy. All of the theorems presented are true.
***** You're right. I'm going to the example in the video showing a planar graph involving loops, but it was NOT declared that it would work for that.
There’s also the fact that contracting an edge of a triangle removes one node, two edges and one face which also ends up working fine but is another case that was missed.
at 3:40, if you contract an edge that is part of a triangle, it removes the face but also merges two edges leaving the Euler characteristic the same but you missed that in the video. minor detail but it needed pointing out
3:25 "When we contacted the edge we removed one edge and one vertex so the Euler characteristic didn't change."
This assumes there is only 1 edge between those two vertices. In the case where there are k edges between the vertices, then you remove k edges, 1 vertex, and k-1 faces. However, since 1-k+(k-1)=0 the Euler characteristic is still unchanged.
You can also leave the other edges just as loops connected to the same vertex at both ends, as in the 1 vertex case.
I saw this popup on my chrome app and I had my stoner friends over and I was acted like it was no biggo but you know, I love this show and lööve it when you upload, couldn't wait till they left, checked their busses and everything 10 times just to see this, now I'm stoned too so here we go
6:14 Assume that two of the points of the triangle lie on a line of slope m. Then they are (m^2)+1 units apart. The third point can go either one of the two parallel lines closest to the line with the original two points. A little geometry shows that both of these lines are exactly 1/((m^2)+1) units away from the original, so we have a triangle with base (m^2)+1 and height 1/((m^2)+1), which just has area 1/((m^2)+1) * ((m^2)+1) / 2 = 1/2.
Also, awesome video thanks for sharing!
not really sure where you’re getting (m^2)+1 from
if you take for example the points (0,0) and (4,3), then there are no other points on the line segment connecting them, which has a slope of 3/4
but those two points are a distant of 5 apart, not (4/3)^2+1
This is not a simple proof, but the video makes it digestible. Thank you!
PBS Digital Studios is a gift to the world!
If maths fails you, you could try archimedes. Extend the surface in the third dimension to give a volume. Submerge it in a bath. Measure the volume of water displaced and divide by the thickness. Run naked down the street shouting eureka (optional). Works for any shape.
I am really glad that you are doing this channel. People need to have a better understanding of what mathematics is about.
That said, you forgot to argue/mention that the graph obtained by contracting an edge is still planar.
1:43 *connected
Also, I enjoy more the other proof. We prove the formula for rectangles, then for right triangles, then for any triangles, and then for any polygon using triangulation
Around 3:35 - for a graph like a triangle you can't merge two vertices without also destroying a face. Of course the Euler characteristic doesn't change because you also merged two edges into one, but it is not obvious (at least for me) why that would always be the case. Hence, why when every pair of connected vertices destroys a face when merged, it must also be the case that exactly one pair of edges is also merged? Is the triangle the only case?
3:28
This proof is wrong.
1. She assumes no faces are affected by the collapsing of an edge, which can happen if you pick a different one from her example graph.
2. She does not use the fact that the graph is planer, so in theory this holds for all graphs.
Actually the number of faces stays constant when you collapse any of the other edges of the example graphs.
1. If you pick one of the sides of the triangle to be removed, then the triangle collapses and the number of faces reduces by one. But, not only are you removing one edge, but the collapse leads to two edges becoming one, so one EXTRA edge is inadvertently lost in the process. So the formula continues to hold!
2. Good point. I don't know how this issue is resolved.
@@jpchaitu I am not sure if my reasoning is correct, but I am thinking that in case of nonplanar graphs, you wouldn't start from n=1 (you can't generate a nonplanar graph with 1 vertex) but with n= 5 ( I believe the simplest nonplanar graphs have 5 vertices). In that case, you would see that the Euler's characteristic is not 2 so the theorem doesn't hold for nonplanar graphs.
@Hassan Akhtar Reading my commen back, 2 does not make sense.
But I still think 1 does. For example, if you contract an edge in a triangle, the number of faces drops from 2 to 1.
Showing that the triangles in 6:14 all have the same area is quite simple, because you can turn them into one another using transformations that don't change the area of the object.
These transformations are moving, turning and shearing. First, you move and turn the triangle on the top left so that one it's sides exactly matches one of the other two. Let's call this side a, the one you just used to align the triangles. After that, shear the point that is NOT a vertex connected to a so that it matches the triangle we are looking for (shearing is done by moving the vertex or corner parallel to an edge that it is not connected to).
The fact that turning and moving doesn't change the area of the triangle is easy, because you can either just shift your 'camera' again to match the original triangle, or show that the formula for the area of a triangle still holds true.
Shearing is a bit more trickier, but can be done graphically. It's probably easier to show it using a square. Take one side of the square, call it a, for example. The side opposite of a is the one we want to shear, let's call it c. Now, shearing would be done by moving c parallel to a. Draw a new c' that is the sheared version of the edge c you want to have, and draw the square using c' over the one using c, so you have to overlapping squares with one shared edge, a. Notice something? The difference between the two squares is visible as two triangles. If you were precise enough with your drawing, the two triangles are the exact same, they're just flipped. This means that you can actually visualise shearing as taking one triangle away on one side and adding the exact same triangle back on on the other side, meaning that you didn't change the net area; you just subtracted and added the exact same area on the original area.
Excellent series, no pun intended, I hope the cuts proposed by the new administration don't hurt this and Space time channels. Keep the good work.
The way you explain is awesome and you explained each and every term so clearly it helped me a lot so thanks for the video 😘
+PBS Infinite Series Do analogues of Pick's Theorem exist for triangular and hexagonal lattices?
At 3:12, it is possible that no such edge exists, unless we specify that the graph must be fully connected.
3:38 correct me if I am wrong but aren't you also missing the possible case where an edge, two vertices and a face is contracted also preserving the relationship?
I know that there are easier solutions (I found one myself), but I want to share this overkill-solution using Minkowski's lattice point theorem:
W.l.o.g. we may assume coordinates, such that in the triangle ABC A=(0|0).
What I want to do first is noting that the area of a lattice-point-triangle is a multiple of 1/2. This can be shown by first doubling it to a parallelogram and then slicing and shifting to make it a rectangle.
Now, if the triangle has an area bigger than 1/2, its area must be at least 1.
Were doing the following: First, we reflect the triangle at the midpoint of AB yielding C'. Then we reflect this triangle at the midpoint of AC' yielding B'. Since the triangles ABC, AC'B and AB'C' are congruent, the angles CAB, BAC' and C'AB' add up to 180°, hence C,A and B' are on one line and |CA|=|B'A|. Therefore, B' and C are reflections of each other at A.
With this in mind, we can reflect the quadrilateral CB'C'B at A, which gives (together with this quadrilateral) a convex hexagon of area at least 6 (since it consists of 6 triangles) symmetric around A.
If we now scale this down to a similar hexagon of area 5>4, this does not contain any of the original vertex points. By the lattice point theorem, this hexagon contains at least one lattice point apart from A.
Hence, at least one of the six triangles contains a nottrivial lattice point.
Now we prove that all six triangles (hence the original one) contain a lattice point:
Since the mid of AB is the arithmetic mean of two integers, its coordinates are multiples of 1/2. Reflecting a lattice point at a point of which the coordinates are a multiple of 1/2 will also yield a lattice point, because (a,b)+2(x/2-a,y/2-b)=(x-a,y-b) hence this applies also to the reflected points. Reflecting back we get a lattice point in every triangle.
If you think this is interesting, look up the shoelace formula. It also allows you to easily calculate the area of a polygon, but it doesn't even need integer coordinates! It works on any arbitrary polygon and is so simple an 8 year old could apply it. If you look closely, you'll see that it uses similar principles.
I have used the fact that the 2*area of a polygon is the sum of the cross product (not the magnitude of the cross product) of the vectors to each successive vertices around the perimeter of the polygon closing with the last vertices to the first in a counterclockwise direction. This of course works for non integers. It seems it would be trivial to use this to prove that for integer points this sum simplifies to Picks theorem shown in this video.
For any triangle that does not have any integer lattice points inside it, so base and height will always be 1 each.
Area = 1/2 * base * height = 1/2 * 1 * 1 = 1/2
Nice! I have two remarks about all this. [REVISION: 3 remarks.]
1. At around 1:40 - 1:50 - Not ****quite**** (I'm making a pinch gesture with thumb and forefinger) true as you've stated it (for the plane, of course).
Yes, that formula will always give 2 for a *connected* graph. For a graph of p mutually disconnected pieces, the formula is:
v - e + f - p = 1
. . . an extension of Euler's formula which is equally beautiful, I believe, as the original form. This version also applies to the null graph, with v = e = p = 0, f = 1 (default face consisting of the whole plane).
2. In proving the formula for the Euler characteristic, it seems to me that you have considerably more work to do than you've shown here. I would say you have 3 steps; namely, to show that:
A. It's true for the base case [which you've done, although, I would have started with a lone vertex, (v,e,f) = (1,0,0)]
B. Adding any single, or minimal set, of elements [and there are multiple ways of doing that], preserves the formula
C. Any finite, connected graph can be constructed this way.
You evidently have more cards here than you're showing, given the constraints of time, and of keeping the viewer-attention train from getting sidetracked; but can you fill in some gaps here, and explain how to prove that your construction method can build any connected planar graph?
New, 3rd remark.
3. In a recent comment thread, in my back-and-forth with Czeckie, the starting comment being by Ruben, it has been established that your method of proof falls short, as it fails to cover some cases, which Czeckie has supplied.
There are any number of triangles, which, taken as the polygon whose area is to be subjected to Pick's Theorem, cannot be tesselated into "small triangles" that satisfy your conditions as you've illustrated them, but can be so tesselated, taking the conditions as you've stated them.
Namely, when a "small triangle" has a unit grid segment as one side (this was true of all your illustrated examples), it is easily shown that its area = ½. [Call this special case a "small grid-segment triangle"]
But when a "small triangle" doesn't have a unit grid segment as one side, it is far from easily shown. And such a triangle can't be partitioned into small grid-segment triangles.
A simple example (due to Czeckie) of a polygon which can't be tesselated into small grid-segment triangles is the triangle:
(0,0), (1,0), (2,3) . . . . i=1, b=3, A = i + ½b - 1 = 3/2
Two examples Czeckie gives of small triangles which aren't small grid-segment triangles are:
(0,0), (1,1), (3,2) . . . . i=0, b=3, A = i + ½b - 1 = ½
(0,0), (9,4), (20,9) . . . i=0, b=3, A = i + ½b - 1 = ½
With infinitely many possible triangles such as these last two, which touch or enclose only the 3 grid points at their vertices, and so, fit the definition of "small triangle," how do you show that Pick's Theorem holds for them all?
about the 3rd remark. I don't think the proof is wrong. The examples I've provided were to show that your "small grid-segment triangle" is insufficient. Your last sentence is the main thing, but Kelsey is aware this is the thing that needs to be proved. She stated it that way. And I don't know the answer and it pains me greatly. I'm sweeping this comment section up and down an haven't find any correct proof. My own attempts are not working. I can prove, that any grid triangle with area 0.5 is a small triangle, but it is the other direction what we need for proving the Pick's theorem.
Well, yes, I'll concede that the proof is not wrong; but it, or her presentation of it at least, is incomplete; and I see that you, like I, have been unable to seal off the proof of that lemma.
I have! I don't feel like writing down all the details, but basically what's needed is to enclose the small triangle into a rectangle (like this imgur.com/WZdDDw2) and the cut out blue parts will be right triangles or rectangles. You can prove pick's theorem for these two shapes. Then the true area of the rectangle is 0.5 greater than that of blue bits. I'm just leaving it here as a hint/program. I'm sure you are curious enough to supply the details :)
awesome, I always love watching these videos. thanks for all of your work
Your mention of Paul Erdős immediately made me wonder: what's your Erdős number?
Shit, as a physicist, I have tons of respect for mathematicians. You guys rock.
Can you extrapolate this to find determine the area of a circle (as you take the density of the lattice field to infinity... or the size of your object if you prefer). I'd be curious if that works.
is there any chance you will discuss russel's paradox in relation to cantors set theory?
3:45 and what about faces? (I know, but you didn't say it) by contracting two vertices that outline a face with two edges, the result is one less face and vertex, and two less edges, net zero change.
An endless hallway *would* ensure sufficient distance between greenscreen and subject to avoid the green light reflecting back on the subject. Of course, since the end of an endless hallway is infinitely far away, that makes lighting it rather challenging.
No greenscreen hair usually means excellent lighting. Or an endless hallway. (I'd like to see the proof on being able to construct an endless hallway in finite time.)
Yes, supertasks allow you, in the abstract, to do an infinite amount of work in finite time. Math doesn't have any issues with that, but physics certainly does. ;)
With the induction proof, doesn't that rely on the contracted edge not also changing the number of faces? What if the graph of N+1 vertices had no vertices that could be contracted without changing the number of faces?
This is one of my favourite theorems!!!
It may be crucial to add the following to the induction step: since there are at least 2 vertices, there exists an edge that is not a loop; when contracting the two vertices at the end of this edge, any other parallel edges are retained as loops - they are not removed from the graph. otherwise things aren't correct.
When stating the Euler formula, you forgot to mention that the planar graph must be connected. For example, consider a graph composed of 2 verticies and no edges. This has a characteristic of 3.
In your proof that planar graphs have Euler characteristic 2, i think you missed the step that all graphs having a Euler char. of 2 are planar graphs. The reverse direction is missing to be shown? Without that, the question could be, if other non planar graphs could have also E. char of 2 ?
I might miss something here, but someone please correct me if I am wrong.
This episode has all the bangers!
0:40 going a bit over the moon mentioning "trigonometry". Segmentation is more than enough.
Without pick's, you circumscribe the problematic spikes with parallelograms (A rectangle is a parallelogram) and those inscribed triangles are half the area of their circumscribed parallelograms! Then the interior is only made of simple rectangles you can add. It's still tedious though.
You can also use the area of a triangle when it's a bit tougher. You can even use it everywhere!
Not all planar graphs have Euler's Characteristic 2, the theorem only holds for connected graphs. for example the first graph you showed, you can split it in the middle to get 2 k3 s , they have the same number of edges, and faces but one more vertex.
The more general formula for planar graphs is
v - e + f - p = 1
where
(v,e,f) = (vertices, edges, faces) , as before, and
p = number of mutually disconnected pieces
For the usual case of a single connected graph, p=1, and you get the form she showed.
ffggddss that is true, and the poof is by looking at each connected part of the graph, summing up the equations and subtracting the number of additional tines the infinite face was counted
ffggddss that is actually incorrect, the formula turns out to be
v - e + f + p - 1 = 2p
you can check it, I checked yours, which Turned out to be false
+ TheSkyCuber
Revisit your algebra then, because your formula and mine are algebraically identical.
Just add (1 - 2p) to both sides of yours.
ffggddss you are right, sorry about that.
Man, I miss this series
4:40 why did you show a different shape than at the begining saying it's the same one?
wait so if it's not integer lattice but instead its by V should you do (2i+b-2)*V*V/2 where V is the distance between each point in the lattice?
The demonstration at about 3:30 does take into account the number of faces when reducing the number of vertices as if F was meaningless: it is always a sign something is wrong when you don't take into account one variable. So here is the counter example to the proof: how do you reduce a triangle? In this case, you remove 1 vertex, 2 edges, and 1 face. Ok, Euler formula still valid but the demonstration is not.
Once you know small triangles have area 1/2, just add up all their interior angles to find out how many there are: 360 degrees per interior point, plus about 180 degrees per point on the boundary, but you need to subtract 360 degrees because you went around once! Now divide by 180 degrees to get the number of small triangles and multiply by 1/2 to get the total area. Much more elegant than all that algebraic manipulation shown in the video.
nice selection of non planar graphs. Beautiful theorem about them
Wouldn't be always possible to draw the polygon in a lattice grid by stretching or shrinking the distance between the points?
Kind of the lowest common multiple or something like that
At 0:08, I just thought to split up the shape into smaller triangles and rectangles, then add up the areas.
What a coincidence! I am taking a course right now about lattice polytopes and Ehrhart theory, and Pick's theorem was used as a motivating example at the beginning of the course. Get out of my brain, Infinite Series!
I love these videos. Kelsey, you have very good taste in mathematics.
Hey I just found out that over at Space Time they set up a reddit forum. I was hoping that one will be set up for Infinite series, as I would be very active on that forum. I love the open-minded culture and community that the PBS videos have currently. I would love to throw my ideas about dividing by zero, infinities/infinitesimals, and the MUH at the diehard Infinite Series community. Any super-fans here agree?
Found it: www.reddit.com/r/PBSInfiniteSeries/
Didn't see a link so I assumed one didn't exist.
Now! Now!! Now!!! I love it when she does that!
0:30 It seems pretty obvious to me that the worst one needs to do for that shape is divide a bunch of rectangles by 2. Even the acute angled bits can be described as one such half-rectangle minus another. The easiest manner of getting the area probably involves an averaging between squares filled and squares "touched" (with some probable counting shenanigans around acute angles and multiply touched squares).
4:50 Not quite what I was expecting, but it looks familiar. It likely works out to more simply describe the minor mess I was thinking of earlier (especially considering the division by two).
6:15 Yeah, accidentally did that while staring at the sharper acute angles about the first polygon (n*m/2 - n*(m-1)/2 = 1/2).
6:47 *Oh.*
I have a question for the Pi episode. Can we prove that there can exist at least one kind of number system where pi does work like it does in our number system? With respect to value, or relationship with the other components of mathematics ?
6:23 "It's always possible to do this."
Why? I don't see any obvious reason this should be true.
As a matter of fact, i have an example for which it seems to be impossible to do this:
Take a 4x4 grid of points and connect points (0,0), (3,2) and (2,3) to form a triangle.
How can you cut this figure into "small triangles"?
It is worth noting that the ultimate theorem still holds.
I figured it out, I misunderstood the definition of "small triangle".
I can't tell you how insanely pissed I am that this series is gone. In fact, I am infinitely pissed
The integer lattice and Cartesian plane seem very similar. Are they the same thing?
The plane are all 2D pairs of real numbers, so all ar eof the form (a,b) with a,b being any real numbers. If you only allow integes for a and b, you get the integer lattice
My attempt at trying to find an easy way to calculate the area resulted in: edge dots/2 + (innerdots -1)
didn't finish the challenge yet , next week an exam but : i picked a three different point , one of them (0,0) the other are random with the condition of the Y coordinates are strictly positive because the other case is already treated (same height +same base => 1/2); the proof is to suppose that the area is 1/2 and there is a point inside the triangle with an integer coordinates which lead to - the area of the initial triangle is strictly greater than 1/2 which is an absurd using 3 inequalities that describe the position of a random point inside the triangle relatively to each side + and knowing that the area of the triangle X2.Y3 - Y2.X3 = 1 where (X2,Y2) , (X3,Y3) are the coordinates of the other edges of the triangle
(P=>Q ) = true (not Q => not P )=true (not Q and P )= false
negation of the Contraposition
Just had a question in my head, is there any way the numbers of boundary or vertices can be a transcendent number? like E or pie..??
They can't even be a non-natural number, and definitely not something irrational
Why not? we can Imagine that
No we cannot. The amount of something (in this case, vertices) is per definition always natural. Imagiantion has nothing to do with that
Doesn't the triangle at 1:50 have an Euler characteristic of 4-6+3=1?
mrjoa96 You must count the outside as a face too
5:42 This is the most difficult part of the proof: to show primitive triangles have the area of 1/2, and you just threw it to us as an "exercise"?
It is not exactly hard as a triangle all has the base and height of 1 (each small triangle is the result of connecting the dots just beside it)
So, the area is (1/2)(1)(1) = 1/2
If this video is supported by Audible, then "Proofs from the Book" should be on there.
6:23 "it's always possible to do this" is doing quite a bit of legwork there
The proof of the challenge question. Are all small triangles (triangles whose interior and edges contain at most three points) necessarily or area 1/2?
First, consider a triangle drawn on a grid. For simplicity and without loss of generality, we will assume the base of the triangle is made up of the points (0,0), and (0, 1). A small triangle can be found by simply drawing the remaining to sides so that they intersect on a vertex at some point (1, y) where y is positive (once again for simplicity and without loss of generality). Any triangle will have a base of one and a height of one. So the triangle will have area 1/2.
Consider the same base, but a different point drawn further in the grid (x > 1). For example, for x = 2, the slope of the line that makes up the edge between (2, n) and (0,0) would be (n+1)/2 for some integer n. The function that defines this line is f(x) = (n+1)x/2 or x(n/2 + 1/2). The second line between (0, 1) (2, n) would be x(n/2). When x = 1, the distance along y between these lines is (n/2 + 1/2) - (n/2) = 1/2. Now consider two possibilities. Suppose n is even. Then n/2 + 1/2 must lie exactly 1/2 unit from an integer point in the column of points x = 1. This means that the other line must lie upon that point. Therefore if n is even, the triangle is not small. Now suppose n is odd. Then n/2 + 1/2 must be an integer. Therefore the triangle is not small. So no small triangle can have a third point lie upon x = 2. A similar argument can be used for x = k where k is an integer.
A further note is that pick's theorem works for any figure that has points whose coordinates are rational. For that, you can simply scale the grid by k where k is the LCD of all points in the graph. The area of each small triangle will be 1/2k. This theorem cannot be extended to the reals (or at least I can't think of a why to do it).
6:14 What's to prove? It's the basic formula for the area of triangles we all learned in elementary school!
Yeah but the height and base may vary in length
What?!?
+ Raphael
A little reflection reveals that they all have base = height = 1, in one or another orientation.
Yes but thats far from obvious
Edit: And just so I don't confuse anybody else, it is wrong as well
Raphael Schmidpeter That's actually an exercise for elementary math.
Very very good vedio👍👍👍
Made my day
1:57 "Linked In The Description" sounds like a cool name for David Epstein's website. :)
Write an essay on a proof of Pick's theorem. "an essay on a proof of Pick's theorem."
Can a smaller triangle has curvy edges? If yes, is the area still 1/2?
Hey, is this a martenitsa on her hand?
Miroslav Dimitrov I've asked the same question :)
Yes, it is. From a Romanian grad student. :)
This isn't a question about this video, but a different math question
Is it possible to have a truly random number generator where one would never be able to state the probabilities of what the next number could be?
testpage
That gives me a number between 1 and whatever number I choose, with an equal likelihood of each number. I know the probability of each number. I want to know if one could exist where the probability could not be known.
If you randomized the probability of any particular number for every new number, you get the same result as a normal random number generator. Just like if you randomly picked and flipped two oppositely weighted coins; the end result will be the same.
If the probability is randomized and it keeps that same probability for every new number, yes, you could do this with discrete numbers between 0 and 1, but after enough numbers you could figure out the current probability.
xenontesla122
I'm looking for one where you could never predict the probablility given an infinite amount of time.
Then what you're looking for is a random number generator that uses atmospheric noise. www.random.org/randomness/
AltisiaK
Atmospheric noise is non deterministic, but it still gives an even probability for every number. I can write a formula to find the odds for what my result will be.
I'm looking for a random number generator where the result is completely unpredictable.
(Note: I'm not literally looking for one, I'm just curious if such a thing could mathematically exist)
That is one of my favorite books!
is it possible to pursue PhD under your guidance?
Say a problem is as easy as Pie, then multiply estimated time to complete problem by Pi to get the true indication of the difficulty of the problem.
How do you prove step nr 2? Every shape can be disected into small triangles.
Yes, it is possible. The dissection here is such that we need to use all of the dots. You can do it however you like. Always connect a point to some other two points that already are adjacent to some edge. And just continue. As long as there is a triangle that contains a grid point in it's interior or somewhere at the perimeter except for its vertices, you can use the point to dissect the said triangle. At some point, you will end up with only "small triangles".
Thank you. Your proposed method of triangularizing is not complete though. It is possible that there is a shape that has no interor point and all of its points are vertices (not contained in an edge). Sometimes you get shapes where it is not possible to pick a random point and then connect it to some other two points that already are adjacent to some edge. (example: In a non-convex quadrilateral one cannot pick one of the pointy ends to construct a small triangle with your method).
Intuitively the statement is obvious. I however was unable to strictly prove it and/or come up with an algorithm.
6:15 Basically:
This portion of the proof is left to the student as an exercise.
Ah, and here I'd thought I'd never think of that phrase again.
Well, at least in this case it's for fun, not a grade.
do you wear martenichka on your left hand ??!
Is this the way computers calculate the area of a shape? Do they approximate the shape into a poligon in a grid of pixels?
Celso Rosa pretty much. Most computer graphics break everything into triangles and them use projection to map anything 3D to 2D. Different algorithms them fill in pixels. Simplest way is to fill in all pixels strictly within triangles, but this creates jagged and rough edges (which things like antialiasing help with)
Hey, does this work for a 3D graph as well? Using Tetrahedron's instead of triangles?
In the induction proof, the argument that contracting an edge will result in the loss of an edge and a vertex is flawed, your own picture shows why this argument is not universally true, since I have a counter-example showing that you can select a random edge to contract and it will not result into losing just an edge and a vertex.
If you contract one of the top vertexes you'll lose 2 edges, 1 vertex and 1 face. The relation is maintained, but you can't say that by contracting and edge the euler caracteristic will not change because you only lose an edge and a vertex, because that's not always the case, as shown in the example above.
I mean, the relation still holds, but you can't say that contracting an edge will always lead to the loss of just an edge and a vertex and use it in an induction proof.
I love this channel, and by no means I want to sound harsh or anything like that. I'm just pointing out the issue with the argument used in the induction proof. Cheers from Brazil.
Thanks a lot😊
This method is actually not the simplest for a computer. You have to count the interior vertices, which isn't trivial, it's not O(n).
If I'm correct, the area of an arbitrary polygon can be computed as follows, in O(n) with n being the number of vertices.
Pick any point p on the plane. Form all n triangles with p and each ordered edge of the polygon taken clockwise. Blindly sum the areas of those triangles, if the triangle is counter clockwise its area is negative.
For this to work, wouldn't the polygon need to be convex and p need to be inside the shape?
Just curious cause I was searching for a solution to this problem some time ago.
Nope, the cool thing is that the negative triangles take care of this. If you go "back" at some time, you subtract that area instead of adding it, which will compensate for any excessive area you added or will add with positive triangles. I don't have a formal proof of this, however it looks fairly logical if you verify it on some shapes and we also looked at this in our computational geometry class in uni last year, so I'm fairly confident it's true. ;-)
As for how to do this practically:
Take a pivot point P (I'd personally pick P_0, automatically makes the areas generally normal, prevents some numerical stuff like catastrophic cancellation).
Iterate through the vertices counter-clockwise, call these vertices P_i and P_i+1.
sum += cross_product(PP_i, PP_i+1)[2]/2
Cross products have some nice properties in computational geometry, even in 2D. We're working in the XY-plane, so all cross products will be pure Z vectors so they're really just scalars. It also automatically deals with the sign and furthermore are great for calculating areas without going all-in with analytical geometry, since it represents the area of the corresponding parallelogram: en.wikipedia.org/wiki/Cross_product#Geometric_meaning
P.S.: It's worth noting though that this doesn't work for self-intersecting polygons. However, since usually we can assume the polygon is "simple" (I think it's called something like that) this method will work as it, unlike some other algorithms from computational geometry, doesn't care about convexity. :)
Edit: Seems to be correct, found out this is a centuries-old algorithm, in fact: en.wikipedia.org/wiki/Shoelace_formula
This is similar to my solution using the 0.5* the sum of the cross project of the vectors to the vertices of the polygon sweeping counter clockwise direction closing with the last vertices to the first. Don't use the magnitude as the sign of the out of plane vector will correct add or subtract the area as necessary. The half the final magnitude of the sum will be the the area. Try it and look at the values as you go around and you will see how the cross product flips from positive to negative when the leading vector switches order in the cross product.
what's your Erdos number?
what happens if you take this to the third dimension. does it work for volume?
I just counted the vertices and guessed 25. close enough for my brain. I assume the error is something with the minus 1
those yellow springer books are not supposed to reach such a wide audience, they may sell out fast after this
Spirals? I was just wondering about this - how mathematically you can go from a helix to a spiral? - Apparently it's all in the maths (I'm British, so I don't sat "Math" - but I do say "Lego" instead of "Legos"?... yeh, anyway..) when dealing with quantum physics. I'm still trying to get my head around it, but supposedly particles are manifestations of fields - and that's all they really are... when talking about whether they are a wave or a particle, they are actually part of a field. What I'm trying to get my head around is that a particle is only a particle when it is observed (which is usually some distance away from the particle and considering a large enough region of space to observe it in - I think? - because of quantum 'fuzziness' about the particles exact location but also - I think? - becuase when you observe close up you are observing the field more than the particle... I think a particle is a macro phenomena). Anyway, now I've cleared up that I am confused :P Particles move around like particles but they interact with each other like waves. A particle also has mass (unlike the 'bosons' that make up a field - edit; not true for W and Z that make up the electron and Higgs) and does have a location in space (when it is 'observed'). A wave though is basically a spiral though isn't it? - A spiral has a point location (the centre of the spiral), whereas as a wave doesn't have a centre (it has a perspective - formed by a helix - that seems to reach a point far off if we view it down the length of the wave - so that it looks like a spiral if viewed in 2 dimensions i.e. with one eye closed). I was just wondering about this - how mathematically you can go from a helix to a spiral? I have actually kind of done this (in my own amature way of not really knowing what I was doing..) by mapping spirals onto a sphere to form a helix... I also found that with multiple spirals you can form patterns either 2 dimensionally on the spheres surfce, or 3 dimensionally with the helical patterns (using the same 2 dimension spirals)... way out of my league but, maybe the relationship is better understood with Lie Groups rather than constructing a geometry you can draw clumsily on a football (sorry - soccer ball).
I genuinely find the topics covered in this channel fascinating, however it's interesting to me how math phobic I am. I watch every episode of Infinite Series all the way through but my palms are sweaty and I feel physically anxious/avoidant by the mid-point, every time. The whole experience is a bit unnerving...youtube maths causing fight or flight response!
Finally something I can actually use. ☺️
Your wording of induction ("if it holds for a graph with N vertices, it holds for N+1"") in 2:33 is a bit misleading. I would rather say "if it holds for all graphs with N vertices, it holds for N+1".
Not a big deal, but I suppose this would be a more "correct" version of the same statement.
6:14 for the triangle being half the area of the square
Here's a pure Geometric Proof by stitching and slicing: imgur.com/gallery/dEdkn The proof easily extends to rectangles.
Alright, finally the lemma. Small triangle can be embedded into a rectangle and cut up the rest into rectangles and/or right triangles. Something like this imgur.com/WZdDDw2. Then you have to prove Pick's theorem for these two simple shapes and using some counting and algebra you will deduce, that the small triangle have area 0.5.
4:23 How is b determined? Which points are counted and which aren't?
Metaknightmare217 all points that the polygon intersects. So, vertices and also points that lie on the lines. In her example shape, it appears to have 7 vertices, but it also passes through two other points on those vertical and horizontal sections. So b = 9 for that shape.
Thanks
please make a video on abel rufini theorm
You are very good.