The Dollar Game - Numberphile

[@burkeysvids]

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]

You do know what the -phile suffix means, right?

[@PaulSzkibik]

@@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.

[@jaypi6423]

You gotta love what you do, if you write on a carton paper with a marker

[@Triantalex]

false.

[@tomatoanus]

numberphile and drawing on brown paper. name a more iconic duo.

[@peachout6227]

Matt and his Parker Square Cliff Stoll and his Klein Bottle James Grime and his singing banana

[@climatixseuche]

Me and Holly

[@halulife35]

peanut butter and jelly

[@Banan_Gutten]

Fitz-Simmons

[@jordanmoseley3019]

tomatoanus and speedrunning

[@marcusprice3199]

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.

[@JJ-kl7eq]

As a pessimist I prefer to play the deficit spending game where all vertices have to have a negative number

[@vizionthing]

are you a banker?

[@JJ-kl7eq]

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.

[@karthiknaicker8216]

Multiply all vertices by -1 to get the pessimist's version?

[@WaltRBuck]

Oh, you're a politician.

[@drmontorsi7498]

Keynes would be proud

[@Rgmenkera]

Somebody should make an app of this game

[@AntonioNoack]

Working on it :D, will be usable in a few hours I think. (idk yet exactly how long it'll take XD)

[@aner_bda]

Would love to play this game if you get it working.

[@stefanhrvatski9152]

This comment is only here, so youtube informs me, when you write again.

[@chandir7752]

Surprisingly there is no app with the name "the dollar game" yet.

[@jeanotzubler2477]

@@AntonioNoack yes please

[@ninjaforest]

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.

[@WTFPr0m]

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.

[@raphielohnef4678]

I'd love that, too :)

[@yungacid1]

You're not alone.

[@samarendra109]

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)

[@stefan1024]

At some level you start comparing it to other equivalent math problems and then it gets very abstract.

[@stefan1024]

it never is. :)

[@lystic9392]

I love the 30 seconds of confusion.

[@hugolabs]

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!

[@coolpipe1]

Thanks!

[@daniellovick1546]

At 7:21 if you watch very carefully or change the playback speed the graph changes

[@rasowa2958]

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.

[@Ninja9191]

I love it when Amy Adams explains stuff!

[@oncedidactic]

Lol it’s true though. Holly should play the mathematician hero in the next scifi film adaption of a Ted Chiang story like Arrival.

[@Dmlaney]

Holly is gorgeous

[@wolfelkan8183]

Kangaroo

[@PartScavenger]

Except Holly is way better looking than Amy Adams.

[@RogerBarraud]

AmySplaining (TM) FTW :-)

[@dattanandraykar]

I am a simple man. I see holly, I press like and then watch the video

[@RafaelMarcF22]

I am much more complicated. I see holly, i press like and pause the video.

[@WilliamKibirango]

This channel is doing an amazing public service! I love it!

[@wolfelkan8183]

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.

[@ruukinen]

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.

[@niclaskristiansen9533]

Yes, one of my favorite persons on this channel!

[@dannyg1812]

Thats NumberWang!

[@Diditallforthexp]

35! 8! -4! 639!

[@elemenopi9239]

122L!

[@jam8munch811]

Amazing!

[@blazeitup420]

let's rotate the bored!

[@dannyg1812]

Thats WangerNumb.

[@ferrariscuderia4290]

1:10 "and the goal of the game is to make sure everyone is out of debt." Keynesian economists have left the chat!

[@banger107]

what do keynesian "economists" know, anyway?

[@c.james1]

Back to back Hannah then Holly? Brady, your spoiling us!

[@takatotakasui8307]

Hey, he's the one who gets to make the visits. I'm sure he's thanking us.

[@Theo_Caro]

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.

[@argh1989]

+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.

[@kumquatmagoo]

We don't come here for maths, nerd.

[@TileBitan]

@@kumquatmagoo xdddddd

[@tinynewtman]

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.

[@RogerBarraud]

