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.
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.
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)
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!
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.
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.
+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.
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.
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.
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.
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.
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...
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...
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.
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 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.
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.
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).
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.
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.
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!
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 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.
I wonder, would “Scramble Squares” puzzles be related to graph theory? That’s a puzzle for arranging nine squares into a larger square, making sure that each edge matches its complement (like the +2 edge matching a -2 edge).
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
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 :)
I wonder if there's any connection between solving this and the travelling salesman problem, I'm going to assume that finding the optimal solution to a solvable graph is going to be NP-hard
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.
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.
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."
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.)
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.
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).
We can also try and reduce the graph in the following 2 ways before solving ... 1: If a node is connected to only one other node...(as in the first example 2 is only connected to 3 and -1 is only connected to -2) then transfer the value of the node to the node it's connected and remove it. 2: If there's a node with value 0 and all other node connected to zero are also mutually and directly connected we can remove that node with value 0. I think this simplifies the graph. Am i right? There may be more such reducing techniques for this game.
You may try to define rules for that but it does not really make sense as it is, since every edge only serves to show where money can flow. More edges between same points would not change that.
The way I see it is that if there were 2 edges instead of taking or giving 1$ at a time it would take/give 2. So a vertex could be linked to 2 vertices, one with only one edge and the other with 2 edges, so it would take/give 3$ each time while only being conected to 2 vertices.
@@calcoph. +Ymi_Yugi Oh, so you give/take one dollar per edge and not one dollar to/from each neighbour. But I doubt that this would change much, since you have to give/take one dollar per edge every time, so with more than one edge between two points now only a larger amount of money is shoved back and forth.
I've looked for some papers on it and it seems dr Krieger didn't explain the rules fully. What is presented in the video is "lending move", ie. picking a vertex and distributing out one dollar along every edge. There should be "borrowing moves" as well, that's picking a vertex and bringing one dollar to it along every edge.
another interesting thing to add is whenever the sum is less than the genus, there is a starting configuration of dollars summing to that number that's actually not winnable.
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).
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!
You might be interested in the math behind the card game Spot It; simple premise with some really interesting math behind it. A bit much to explain but the math behind it is crazy
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.
Okay so if any is solvable and you have a total other than 0, you could take away all of the money from all of the locations with a remainder at the end exactly equal to the remainder from the start. That means that any solvable sequence can be solved with a total of 0 correct? To clarify I mean that once you've reached a solution and a location, for example has 2 left over, then you could do that same configuration with the same moves except that that one location could start with 2 less and it would end at 0 instead of 2. If you did this for all ending locations that means that they would all end at 0. So the genus test might show if you can solve it, but also if it could always pass with, say 1000 dollars, why couldn't you subtract that exact starting amount, divided evenly based on its ending location in the solution, and therefore also have the same solution starting with 0? This would make every possibility solvable right? Or would that not work based on relative distribution. Idk just a thought
If you represent the distribution of dollars over all nodes with a vector v and the connections between those nodes with matrix M, then the goal is to find a vector w, such that v + M * w is a vector containing no negative numbers. If the numbers contained by vector w can be any real value, then this problem would be a piece of cake to solve, since it would be an LP problem. Of course this is not the case, which turns it into an ILP problem, which means it's related to the P = NP problem.
@@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.
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
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.
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.
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. :)
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
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.
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!
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.
Yes, one of my favorite persons on this channel!
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??!!
;-)
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.
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
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 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.
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?
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
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.
Thats NumberWang!
35! 8! -4! 639!
122L!
Amazing!
let's rotate the bored!
Thats WangerNumb.
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
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?
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.
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!! :-)
Two things:
a) Order of the moves doesn't matter
b) In planar graphs, the genus is the number of faces
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.
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...
We definitely need a part 2. Maybe a proof on Numberphile2?
That's the spirit ;)
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.
Is the brown paper a mathmo thing, an MIT thing or do you record this next to the postal department?
recyclable etc
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...
:-/
But is there a way to figure out whether it is COMEBACKABLE?
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.
This channel is doing an amazing public service! I love it!
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.
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 😍
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.
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...
This woman has a lovely laugh. She seems fun.
Someone needs to make this an app! It would be a very fun game. Should be pretty simple to program.
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.
Please could you show the names of all the books present on the shelve.
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...
?
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!
That 30 seconds of confusion seemed like an eternity.
another great show, thanks to both of you, have a great evening.
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 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.
Amy Adams is so versatile! Great actress, beautiful and also smart!
That is not Amy Adams. That is the mathematician, Holly Krieger.
I wonder, would “Scramble Squares” puzzles be related to graph theory? That’s a puzzle for arranging nine squares into a larger square, making sure that each edge matches its complement (like the +2 edge matching a -2 edge).
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
Another proof that mathematics isn't dull
(Can be fun!). Thanks Holly.
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 :)
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
It got my head spinning like a centrifuge.
I wonder if there's any connection between solving this and the travelling salesman problem, I'm going to assume that finding the optimal solution to a solvable graph is going to be NP-hard
I need to stop crushing on Holly Krueger. I really really do. 😍
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.
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? :-)
I'm all in for a series of videos or huge video with the full explanation and information they've got so far!
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
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.
That would make a really nice casual game for mobiles.
Sssshhh!!
some guy in the comments made it into an app
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.
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.
I would love to see this as an app to play around with. This applies to finances also
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?
The case of a specific connectivity preventing a graph/system from being reaching a unique optimal configuration also occurs in physics.
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.
Wouldn't finding the optimal strategy for fewest moves be equivalent to trying to solve the travelling salesman problem?
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).
We can also try and reduce the graph in the following 2 ways before solving ...
1: If a node is connected to only one other node...(as in the first example 2 is only connected to 3 and -1 is only connected to -2) then transfer the value of the node to the node it's connected and remove it.
2: If there's a node with value 0 and all other node connected to zero are also mutually and directly connected we can remove that node with value 0.
I think this simplifies the graph. Am i right?
There may be more such reducing
techniques for this game.
Is it possible to have more one edge between two vertices?
You could make an alternate version but i guess the genus things would change.
You may try to define rules for that but it does not really make sense as it is, since every edge only serves to show where money can flow.
More edges between same points would not change that.
@@xCorvus7x I think two edges would mean you have to send 2 dollars to one vertex.
The way I see it is that if there were 2 edges instead of taking or giving 1$ at a time it would take/give 2. So a vertex could be linked to 2 vertices, one with only one edge and the other with 2 edges, so it would take/give 3$ each time while only being conected to 2 vertices.
@@calcoph.
+Ymi_Yugi
Oh, so you give/take one dollar per edge and not one dollar to/from each neighbour.
But I doubt that this would change much, since you have to give/take one dollar per edge every time, so with more than one edge between two points now only a larger amount of money is shoved back and forth.
I remember Genuses/Genii (I am not aware of the correct plural form) being used in Euler's theorem for 3 Dimensional shapes with enclosed volume
If you want a Latin plural it would be 'genera', but I doubt that people use that.
I'm positive about this
I've looked for some papers on it and it seems dr Krieger didn't explain the rules fully. What is presented in the video is "lending move", ie. picking a vertex and distributing out one dollar along every edge. There should be "borrowing moves" as well, that's picking a vertex and bringing one dollar to it along every edge.
another interesting thing to add is whenever the sum is less than the genus, there is a starting configuration of dollars summing to that number that's actually not winnable.
It is always a pleasure seing a video by Dr. Holly Krieger. :)
I'd like to see a program that allows you to play this game and analyzes your moves.
Beautiful teacher )
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
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!
Can you provide a link to a paper proving that if the dollar amount on the board is greater than or equal to the genus then the game is winnable?
There's this li'l thang called Google...
Which I tried to no avail. My guess is in academia this is not called 'the dollar game,' thus my request for a link.
Regardless of the content of the video: what a beautiful laughter she has!
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.
7:16, lovely laughter, besides being a great video.
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. ^^
I think i am in love .
we all are
You might be interested in the math behind the card game Spot It; simple premise with some really interesting math behind it. A bit much to explain but the math behind it is crazy
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.
Okay so if any is solvable and you have a total other than 0, you could take away all of the money from all of the locations with a remainder at the end exactly equal to the remainder from the start. That means that any solvable sequence can be solved with a total of 0 correct? To clarify I mean that once you've reached a solution and a location, for example has 2 left over, then you could do that same configuration with the same moves except that that one location could start with 2 less and it would end at 0 instead of 2. If you did this for all ending locations that means that they would all end at 0. So the genus test might show if you can solve it, but also if it could always pass with, say 1000 dollars, why couldn't you subtract that exact starting amount, divided evenly based on its ending location in the solution, and therefore also have the same solution starting with 0? This would make every possibility solvable right? Or would that not work based on relative distribution. Idk just a thought
Never clicked on a video faster
I hope it was because of Holly and not because maths.
@8:43
You have:
165 -
87 .
That is a Genus = 79
The Total $ is 105
105 > 79
Yes you can Win this Game
Okay, second video I have seen with this lady...........I think I have a crush :)
If you represent the distribution of dollars over all nodes with a vector v and the connections between those nodes with matrix M, then the goal is to find a vector w, such that v + M * w is a vector containing no negative numbers. If the numbers contained by vector w can be any real value, then this problem would be a piece of cake to solve, since it would be an LP problem. Of course this is not the case, which turns it into an ILP problem, which means it's related to the P = NP problem.
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.
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
Holly molly! I'm in love with this math!
Who is Molly?
That massive board is actually possible; I got it in 810 moves after a bit of optimization. Can anyone beat that?