Something I love about Numberphile is that the subject matter experts are always so passionate in presenting these things - you can really tell that they love what they do.
@@VideoFacio A bit too much snark here, my dude. He can still voice his appreciation and just because something a has label, doesn't mean that the label is accurate. In this case, yeah the channelname really does reflect the content. I Invite you to guess what the channel "FrameWhisperer" ist about and how the content of that channel connects to its name.
I can be. I envision the cue ball and and target ball as forming a vertex and normally just go for a straight shot. I can bank it, but only if there’s nothing less tricky available.
I love they way Holly is so happy and enthusiastic about what she does. It's great, I'm sure it's easier to learn from someone who has this enthusiasm.
Am I the only person who wants a 5+ hour video on the full, complicated explanation of winnable games? I doubt I'd even understand it, but I'm just too damn curious now.
Who would be able to sit for straight five hours . May be a series with videos of 20 minutes each a better option . (Something that 3BluesOneBrown does)
The genus gives you the minimum number of cycles that you can find in the graph. If the genus is 0 then you have a tree. In a tree you can always use the leaves to push back the dollars in the tree, without having to lose a dollar. In a cycled graph you may have leaves that have the same property, but for every cycle you have to leave a dollar behind.
I just got the book, "Divisors and Sandpiles" today and I'm very excited to start it... the introductory motivating problem is the dollar game. I can't figure out a proof as to why C6 with v0 = -2 and v2 = 2 and all other v 0 is unwinnable, but I feel that it is. The genus formula doesn't guarantee a winning strategy, since for that, the genus must be 1, but it's 0. C6 with v0 = -2 and v3 = -2 is clearly winnable and has same genus.
See, this is what I love about math! This is the first time I've heard about a 'genus' in math context. I immediately thought about Euler's polygon formula: V - E + F = 2. The fact that you have similar tools/viewpoints/frames for both cases (polygons and graphs) is (amongst other things ) what maths is about. I love it!
+Theo_Caro Uh, I'm fairly certain the fact that they're married or otherwise taken is irrelevant to those who admire them. Oh and they're not just pretty.
The graph has 87 vertices and 165 edges, giving it a genus of 79. The normal version has 113 dollars total and is definitely winnable (I found a solution in 195 moves). The secret version that flashes up for one frame has the same layout but only 22 dollars. This is less than the genus and probably not winnable.
Seeing ppl comment on the "redistributive" element of this game makes me want to ask: has anyone ever characterized economic models such as "socialism" or "laissez faire capitalism" or "crony capitalism" or "communism" etc. mathematically via graph theory? Cuz this video seems like EXACTLY the right place/way to start...
I think the subject you're looking for is economics. The whole point of that subject is to study the mathematics of the aggregate behavior of economic actors in those kinds of scenarios.
If you're looking for a basic analogy, then it'd be like this: Capitalism is structured so that the most-connected nodes gain the most value, as long as they pay less than the value they receive. These nodes would be the bosses and CEOs and landlords and other rent-seekers. Social democracy would try to redistribute the value from these concentrated nodes back to the mass nodes, but the whole process would be inefficient and take a long time to complete, and it also wouldn't prevent a re-accumulation because the graph system is still inherently tilted in favor of the highly-connected, lowly-paying nodes. Simply raising the pay rate isn't enough to solve the systemic issue. Socialism would fundamentally change the graph system and even aim to abolish it entirely. One way of doing so would be to erase every single edge in the graph, create one large node in the center, and draw edges from that node to every other node; all value would be distributed from the central node. At that point, the distinction would be entirely in *how* that value is dispensed from that central node.
This is sort of related. If you have a house party and you are putting out snacks how many snacks to you put in each room? In a mathematically perfect house party with totally random and unbiased guests you simply have to count the doors. Your guest will wander from room to room, picking any exit at random. After a while the distribution of guests will reach an equilibrium. It turns out this is stable when the number of guest in each room is proportional to the number of doors. So count the doors and put that many snacks in each room.
My argument for this partial solution is the following: When a graph has a genus of zero, then that graph has zero cycles in it (i.e. no sections that form a loop). Increasing the number of vertices in a contiguous graph will still keep the genus at zero, because for the graph to remain contiguous you need to add a single edge that connects the new vertex to part of the existing graph. Thus, we can only increase the genus of a graph by creating cycles inside it. As we saw with a three-vertex cycle, any operation in that cycle will have three adjustments in value: prime node loses 2, and the two adjacent nodes gain 1 each; alternatively, the prime node gains 2, and the two adjacent nodes lose 1 each. The smallest possible amount of excess money we can have is 0 (example: a=-1 -> b=2 -> c=-1 -> a). If it was (a=-2 -> b=-2 -> c=0 -> a), then this would be unsolvable, because the distribution of negative or positive values will never be even enough to allow for it. If we add a single dollar to any of the nodes, though, then it becomes easily solvable. That dollar has to come from somewhere though; imagine it being a node outside the cycle, (d=1 -> a). If we had d push this extra dollar into the graph, then it would be solvable, because d can immediately give back any dollars it gets to a. If we added a second node, (d -> c), then it becomes unsolvable again, because you don't have the extra value to pass around. You need to add an extra dollar to d, so that it can still pass its value in to a and participate. With this in mind, my suggestion is that you can validate if a graph is guaranteed solvable by removing nodes until you reach a minimum coverage graph, where each node is reachable through every other node with exactly one path. Each time you remove a node, you need to remove one dollar from a node. If you still have a net positive value at the end of this, then you are guaranteed to be able to solve this graph. As for checking if a graph is impossible to solve, I have no clue.
After 20 minutes of scribbling on a whiteboard I have found that: 1. The least dollars that can travel in a closed loop at a time, is equal to the least connected vertex in that loop. e.g. in the triangle graph, the least connected vertex has 2 edges; i.e. >= $2 must move in that loop at a time. 2. A loop is solvable if it has enough spare money to move in the loop less $1 (since a 1 connected vertex is not a loop). e.g. in the triangle loop, since >= $2 must move at a time, and there is a spare $1, every 2x + 1 value can be reached. note: some loops may be solvable without any spare $dollars as they may coincide with the minimum movable value (xth value). 3. A graph is a collection of connected loops, therefore a graph is solvable if all its loops are i.e. if it's most connect loop is. i.e. A graph is solvable if the least connected vertex of the most connected loop - $1 is >= the spare $dollars on the graph. 4. The genus of a graph is always >= the least connected vertex of the most connected loop, therefore it will always be solvable. 5. By this logic, large graphs are more likely to be solvable, as they tend to have proportionally less edges per vertex. i.e. size does not equal complexity. Although they may take longer to solve...
According to my calculations, there are 163 edges (a straight line connecting two vertices), 87 vertices (the round endpoints), and the sum of money on the board is $105. Given the circumstances for some games, as mentioned in the video, this game should be winnable, given that $105 > 163-87+1. I'll brute force this and see if it actually is winnable, though.
You could make a graph of all the possible moves you could make. Each edge is a move, each vertex is a game state. That gives you a tool for analyzing the game. You're looking for the shortest path from your game state to a winning game state. In the move graph you'll always have as many edges for each node as the number of nodes in the graph being analyzed. The number of nodes will be infinite.
For any subset of vertices, consider the edges joining a vertex in the subset and a vertex not in the subset. It is always possible to send one dollar into the subset or out of this subset through these edges by either using all the vertices in the subset, or using all the vertices not in the subset. If there is a bridge can be used to cut a problem satisfying the E-V+1 bound into 2 problems satisfying their E-V+1 bounds. Hence, we can assume there are no bridges. That solves all trees. We can try to induct on the genus, E-V+1. Clearly, it is always possible when the genus is 0, as it is a tree. Suppose a solution is possible for every graph with certain genus g. Then, consider a graph with genus g+1. Ignore 1 edge and one dollar to reduce the genus (say edge from a to b, WLOG dollar on a) and pretend to solve the problem. What this does is that now, we can guarantee: 1. All vertices except possibly a, b, have nonnegative value. 2. As we used the edge between a and b some number of net times, their sum will still be nonnegative, in particular, we have value of a + value of b >= 1 (due to the ignored dollar). WLOG, value of a >= 2 and value of b
I guess the solution involves vector addition. Each move is reversible, so you can start with zero dollars at each vertex and work backwards from there. For every point you have two operations. One is to add n to the vertex and subtract 1 from each of it's neighbours. The other is it's reverse. This whole setup is like adding and subtracting vectors. It does not matter what order you add the vectors in. You only have to count how many times you add each vector, and multiply that vector by this number. Because the process is reversible you can also subtract the same vector, which is the same as multiplying by a negative. You can visualize this for the three vertex case. Label each vertex (x,y,z). The vectors are +/- (-2,1,1),(1,-2,1) and (1,1,-2). If you do the first one 3 times and the second -2 times, you get (-8,7,1).
You can reduce this to an ILP problem, but that is NP hard. Let your variables be per vertex the amount of times you claim money (for example: 3 claim moves and 5 give moves will make the variable 3-5=-2, so this can be negative) The constraints are simple per vertex: starting money + amount of neighbors * variable - sum of variables of neighbors >= 0
I apologize if this is mentioned already but if you donate money you don't have you're borrowing money from another entity unless you can create money. So your solution in the first example where the point that went from -1 to -4 is either something like the Federal Reserve that creates money, or that move violates the game rules as it utilized a verticie that is not listed on your paper graph. Also, typically borrowing money comes at a premium rarely do you see 0% loans, so that node would likely owe MORE than what they gave.
You can use a little knot theory to come up with the vertices outlining the knots, and the crossovers would govern the + or - by direction. Snap pea program will show the characteristics of the knot, while the direction and vertices dictate the sums. The overall balance isn't important because the directionality of the process of exchange will show the problem areas (vertices that light up the most) as a probability spectrum of possible connections which would imply the number of vertices per unit is a function of the length to complete a cycle, not balance out the "budget". Once cycled the unlit areas will be the isolated Islands of incomplete transactions, aka the crossovers, or genus, of the outlayed knots that replaced the vertices. Maybe some dehn twist to show an anti correlation at the complex arena, possibly showing why extra routes may inhibit whole areas from even participating. Excuse the vagueness
Here the case is clear: We have a subgraph with nodes -1 and -2 which has debts of 3 Dollars. It is -2 to get Dollars. It will do so 1 time and also 3 will give one time. Now the subgraph is to be balanced and the node with 3 needs toget one from 2. We have to distribute within the subgraph which takes 2 further takes from the leave. 5 steps are minimum.
The genus/sum connection is about how much control you have over dividing up the money. A graph with very few connections means you have more control over how the money moves around; after all, a vertex connected to only one other vertex gives you absolute control over where you send the money, because you can always give or take from a specific vertex. The more highly connected the graph is, the more spare cash you need, because you aren't able to divide it amongst the vertices as evenly as you would like. I suspect that's an accurate and more straightforward explanation of the genus/dollar connection.
Has there been research on this game? I was trying to find some literature on this, but I only ended up with the Auction Theory Dollar Bidding Game. Some more in depth theory about this would be very interesting!
There is a link in the description to Matt Baker's blog. Baker is co-author of the paper in which the winning criteria are proved. In his blog there is a link to his joint paper from 2007.
I actually took an entire course on the subject! Look up Matt Baker or the book Divisors and Sandpiles: An Introduction to Chip-Firing by Scott Corry and D. Perkinson
As a computer scientist, since we rely a lot on graph theory and algorithmic complexity computation, I wonder if anyone may have referred to such works to improve performance of multicore computation, since it can be seen as a problem of fairly distributing work among workers (pre-requisite being for tasks not being mutually dependent - think scalar chips like GPUs maybe). Since the overall computation time would amount to the node/vertice with the highest value, optimising would reduce the global computation time. However the way to compute the optimal distribution seems pretty complicated and may often take longer than the computation itself... I’m pretty sure there should be references in the field. I’ll have to look it up :) And the same kind of problem could also be considered with parallel factory work I guess, or in biology with cells or ants maybe, so other fields may have worked on the topic too...
While it seems like commenters have already figured out that the monster puzzle at 8:42 and linked in the description is solvable, it looks like the one shown at 3:50 with "how few moves can you win the game in" is a troll. The genus is 11 with 4 dollars on the board!
Numberphile you should tottaly do a video on spinors vectors and tensors! tidbit about a spinor is that rotating it 360 degrees does not return it to its original position, yet rotating it 720 does! eventhough 720=2×360!
There are already videos on that. The "belt trick" is the classic illustration. The right way to think about it is that it's the spinor's relationship with the phases of its neighbors that changes after one rotation, not so much anything "internal" to the spinor itself, so it's not as strange as it sounds. The belt trick video shows how those "connections" get "twisted" after one rotation and "untwisted" after another.
Careful: "$ >= genus guarantees a valid game" is not the same thing as "$ >= genus is NECESSARY to guarantee a valid game." The former is true, the latter is trivially false (a graph of just a single vertex with $0 wins, but has a genus of 1).
In a perfect world dollar stores would offer puzzles to customers that if worked out and proved solvable/unsolvable they could get dollar discounts on their dollar items.
this is the best numberphile video, its not just entertainer and educational like most of other I also learn a new game, so I can be still entertained after the video end
Thank you for calling a vertex a vertex. I work in 3d and it drives me absolutely nuts how often veteran animators and modelers will refer to a singular "vertice" (ver-tis-see).
NICE !!!! It would make for a game that is really fun to play and not that difficult to program (the logic that is). The more I think about it the more I recognize the brilliance of the rules. Who invented those rules? Simple/Straight/Exact ... you just have to love it. The number equivalent to Tetris.
In the 3 vertices, 3 edges (triangle) the genus is 1. There's a trivial solution where all vertices are 0. You have already won. This will also be the case for all genus > 0 where all vertices contain 0 or > 0 dollars.
This doesn't exactly solve anything but may be interesting to someone. - Any turn you can take is reversible: "Vertex V takes" is reversible with "vertex V donates" and the other way around. Therefore, if you can get from configuration A to configuration B, you can also necessarily get from configuration B to configuration A by reversing all moves. Therefore if you cannot get from configuration B to configuration A, you also cannot get from configuration A to configuration B. And finally, therefore, if and only if you can get a configuration from any winning configuration, this configuration represents a winnable game. - Order of turns doesn't matter: Donating causes the vertex to lose n dollars, where n is number of its edges, and each neighbor vertex to gain 1 dollar, regardless of when in the game this happens. Similarly this goes for taking. I don't exactly know how to write this in proper maths but a vertex' final bank is its starting value + edge count*(times it took - times it donated) + sum of times its neighbors donated - sum of times its neighbors took. - That also implies that if a vertex takes and also donates in a single game, these turns cancel out both for this vertex and for its neighbors. If we cancel them out, each vertex either did nothing, donated n times, or took n times. As donating is the reverse of taking, we can consider donating n times as taking -n times. This way we can describe any set of moves without redundant fluff by assigning an integer to every vertex. - Any winnable game can be described with a combination of a winning configuration and this move set description, and any such combination describes a winnable game.
This reminds me of using the Critical Path Method to solving a flow issue between various processes in manufacturing, etc. Usually the CPM is used in relationship to time.
The (probably) optimal solution for the graph they solved by hand: Let the labels of the vertices be A=-2, B=-1, C=1, D=2, E=3 A takes once. B takes twice. D gives once. E gives once.
Consider the "impossible" triangle graph in the video with values 1, 0, -1. As always, there does exist the cheeky solution using infinity. First, let's make it r, 0, -r for generality since r doesn't need to be 1. Make the r give r/2 to each. The r is now 0, the 0 is now r/2, and the -r is now -r/2. For the positive value, do the same thing. r/2 gives r/4 to each. r/2 is now 0, 0 is now r/4, -r/2 is now -r/4. If you continue this infinitely then all nodes will approach 0, meaning the limit is a solution. Although this is more of a math joke, I wonder if this can be done for any "impossible" graph, which ones can't if not, what methods if can, and how to prove it can or can't. I did a lot of thinking on the original problem, and did some nice findings, but I'm a little too worn out to give it any thought at the moment, so feel free to answer what might be an easy, fun, and/or insightful find.
I wasn't thinking of how to determine if it's winnable or not, I was thinking of how to program the lowest number of moves needed. I was thinking of a set of two numbers per node, one number is how many it connects to and the second number is the total directly connected to it. Maybe a third number indicating true/false if there's a negative number connected to the node. Then somehow work the nodes in some order. This would make an interesting mobile phone app.
It's actually related, check out 3blue1brown's video on the Euler Formula, he uses the fact that a complete graph always in two dimensions always has a genus of one :)
The Major. That's the theory, sadly practice has revealed aspects of capitalism that probably merit an evolution investigation to bring us a more updated definition so that we are all on the same page.
+The Major A starving orphan "benefits" from being taken as a slave by a plantation owner. Capitalism involves the same kind of "mutual benefit." It's fundamentally asymmetric and exploitative. It relies on system of property relations that can't be rationally agreed to by a large chunk of the population.
Great strategy for people helping one another, say like a large family pool of members,buy a home buy a car get out of dept, practically anything can be done for one another by chipping in. The the only thing that would hinder this process is the greed factor.
As far as i'm aware, you can't really turn one graph into another, since simply moving nodes around doesn't count as different graphs. However, you might be able to focus on smaller portions of the graph at a time, balancing out the smaller graphs to better balance out the entire graph as a whole. That gets further into game theory though.
Some observations: 1. You always gave, never took, even though taking was explained initially, and it seems it would have helped to keep the number of moves minimal. 2. While graph theory is an obvious choice to tackle this kind of puzzle, I smell a set of linear (in-)equations (one for every game) as well. For the first example graph, and with nodes A…E ordered from top to bottom and left to right, and t(N), g(N) denoting the number of times we've taken to or given from node N, and A'…E' the new values for each node, we get (if I counted correctly): A' = 1 + 2*t(A) - t(C) - t(E) - 2*g(A) + g(C) + g(E) B' = -1 + t(B) - t(C) - g(B) + g(C) C' = -2 - t(A) - t(B) + 3*t(C) + g(A) + g(B) - 3*g(C) D' = 2 + t(D) - t(E) - g(D) + g(E) E' = 3 - t(A) - t(C) - t(D) + 3*t(E) + g(A) + g(C) + g(D) - 3*g(E) These are our linear equations, and the unknowns are the t(N) and g(N). But they don't describe a solution - too many unknowns and no idea yet of what A'…E' should be. We need more constraints, and we do have the following inequations that describe the objective of the game: A' >= 0, …, E' >= 0. Now, a straightforward Gaussian elimination will not give us a solution here. However, I think we could use Gaussian elimination as a tool by (for the moment) allowing rationals and searching for manifolds that intersect zero in one or more outputs… we could also look for intersections with the total sum for the graph… this could give us some acceptable boundaries to work with. I'll admit this is a very rough sketch, and it's been a long time since I studied linear algebra.
I thought the same thing when I saw the simple graph with 0,1 and -1 in a triangle: "that must represent some fundamental notion of superposition or entanglement."
Well, assuming I didn't mess up anywhere while programming this, I made a simple program and wrote a unit test with the big game at the end as its data: Edges: 154 Vortices: 87 Genus: 68 Sum of vortex values: 90 Game should be winnable because sum > genus
i assume that the requirement is [altough its not stated] that the graph must connected, else you can make any game unwinnable by adding a vertex not connected and with a 'score' of -1.
Here's a neat idea for an expansion of that concept: have several graphs each with multiple vertices that are interconnected with edges. Each of the separate graphs are connected with "super-edges" which must then be somehow "balanced" in the same way as the "lesser" graphs. (I know, it is a very rough concept, but I thought I'd throw it out there.)
I've got a trick. Take any amount of currency, how do make it lose 96% of value? Simple, Make the currency fiat, Let the fed lend it to the banks! Magic!
The initial game they played by hand could be won with 6 moves: - vertex with initial 1 donates ones, - vertex with initial -1 takes from all once, - vertex with initial 2 donates twice, - vertex with initial 3 donates twice. Order of the moves is actually unimportant.
@@iliakorvigo7341 In maths there is a need to point everything out. We are dealing with absolutes here. And considering trivial cases might well help figuring out more solutions as you differentiate several cases.
I found a pretty intuitive way to prove this for Genus=0,1 and I think it can be a beggining to the prove for genus=n (maby by using induction). Also i'm 17 yo and Englisg isn't my native language so sorri four bed inglish. First we need to notice that every vertex which is connected to only one other vertex and also it's number is 0 can be ignored because if we choose that every time that the vertex that connected to it donates this vertex will also donate it's like no one ever donated to it. Second we can notice that if a vertex number isn't 0 we can make it 0 like this: (1) if it's negative we donate to it untill it's 0. (2) if it's positive we donate from it until it's negative (or 0) and then step one (if it's negative). For genus = 0: the graph must be a tree(no circles) so we can make all the leafs(vertices which are connected only to one other vertex) of the tree values to be 0 and than ignore them and than we can do the same things to the leafs which were created because we ignored the leafs from before and we can keep doing this until were left with only one vertex (the root) which has the sum of all vertices (which must be 0 or bigger). For genus = 1. we can look at this as a tree which have been added to it one edge that is connecting to vertices on with height(length from root) h1and other h2. Now if are ignoring all the leafs we can and keep doing it we're left with one big circle (instead of one vertex) which have h1+h2+1 vertices (and edges) now we seperate it to 2 different cases: (1) h1+h2+1=3: we already know for this case that the statement is true (it's the case of the 3 vertices and 3 edges from the video) (2) h1+h2+1>3: we can focus on one of the vertices and make it's value 0, now we can notice that we can ignore it becuase if every time we donate from one of its neighbors we also donate from it than since it's 2 neighbors are not connected (h1+h2+1>3) it's like this vertex didn't exist (when one of it's neighbors donate it's like it donated directly to the other neighbor). So now we can choose one random vertex from the circle and ignore it and keep doing this until we only have 3 vertices amd than we go back to case 1.
Something I love about Numberphile is that the subject matter experts are always so passionate in presenting these things - you can really tell that they love what they do.
You do know what the -phile suffix means, right?
@@VideoFacio A bit too much snark here, my dude. He can still voice his appreciation and just because something a has label, doesn't mean that the label is accurate. In this case, yeah the channelname really does reflect the content.
I Invite you to guess what the channel "FrameWhisperer" ist about and how the content of that channel connects to its name.
You gotta love what you do, if you write on a carton paper with a marker
false.
numberphile and drawing on brown paper. name a more iconic duo.
Matt and his Parker Square
Cliff Stoll and his Klein Bottle
James Grime and his singing banana
Me and Holly
peanut butter and jelly
Fitz-Simmons
tomatoanus and speedrunning
As a pessimist I prefer to play the deficit spending game where all vertices have to have a negative number
are you a banker?
I can be. I envision the cue ball and and target ball as forming a vertex and normally just go for a straight shot. I can bank it, but only if there’s nothing less tricky available.
Multiply all vertices by -1 to get the pessimist's version?
Oh, you're a politician.
Keynes would be proud
I love they way Holly is so happy and enthusiastic about what she does. It's great, I'm sure it's easier to learn from someone who has this enthusiasm.
Somebody should make an app of this game
Working on it :D, will be usable in a few hours I think.
(idk yet exactly how long it'll take XD)
Would love to play this game if you get it working.
This comment is only here, so youtube informs me, when you write again.
Surprisingly there is no app with the name "the dollar game" yet.
@@AntonioNoack yes please
Am I the only person who wants a 5+ hour video on the full, complicated explanation of winnable games?
I doubt I'd even understand it, but I'm just too damn curious now.
I'd love that, too :)
You're not alone.
Who would be able to sit for straight five hours . May be a series with videos of 20 minutes each a better option . (Something that 3BluesOneBrown does)
At some level you start comparing it to other equivalent math problems and then it gets very abstract.
it never is. :)
The genus gives you the minimum number of cycles that you can find in the graph. If the genus is 0 then you have a tree. In a tree you can always use the leaves to push back the dollars in the tree, without having to lose a dollar. In a cycled graph you may have leaves that have the same property, but for every cycle you have to leave a dollar behind.
I love it when Amy Adams explains stuff!
Lol it’s true though. Holly should play the mathematician hero in the next scifi film adaption of a Ted Chiang story like Arrival.
Holly is gorgeous
Kangaroo
Except Holly is way better looking than Amy Adams.
AmySplaining (TM) FTW :-)
I love the 30 seconds of confusion.
I just got the book, "Divisors and Sandpiles" today and I'm very excited to start it... the introductory motivating problem is the dollar game. I can't figure out a proof as to why C6 with v0 = -2 and v2 = 2 and all other v 0 is unwinnable, but I feel that it is. The genus formula doesn't guarantee a winning strategy, since for that, the genus must be 1, but it's 0. C6 with v0 = -2 and v3 = -2 is clearly winnable and has same genus.
I am a simple man. I see holly, I press like and then watch the video
I am much more complicated. I see holly, i press like and pause the video.
Yes, one of my favorite persons on this channel!
See, this is what I love about math! This is the first time I've heard about a 'genus' in math context. I immediately thought about Euler's polygon formula: V - E + F = 2. The fact that you have similar tools/viewpoints/frames for both cases (polygons and graphs) is (amongst other things ) what maths is about. I love it!
Back to back Hannah then Holly? Brady, your spoiling us!
Hey, he's the one who gets to make the visits. I'm sure he's thanking us.
Guys, I'm fairly certain both Hannah and Holly are married. Please lay off. We get it; they're pretty. Let's get back to math.
+Theo_Caro Uh, I'm fairly certain the fact that they're married or otherwise taken is irrelevant to those who admire them. Oh and they're not just pretty.
We don't come here for maths, nerd.
@@kumquatmagoo xdddddd
Thats NumberWang!
35! 8! -4! 639!
122L!
Amazing!
let's rotate the bored!
Thats WangerNumb.
The graph has 87 vertices and 165 edges, giving it a genus of 79. The normal version has 113 dollars total and is definitely winnable (I found a solution in 195 moves). The secret version that flashes up for one frame has the same layout but only 22 dollars. This is less than the genus and probably not winnable.
I'd assume it's one of those special cases where it actually is winnable. There would be no reason to flash it on the screen otherwise.
Seeing ppl comment on the "redistributive" element of this game makes me want to ask: has anyone ever characterized economic models such as "socialism" or "laissez faire capitalism" or "crony capitalism" or "communism" etc. mathematically via graph theory? Cuz this video seems like EXACTLY the right place/way to start...
I think the subject you're looking for is economics. The whole point of that subject is to study the mathematics of the aggregate behavior of economic actors in those kinds of scenarios.
If you're looking for a basic analogy, then it'd be like this:
Capitalism is structured so that the most-connected nodes gain the most value, as long as they pay less than the value they receive. These nodes would be the bosses and CEOs and landlords and other rent-seekers.
Social democracy would try to redistribute the value from these concentrated nodes back to the mass nodes, but the whole process would be inefficient and take a long time to complete, and it also wouldn't prevent a re-accumulation because the graph system is still inherently tilted in favor of the highly-connected, lowly-paying nodes. Simply raising the pay rate isn't enough to solve the systemic issue.
Socialism would fundamentally change the graph system and even aim to abolish it entirely. One way of doing so would be to erase every single edge in the graph, create one large node in the center, and draw edges from that node to every other node; all value would be distributed from the central node. At that point, the distinction would be entirely in *how* that value is dispensed from that central node.
I would love to see this as an app to play around with. This applies to finances also
This is sort of related. If you have a house party and you are putting out snacks how many snacks to you put in each room? In a mathematically perfect house party with totally random and unbiased guests you simply have to count the doors.
Your guest will wander from room to room, picking any exit at random. After a while the distribution of guests will reach an equilibrium. It turns out this is stable when the number of guest in each room is proportional to the number of doors. So count the doors and put that many snacks in each room.
WAT?!!?11??!!
;-)
My argument for this partial solution is the following:
When a graph has a genus of zero, then that graph has zero cycles in it (i.e. no sections that form a loop). Increasing the number of vertices in a contiguous graph will still keep the genus at zero, because for the graph to remain contiguous you need to add a single edge that connects the new vertex to part of the existing graph. Thus, we can only increase the genus of a graph by creating cycles inside it. As we saw with a three-vertex cycle, any operation in that cycle will have three adjustments in value: prime node loses 2, and the two adjacent nodes gain 1 each; alternatively, the prime node gains 2, and the two adjacent nodes lose 1 each. The smallest possible amount of excess money we can have is 0 (example: a=-1 -> b=2 -> c=-1 -> a). If it was (a=-2 -> b=-2 -> c=0 -> a), then this would be unsolvable, because the distribution of negative or positive values will never be even enough to allow for it. If we add a single dollar to any of the nodes, though, then it becomes easily solvable.
That dollar has to come from somewhere though; imagine it being a node outside the cycle, (d=1 -> a). If we had d push this extra dollar into the graph, then it would be solvable, because d can immediately give back any dollars it gets to a. If we added a second node, (d -> c), then it becomes unsolvable again, because you don't have the extra value to pass around. You need to add an extra dollar to d, so that it can still pass its value in to a and participate. With this in mind, my suggestion is that you can validate if a graph is guaranteed solvable by removing nodes until you reach a minimum coverage graph, where each node is reachable through every other node with exactly one path. Each time you remove a node, you need to remove one dollar from a node. If you still have a net positive value at the end of this, then you are guaranteed to be able to solve this graph.
As for checking if a graph is impossible to solve, I have no clue.
tl;dr: You have no clue?
We definitely need a part 2. Maybe a proof on Numberphile2?
That's the spirit ;)
Firmula will be something with connection number
At 7:21 if you watch very carefully or change the playback speed the graph changes
Nice catch. More precisely, almost all 8's and 7's turn into 0's, except one 8 turns into 2, one 8 stays, one 7 stays.
After 20 minutes of scribbling on a whiteboard I have found that:
1. The least dollars that can travel in a closed loop at a time, is equal to the least connected vertex in that loop.
e.g. in the triangle graph, the least connected vertex has 2 edges; i.e. >= $2 must move in that loop at a time.
2. A loop is solvable if it has enough spare money to move in the loop less $1 (since a 1 connected vertex is not a loop).
e.g. in the triangle loop, since >= $2 must move at a time, and there is a spare $1, every 2x + 1 value can be reached.
note: some loops may be solvable without any spare $dollars as they may coincide with the minimum movable value (xth value).
3. A graph is a collection of connected loops, therefore a graph is solvable if all its loops are i.e. if it's most connect loop is.
i.e. A graph is solvable if the least connected vertex of the most connected loop - $1 is >= the spare $dollars on the graph.
4. The genus of a graph is always >= the least connected vertex of the most connected loop, therefore it will always be solvable.
5. By this logic, large graphs are more likely to be solvable, as they tend to have proportionally less edges per vertex.
i.e. size does not equal complexity. Although they may take longer to solve...
According to my calculations, there are 163 edges (a straight line connecting two vertices), 87 vertices (the round endpoints), and the sum of money on the board is $105. Given the circumstances for some games, as mentioned in the video, this game should be winnable, given that $105 > 163-87+1. I'll brute force this and see if it actually is winnable, though.
Happy numbercrunching Billennium to your Pascal cores....
:-/
@Kazutoification are you done yet? :x
another great show, thanks to both of you, have a great evening.
A Holly Krieger video right after a Hannah Fry video? Christmas came early!
It's called Christmas and a birthday at once in the UK.
...if he can get them both in the same video, I think it'd break the internet! :-D
@@neilwilson5785 My maternal grandmother's birthday literally _is_ Christmas. :)
And so did I!
OMG 😍
You could make a graph of all the possible moves you could make. Each edge is a move, each vertex is a game state. That gives you a tool for analyzing the game. You're looking for the shortest path from your game state to a winning game state.
In the move graph you'll always have as many edges for each node as the number of nodes in the graph being analyzed. The number of nodes will be infinite.
How many PetaBytes in *your* rig then?
Prove it :-)
At least you're thinking... :-)
I'm not nearly so excellent a mathemtician as Holly Krieger. :-) I mostly dabble in it as a side-interest and also to be better at writing software.
When I see a video with either Holly or Hannah in the thumbnail, I click. I really don'y care what they are discussing. I'll listen.
For any subset of vertices, consider the edges joining a vertex in the subset and a vertex not in the subset. It is always possible to send one dollar into the subset or out of this subset through these edges by either using all the vertices in the subset, or using all the vertices not in the subset.
If there is a bridge can be used to cut a problem satisfying the E-V+1 bound into 2 problems satisfying their E-V+1 bounds. Hence, we can assume there are no bridges. That solves all trees.
We can try to induct on the genus, E-V+1. Clearly, it is always possible when the genus is 0, as it is a tree. Suppose a solution is possible for every graph with certain genus g. Then, consider a graph with genus g+1. Ignore 1 edge and one dollar to reduce the genus (say edge from a to b, WLOG dollar on a) and pretend to solve the problem. What this does is that now, we can guarantee:
1. All vertices except possibly a, b, have nonnegative value.
2. As we used the edge between a and b some number of net times, their sum will still be nonnegative, in particular, we have value of a + value of b >= 1 (due to the ignored dollar). WLOG, value of a >= 2 and value of b
*somehow*...
I think you need to be a little more explicit in step N...
:-/
1:10 "and the goal of the game is to make sure everyone is out of debt."
Keynesian economists have left the chat!
what do keynesian "economists" know, anyway?
This channel is doing an amazing public service! I love it!
Amy Adams is so versatile! Great actress, beautiful and also smart!
That is not Amy Adams. That is the mathematician, Holly Krieger.
I guess the solution involves vector addition.
Each move is reversible, so you can start with zero dollars at each vertex and work backwards from there. For every point you have two operations. One is to add n to the vertex and subtract 1 from each of it's neighbours. The other is it's reverse.
This whole setup is like adding and subtracting vectors. It does not matter what order you add the vectors in. You only have to count how many times you add each vector, and multiply that vector by this number. Because the process is reversible you can also subtract the same vector, which is the same as multiplying by a negative.
You can visualize this for the three vertex case. Label each vertex (x,y,z). The vectors are +/- (-2,1,1),(1,-2,1) and (1,1,-2). If you do the first one 3 times and the second -2 times, you get (-8,7,1).
There are algorithms that can solve this sort of problem for indiscrete numbers. I don't know if they would be applicable to this problem.
Dunno... what are said algorithms?
What do their respective literature say about applicability?
...
I’d love to seen some proofs for this. Graph theory games are really interesting.
Two things:
a) Order of the moves doesn't matter
b) In planar graphs, the genus is the number of faces
This woman has a lovely laugh. She seems fun.
You can reduce this to an ILP problem, but that is NP hard. Let your variables be per vertex the amount of times you claim money (for example: 3 claim moves and 5 give moves will make the variable 3-5=-2, so this can be negative) The constraints are simple per vertex: starting money + amount of neighbors * variable - sum of variables of neighbors >= 0
Someone needs to make this an app! It would be a very fun game. Should be pretty simple to program.
I'm all in for a series of videos or huge video with the full explanation and information they've got so far!
That 30 seconds of confusion seemed like an eternity.
I apologize if this is mentioned already but if you donate money you don't have you're borrowing money from another entity unless you can create money.
So your solution in the first example where the point that went from -1 to -4 is either something like the Federal Reserve that creates money, or that move violates the game rules as it utilized a verticie that is not listed on your paper graph. Also, typically borrowing money comes at a premium rarely do you see 0% loans, so that node would likely owe MORE than what they gave.
You can use a little knot theory to come up with the vertices outlining the knots, and the crossovers would govern the + or - by direction. Snap pea program will show the characteristics of the knot, while the direction and vertices dictate the sums. The overall balance isn't important because the directionality of the process of exchange will show the problem areas (vertices that light up the most) as a probability spectrum of possible connections which would imply the number of vertices per unit is a function of the length to complete a cycle, not balance out the "budget". Once cycled the unlit areas will be the isolated Islands of incomplete transactions, aka the crossovers, or genus, of the outlayed knots that replaced the vertices. Maybe some dehn twist to show an anti correlation at the complex arena, possibly showing why extra routes may inhibit whole areas from even participating. Excuse the vagueness
Here the case is clear: We have a subgraph with nodes -1 and -2 which has debts of 3 Dollars. It is -2 to get Dollars. It will do so 1 time and also 3 will give one time.
Now the subgraph is to be balanced and the node with 3 needs toget one from 2. We have to distribute within the subgraph which takes 2 further takes from the leave. 5 steps are minimum.
It got my head spinning like a centrifuge.
Please could you show the names of all the books present on the shelve.
I need to stop crushing on Holly Krueger. I really really do. 😍
The genus/sum connection is about how much control you have over dividing up the money. A graph with very few connections means you have more control over how the money moves around; after all, a vertex connected to only one other vertex gives you absolute control over where you send the money, because you can always give or take from a specific vertex. The more highly connected the graph is, the more spare cash you need, because you aren't able to divide it amongst the vertices as evenly as you would like.
I suspect that's an accurate and more straightforward explanation of the genus/dollar connection.
Bit like a bank really eh...
Has there been research on this game? I was trying to find some literature on this, but I only ended up with the Auction Theory Dollar Bidding Game. Some more in depth theory about this would be very interesting!
Try looking up chip firing on graphs.
There is a link in the description to Matt Baker's blog. Baker is co-author of the paper in which the winning criteria are proved. In his blog there is a link to his joint paper from 2007.
I actually took an entire course on the subject! Look up Matt Baker or the book Divisors and Sandpiles: An Introduction to Chip-Firing by Scott Corry and D. Perkinson
As a computer scientist, since we rely a lot on graph theory and algorithmic complexity computation, I wonder if anyone may have referred to such works to improve performance of multicore computation, since it can be seen as a problem of fairly distributing work among workers (pre-requisite being for tasks not being mutually dependent - think scalar chips like GPUs maybe). Since the overall computation time would amount to the node/vertice with the highest value, optimising would reduce the global computation time. However the way to compute the optimal distribution seems pretty complicated and may often take longer than the computation itself... I’m pretty sure there should be references in the field. I’ll have to look it up :) And the same kind of problem could also be considered with parallel factory work I guess, or in biology with cells or ants maybe, so other fields may have worked on the topic too...
SIGARCH Sub time 4 U!!!11!! :-)
While it seems like commenters have already figured out that the monster puzzle at 8:42 and linked in the description is solvable, it looks like the one shown at 3:50 with "how few moves can you win the game in" is a troll. The genus is 11 with 4 dollars on the board!
Numberphile you should tottaly do a video on spinors vectors and tensors!
tidbit about a spinor is that rotating it 360 degrees does not return it to its original position, yet rotating it 720 does! eventhough 720=2×360!
There are already videos on that. The "belt trick" is the classic illustration. The right way to think about it is that it's the spinor's relationship with the phases of its neighbors that changes after one rotation, not so much anything "internal" to the spinor itself, so it's not as strange as it sounds. The belt trick video shows how those "connections" get "twisted" after one rotation and "untwisted" after another.
The fact that the amount of money needed to guarantee a winnable situation is the genus, quite elegant
Careful: "$ >= genus guarantees a valid game" is not the same thing as "$ >= genus is NECESSARY to guarantee a valid game." The former is true, the latter is trivially false (a graph of just a single vertex with $0 wins, but has a genus of 1).
@@Kwyjibo28372 I did mean the former, although I see the ambiguity in my statement
That would make a really nice casual game for mobiles.
Sssshhh!!
some guy in the comments made it into an app
This is such a cool game for a small programming challenge!
In a perfect world dollar stores would offer puzzles to customers that if worked out and proved solvable/unsolvable they could get dollar discounts on their dollar items.
The perfect world doesn't have dollar stores.
My city doesn't really have dollar stores anymore. They used to be everywhere, but I can't remember seeing any recently.
this is the best numberphile video, its not just entertainer and educational like most of other I also learn a new game, so I can be still entertained after the video end
Thank you for calling a vertex a vertex. I work in 3d and it drives me absolutely nuts how often veteran animators and modelers will refer to a singular "vertice" (ver-tis-see).
NICE !!!! It would make for a game that is really fun to play and not that difficult to program (the logic that is). The more I think about it the more I recognize the brilliance of the rules. Who invented those rules? Simple/Straight/Exact ... you just have to love it. The number equivalent to Tetris.
But is there a way to figure out whether it is COMEBACKABLE?
In the 3 vertices, 3 edges (triangle) the genus is 1. There's a trivial solution where all vertices are 0. You have already won. This will also be the case for all genus > 0 where all vertices contain 0 or > 0 dollars.
It is always a pleasure seing a video by Dr. Holly Krieger. :)
This doesn't exactly solve anything but may be interesting to someone.
- Any turn you can take is reversible: "Vertex V takes" is reversible with "vertex V donates" and the other way around. Therefore, if you can get from configuration A to configuration B, you can also necessarily get from configuration B to configuration A by reversing all moves. Therefore if you cannot get from configuration B to configuration A, you also cannot get from configuration A to configuration B. And finally, therefore, if and only if you can get a configuration from any winning configuration, this configuration represents a winnable game.
- Order of turns doesn't matter: Donating causes the vertex to lose n dollars, where n is number of its edges, and each neighbor vertex to gain 1 dollar, regardless of when in the game this happens. Similarly this goes for taking. I don't exactly know how to write this in proper maths but a vertex' final bank is its starting value + edge count*(times it took - times it donated) + sum of times its neighbors donated - sum of times its neighbors took.
- That also implies that if a vertex takes and also donates in a single game, these turns cancel out both for this vertex and for its neighbors. If we cancel them out, each vertex either did nothing, donated n times, or took n times. As donating is the reverse of taking, we can consider donating n times as taking -n times. This way we can describe any set of moves without redundant fluff by assigning an integer to every vertex.
- Any winnable game can be described with a combination of a winning configuration and this move set description, and any such combination describes a winnable game.
I think I may have just found what I am going to write my dissertation on next year. Some opportunities for some programming and some pure maths!
How is the dissertation writing going? :-)
This reminds me of using the Critical Path Method to solving a flow issue between various processes in manufacturing, etc. Usually the CPM is used in relationship to time.
This was so interesting, not sure if I could design games well enough for my students to try. Also, I think I just fell in love XD
The (probably) optimal solution for the graph they solved by hand:
Let the labels of the vertices be A=-2, B=-1, C=1, D=2, E=3
A takes once.
B takes twice.
D gives once.
E gives once.
It's just a takes once, b takes once. 0 is ok.
I'm positive about this
Consider the "impossible" triangle graph in the video with values 1, 0, -1. As always, there does exist the cheeky solution using infinity. First, let's make it r, 0, -r for generality since r doesn't need to be 1. Make the r give r/2 to each. The r is now 0, the 0 is now r/2, and the -r is now -r/2. For the positive value, do the same thing. r/2 gives r/4 to each. r/2 is now 0, 0 is now r/4, -r/2 is now -r/4. If you continue this infinitely then all nodes will approach 0, meaning the limit is a solution. Although this is more of a math joke, I wonder if this can be done for any "impossible" graph, which ones can't if not, what methods if can, and how to prove it can or can't. I did a lot of thinking on the original problem, and did some nice findings, but I'm a little too worn out to give it any thought at the moment, so feel free to answer what might be an easy, fun, and/or insightful find.
Is the brown paper a mathmo thing, an MIT thing or do you record this next to the postal department?
recyclable etc
I think it would also be interesting if you had an opponent who tries to prevent you from winning and you and the opponent take turns.
I do like math games. This one seems like it has some possibilities. I wonder if there's an application for this in game theory...
y'think?
Or in name-dropping...
?
I wasn't thinking of how to determine if it's winnable or not, I was thinking of how to program the lowest number of moves needed. I was thinking of a set of two numbers per node, one number is how many it connects to and the second number is the total directly connected to it. Maybe a third number indicating true/false if there's a negative number connected to the node. Then somehow work the nodes in some order.
This would make an interesting mobile phone app.
calculating the genus sounds a lot like the Euler Formula (if it were for only 2 dimensions)
It's actually related, check out 3blue1brown's video on the Euler Formula, he uses the fact that a complete graph always in two dimensions always has a genus of one :)
That massive board is actually possible; I got it in 810 moves after a bit of optimization. Can anyone beat that?
Alternate way to win:
- Screw your neighbours
- Take the money and run
Go on, take the money and run, Whoohoohoo!
...and the graph theory remains unchanged! This is what I love about real math.
Nathan-DTS that's not capitalism, though... because capitalism is the mutual benefit of goods and services being exchanged.
The Major. That's the theory, sadly practice has revealed aspects of capitalism that probably merit an evolution investigation to bring us a more updated definition so that we are all on the same page.
+The Major A starving orphan "benefits" from being taken as a slave by a plantation owner. Capitalism involves the same kind of "mutual benefit." It's fundamentally asymmetric and exploitative. It relies on system of property relations that can't be rationally agreed to by a large chunk of the population.
Holly: Triangle configuration is not winnable
Me: *makes the vertices 0, -1, and 2*
Beautiful teacher )
We created a web version. You can find a link in the recent Numberphile twitter post. For some reason I cannot post a link in the comments.
I think i am in love .
we all are
Great strategy for people helping one another, say like a large family pool of members,buy a home buy a car get out of dept, practically anything can be done for one another by chipping in. The the only thing that would hinder this process is the greed factor.
7:16, lovely laughter, besides being a great video.
For the 3 vertex all connected example, it is winnable with $0, provided one vertex has $2 and the other two have -1 each.. then you can win in 1 move
Regardless of the content of the video: what a beautiful laughter she has!
Another proof that mathematics isn't dull
(Can be fun!). Thanks Holly.
On the triangle graph it would work with '0' with the config:
/(2)\
(-1) - (-1)
Yeah, it's not a bi-conditional. The test is inconclusive when the sum is less than the genus.
This man has discovered the secrets of the universe
0 always work for every possible configuration with a 0 in each vertices.
@@allasar - I wonder if there is a transformation that lets you turn graphs that are ambiguous into simpler graphs that aren't?
As far as i'm aware, you can't really turn one graph into another, since simply moving nodes around doesn't count as different graphs. However, you might be able to focus on smaller portions of the graph at a time, balancing out the smaller graphs to better balance out the entire graph as a whole. That gets further into game theory though.
Some observations:
1. You always gave, never took, even though taking was explained initially, and it seems it would have helped to keep the number of moves minimal.
2. While graph theory is an obvious choice to tackle this kind of puzzle, I smell a set of linear (in-)equations (one for every game) as well. For the first example graph, and with nodes A…E ordered from top to bottom and left to right, and t(N), g(N) denoting the number of times we've taken to or given from node N, and A'…E' the new values for each node, we get (if I counted correctly):
A' = 1 + 2*t(A) - t(C) - t(E) - 2*g(A) + g(C) + g(E)
B' = -1 + t(B) - t(C) - g(B) + g(C)
C' = -2 - t(A) - t(B) + 3*t(C) + g(A) + g(B) - 3*g(C)
D' = 2 + t(D) - t(E) - g(D) + g(E)
E' = 3 - t(A) - t(C) - t(D) + 3*t(E) + g(A) + g(C) + g(D) - 3*g(E)
These are our linear equations, and the unknowns are the t(N) and g(N). But they don't describe a solution - too many unknowns and no idea yet of what A'…E' should be. We need more constraints, and we do have the following inequations that describe the objective of the game: A' >= 0, …, E' >= 0. Now, a straightforward Gaussian elimination will not give us a solution here. However, I think we could use Gaussian elimination as a tool by (for the moment) allowing rationals and searching for manifolds that intersect zero in one or more outputs… we could also look for intersections with the total sum for the graph… this could give us some acceptable boundaries to work with. I'll admit this is a very rough sketch, and it's been a long time since I studied linear algebra.
7:19 seems that puzzle is in a quantum state.
I thought the same thing when I saw the simple graph with 0,1 and -1 in a triangle: "that must represent some fundamental notion of superposition or entanglement."
Not if the zero gives. it will do :
/-2\
2 -2
and then let the 2 give twice.
@@titip1995 If the zero gives the -1 becomes 0, not -2.
Well, assuming I didn't mess up anywhere while programming this, I made a simple program and wrote a unit test with the big game at the end as its data:
Edges: 154
Vortices: 87
Genus: 68
Sum of vortex values: 90
Game should be winnable because sum > genus
But if you add a vertex that's not connected to the graph, the genus decreases.
I guess each disconnected component should be considered seperately.
i assume that the requirement is [altough its not stated] that the graph must connected, else you can make any game unwinnable by adding a vertex not connected and with a 'score' of -1.
Or at least a union of disconnected graphs is winnable iff each component is winnable.
Here's a neat idea for an expansion of that concept: have several graphs each with multiple vertices that are interconnected with edges. Each of the separate graphs are connected with "super-edges" which must then be somehow "balanced" in the same way as the "lesser" graphs. (I know, it is a very rough concept, but I thought I'd throw it out there.)
How's that different from the superedges being normal edges and just connecting the graphs?
@8:43
You have:
165 -
87 .
That is a Genus = 79
The Total $ is 105
105 > 79
Yes you can Win this Game
I've got a trick. Take any amount of currency, how do make it lose 96% of value?
Simple, Make the currency fiat, Let the fed lend it to the banks! Magic!
Holly's laugh can cure cancer.
I think I'm in love
The initial game they played by hand could be won with 6 moves:
- vertex with initial 1 donates ones,
- vertex with initial -1 takes from all once,
- vertex with initial 2 donates twice,
- vertex with initial 3 donates twice.
Order of the moves is actually unimportant.
You can always win the game if all values are 0, regardless of the genus.
Yes obviously but that's pointless because the purpose of the game is to get someone out of debt and there has to be someone who *is* in debt
Yeah but I thought somebody should point it out. :)
Or if there are no negative values.
This is called a trivial case - the game is won before you even start, hence there is no need to point it out.
@@iliakorvigo7341
In maths there is a need to point everything out.
We are dealing with absolutes here.
And considering trivial cases might well help figuring out more solutions as you differentiate several cases.
I found a pretty intuitive way to prove this for Genus=0,1 and I think it can be a beggining to the prove for genus=n (maby by using induction). Also i'm 17 yo and Englisg isn't my native language so sorri four bed inglish.
First we need to notice that every vertex which is connected to only one other vertex and also it's number is 0 can be ignored because if we choose that every time that the vertex that connected to it donates this vertex will also donate it's like no one ever donated to it.
Second we can notice that if a vertex number isn't 0 we can make it 0 like this:
(1) if it's negative we donate to it untill it's 0.
(2) if it's positive we donate from it until it's negative (or 0) and then step one (if it's negative).
For genus = 0:
the graph must be a tree(no circles) so we can make all the leafs(vertices which are connected only to one other vertex) of the tree values to be 0 and than ignore them and than we can do the same things to the leafs which were created because we ignored the leafs from before and we can keep doing this until were left with only one vertex (the root) which has the sum of all vertices (which must be 0 or bigger).
For genus = 1.
we can look at this as a tree which have been added to it one edge that is connecting to vertices on with height(length from root) h1and other h2. Now if are ignoring all the leafs we can and keep doing it we're left with one big circle (instead of one vertex) which have h1+h2+1 vertices (and edges)
now we seperate it to 2 different cases:
(1) h1+h2+1=3:
we already know for this case that the statement is true (it's the case of the 3 vertices and 3 edges from the video)
(2) h1+h2+1>3:
we can focus on one of the vertices and make it's value 0, now we can notice that we can ignore it becuase if every time we donate from one of its neighbors we also donate from it than since it's 2 neighbors are not connected (h1+h2+1>3) it's like this vertex didn't exist (when one of it's neighbors donate it's like it donated directly to the other neighbor). So now we can choose one random vertex from the circle and ignore it and keep doing this until we only have 3 vertices amd than we go back to case 1.
Never clicked on a video faster
I hope it was because of Holly and not because maths.
9:30 The obvious example of "amount of money < genus but still winable" is some monster graph with an astronomical genus, and 0 in each vertex.
Or just the triangle with all zeroes :D
Well, you can make it boring if you want to. ^^
7:23 I'm sorry but that's the sexiest "Do you want to know the answer?" I've ever seen
Hahaha, looking for that comment! Someone else must had picked that up.
The case of a specific connectivity preventing a graph/system from being reaching a unique optimal configuration also occurs in physics.