tl;dr: You have no clue?

[@thumper8684]

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.

[@RogerBarraud]

WAT?!!?11??!! ;-)

[@vorpal22]

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.

[@atrumluminarium]

We definitely need a part 2. Maybe a proof on Numberphile2?

[@atrumluminarium]

That's the spirit ;)

[@camfunme]

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...

[@RadioactiveLobster]

A Holly Krieger video right after a Hannah Fry video? Christmas came early!

[@neilwilson5785]

It's called Christmas and a birthday at once in the UK.

[@flyguy000]

...if he can get them both in the same video, I think it'd break the internet! :-D

[@agiar2000]

@@neilwilson5785 My maternal grandmother's birthday literally _is_ Christmas. :)

[@aaronbyrd420]

And so did I!

[@peterboyford9673]

OMG 😍

[@PabloNevares]

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!

[@alexanderpoth9995]

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!

[@dalek2538]

Try looking up chip firing on graphs.

[@stevethecatcouch6532]

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.

[@code-cave]

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

[@ElCeceh]

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...

[@RogerBarraud]

SIGARCH Sub time 4 U!!!11!! :-)

[@richardpg2704]

another great show, thanks to both of you, have a great evening.

[@BryonLape]

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.

[@erichopper4979]

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.

[@RogerBarraud]

How many PetaBytes in *your* rig then?

[@RogerBarraud]

Prove it :-)

[@RogerBarraud]

At least you're thinking... :-)

[@erichopper4979]

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.

[@Torchman-]

That 30 seconds of confusion seemed like an eternity.

[@chadwilson618]

I would love to see this as an app to play around with. This applies to finances also

[@Kazutoification]

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.

[@RogerBarraud]

Happy numbercrunching Billennium to your Pascal cores.... :-/

[@HMR_Sekai]

@Kazutoification are you done yet? :x

[@clarencechew3971]

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

[@RogerBarraud]

*somehow*... I think you need to be a little more explicit in step N... :-/

[@micronalpha]

It is always a pleasure seing a video by Dr. Holly Krieger. :)

[@ChristianoMDSilva]

I'm all in for a series of videos or huge video with the full explanation and information they've got so far!

[@HammerandNeil]

Someone needs to make this an app! It would be a very fun game. Should be pretty simple to program.

[@omafalk443]

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.

[@edudey]

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...

[@Xezlec]

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.

[@obvious_humor]

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.

[@Pedro999Paulo]

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

[@seanm7445]

Alternate way to win: - Screw your neighbours - Take the money and run

[@mikeguitar9769]

Go on, take the money and run, Whoohoohoo!

[@billsemenoff]

...and the graph theory remains unchanged! This is what I love about real math.

[@livedandletdie]

Nathan-DTS that's not capitalism, though... because capitalism is the mutual benefit of goods and services being exchanged.

[@eideticex]

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.

[@lavamatstudios]

+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.

[@BarneyIX]

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.

[@sarysa]

7:19 seems that puzzle is in a quantum state.

[@edtsch]

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."

[@titip1995]

Not if the zero gives. it will do : /-2\ 2 -2 and then let the 2 give twice.

[@yehoshuas.6917]

@@titip1995 If the zero gives the -1 becomes 0, not -2.

[@Donbros]

Firmula will be something with connection number

[@elliotvernon7971]

Is the brown paper a mathmo thing, an MIT thing or do you record this next to the postal department?

[@kaiserauthoria]

recyclable etc

[@columbus8myhw]

Two things: a) Order of the moves doesn't matter b) In planar graphs, the genus is the number of faces

[@Xomage999]

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.

[@smurfyday]

The perfect world doesn't have dollar stores.

[@caenir]

My city doesn't really have dollar stores anymore. They used to be everywhere, but I can't remember seeing any recently.

[@SmileyMPV]

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

[@maxximumb]

That would make a really nice casual game for mobiles.

[@RogerBarraud]

Sssshhh!!

[@irusvzi]

some guy in the comments made it into an app

[@subhadipdas3918]

Please could you show the names of all the books present on the shelve.

[@darts421]

I’d love to seen some proofs for this. Graph theory games are really interesting.

[@MasterHigure]

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.

[@raphielohnef4678]

Or just the triangle with all zeroes :D

[@MasterHigure]

Well, you can make it boring if you want to. ^^

[@lamintouray7386]

It got my head spinning like a centrifuge.

[@thumper8684]

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).

[@thumper8684]

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.

[@RogerBarraud]

Dunno... what are said algorithms? What do their respective literature say about applicability? ...

[@LionidasL10]

This woman has a lovely laugh. She seems fun.

[@terdragontra8900]

The fact that the amount of money needed to guarantee a winnable situation is the genus, quite elegant

[@Kwyjibo28372]

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).

[@terdragontra8900]

@@Kwyjibo28372 I did mean the former, although I see the ambiguity in my statement

[@sengchamrong5993]

But is there a way to figure out whether it is COMEBACKABLE?

[@chipblock2854]

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.

[@fuseteam]

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!

[@Xezlec]

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.

[@Fenrakk101]

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.

[@RogerBarraud]

Bit like a bank really eh...

[@thermotronica]

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

[@kurtschatteman5193]

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.

[@nymalous3428]

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...

[@RogerBarraud]

y'think? Or in name-dropping... ?

[@fane7063]

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.

[@CTJ2619]

calculating the genus sounds a lot like the Euler Formula (if it were for only 2 dimensions)

[@HAL-oj4jb]

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 :)

[@Randy_McShandy]

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

[@seventeeen29]

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!

[@flyingpenandpaper6119]

How is the dissertation writing going? :-)

[@alexandersukhanov5691]

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.

[@floheissler2336]

Amy Adams is so versatile! Great actress, beautiful and also smart!

[@michaelerickson985]

That is not Amy Adams. That is the mathematician, Holly Krieger.

[@MathIguess]

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

[@fome53]

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

[@karljay7473]

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.

[@meithecatte8492]

But if you add a vertex that's not connected to the graph, the genus decreases.

[@jonp3674]

I guess each disconnected component should be considered seperately.

[@SvenBeh]

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.

[@jonp3674]

Or at least a union of disconnected graphs is winnable iff each component is winnable.

[@nymalous3428]

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.)

[@smurfyday]

How's that different from the superedges being normal edges and just connecting the graphs?

[@Ajoscram]

This is such a cool game for a small programming challenge!

[@ymi_yugy3133]

Is it possible to have more one edge between two vertices?

[@calcoph.]

You could make an alternate version but i guess the genus things would change.

[@xCorvus7x]

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.

[@ymi_yugy3133]

@@xCorvus7x I think two edges would mean you have to send 2 dollars to one vertex.

[@calcoph.]

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.

[@xCorvus7x]

@@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.

[@erniejudge9311]

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.

[@MonsterHealthandFitness]

I need to stop crushing on Holly Krueger. I really really do. 😍

[@paslasks]

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?

[@RogerBarraud]

There's this li'l thang called Google...

[@paslasks]

Which I tried to no avail. My guess is in academia this is not called 'the dollar game,' thus my request for a link.

[@bjarnes.4423]

On the triangle graph it would work with '0' with the config: /(2)\ (-1) - (-1)

[@didles123]

Yeah, it's not a bi-conditional. The test is inconclusive when the sum is less than the genus.

[@anamikarai7240]

This man has discovered the secrets of the universe

[@Errzoin]

0 always work for every possible configuration with a 0 in each vertices.

[@erichopper4979]

@@allasar - I wonder if there is a transformation that lets you turn graphs that are ambiguous into simpler graphs that aren't?

[@arcuesfanatic]

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.

[@guitar81sb]

The case of a specific connectivity preventing a graph/system from being reaching a unique optimal configuration also occurs in physics.

[@abhijitborah]

7:16, lovely laughter, besides being a great video.

[@jasonmintzchannel8902]

Holly: Triangle configuration is not winnable Me: *makes the vertices 0, -1, and 2*

[@kev3d]

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).

[@MrSimpsondennis]

so, watched up to 7:15 and came to this conclusion: If you have an open end AND there is enough money in the game, just move all the money towards the open end and work it out from there, always winnable. If you have a closed board, try to look for a way to emulate an open end, solve that open end and use that to work out the rest. (post vid edit) just split up the graph into multiple genes and check each gene for possibility seems to be the easiest way. (first example would be 2 0-genes and 1 1-gene) so that would make it that you need 1 dollar on board. Modularity is the trick.

[@steffahn]

Hmm, I neither see how "just move all the money towards the open end" nor how "work it out from there" is supposed to work in general. Quite the opposite is true, an "open end" (by which I believe you mean a vertex only connected to a single edge") is something quite boring, it doesn’t help with a solution at all, as you can just "ignore it". Start out by making its balance be 0 and then every time it changes, change it back to zero. If you think about it, the rest of the game then works as if the extra edge+vertex were not even there. This means, you you can solve a particular graph if and only if you can solve the same graph with an extra "open end" attached to it.

[@MrSimpsondennis]

With open end I indeed mean a vertex with only 1 connection. And well, it basically works like a battery/holding cell, allowing you to gradually work your way out from there. You can at any time guarantee that that point will be positive, from there on you can go to the next point. If the next point has 2 outgoing vertexes, you have to make sure that the 'incoming' vertex (the open end) has a stockpile of 1, so that when the one after the next point when it splits up gives one back to the previous one, which you can then fill up with the stockpile so that one can split open again. It's kinda hard to put in words ^^" Basically, make it so your branch will always be nurished.

[@TheRealFlenuan]

7:23 I'm sorry but that's the sexiest "Do you want to know the answer?" I've ever seen

[@porschepanamera92]

Hahaha, looking for that comment! Someone else must had picked that up.

[@perceive8159]

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.

[@ameba2804]

Regardless of the content of the video: what a beautiful laughter she has!

[@supermarble94]

That massive board is actually possible; I got it in 810 moves after a bit of optimization. Can anyone beat that?

[@apdgslfhsodbna]

Beautiful teacher )

[@user_2793]

I was able to prove that if every possible combination is attainable (enough to show that debt free configs exist), the graph must be a spanning tree (no loops - any two vertices are connected by a unique path). This is just a sufficiency condition though, as this game is winnable for certain non spanning trees. Still I'm proud of this, cause I don't know graph theory formally :) I will post the full solution to this weaker problem if anyone's interested.

[@StefanReich]

You can always win the game if all values are 0, regardless of the genus.

[@frabol02]

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

[@StefanReich]

Yeah but I thought somebody should point it out. :)

[@xCorvus7x]

Or if there are no negative values.

[@iliakorvigo7341]

This is called a trivial case - the game is won before you even start, hence there is no need to point it out.

[@xCorvus7x]

@@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.

[@ARP2wefightforyou]

An example of when you can win when the number of dollars is less than the genus: that three vertex game where everything was connected, but with $2, $-1, and $-1.

[@עמריטפלא]

Quickburger9000 Deal with it yes

[@HemantGanti117]

"Dunder Mifflin,this is Pam"

[@esthoril]

That's what I was searching for, exactly the same mouth movement!

[@DavePawson]

Another proof that mathematics isn't dull (Can be fun!). Thanks Holly.

[@zarathustra7139]

I think i am in love .

[@SnabbKassa]

we all are

[@88predy]

We did the very same thing in static calculation during the college. We just called it degree of static freedom. Pretty neat thing.

[@jmaymay1997]

Never clicked on a video faster

[@ongbonga9025]

I hope it was because of Holly and not because maths.

[@mediumjohnsilver]

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).

[@BuzzaB77]

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!

[@QuilloManar]

Holly's laugh can cure cancer.