BTW before anyone gets any bright ideas about trying this in real life:<p>This is called "layering" and is often a criminal offense [1] and banks have effective means to detect it (as they are required to by law). In particular they are highly attuned to flows of money that seem to split up large bunches of cash into smaller amounts that the would-be money launderer thinks will be below some static threshold. The detections which catch this have been in all banks I've ever worked with (since around 2010 when I first touched on doing any anti-moneylaundering work and they were very mature and well-established by then)[2].<p>You are highly unlikely to get away with it unless you have already been doing it for some time or know someone who has and is willing to share their techniques.<p>[1] Obviously or not it's only a criminal offense if you doing it to evade detection (eg for tax fraud or to avoid paying say a court settlement or something) or are otherwise laundering the proceeds of crime - that sort of thing. If you're just doing it for your own amusement it will probably get you added to a watchlist of suspicious accounts at your bank that they will monitor extra closely and may get you investigated by various financial crime enforcement organisations. Which even if you haven't done anything wrong I imagine would be stressful and time-consuming.<p>[2] To give people who are not part of this world the idea, at least in the UK and US all employees of any kind of deposit-taking institution are required by regulators to have an annual anti-moneylaundering training which covers layering and how to detect it. So literally every bank employee should know what this pattern looks like and should be on the look out for it.
This is Subset Sum and is famously NP-complete so, no, an LP doesn't work. However, the problem is only weakly NP-hard and there is a pseudo-polynomial time algorithm running in time O(M • n) where M is the sum and n is the number of accounts.<p>The problem is, perhaps, most of all, that it takes the same amount of space.<p>Ps, it's not a permutations problem, but a subsets problem. While permutations is n! subsets are "only" 2^n.
I used to walk people through the "2sum" and "3sum" variants of this for an interview question. I was not looking for anything complicated, such that it was easy enough to talk through solutions that we could play with. Had a few people that would take us down some rather complicated approaches. (Even gave offers to some that got through some complicated solutions that wouldn't work.)<p>I never tried doing an "optimal" solution. Thinking about the problem, I'm curious if a BDD approach wouldn't work? Will try and write one up to see. Fun times.
In the real world this would be more complicated, because there could be more mixing and withdrawals. Banks also have a lot of visibility into account transactions, at least in the case of accounts which they would know the balances for.
No, money needs to be like Monero and the state can f- right off with their panopticon financial surveillance. Sometimes it's better to be armed and tolerate or handle an occasional little bad-guy, than it is to succumb to a supermassive Goku-monster bending you over a barrell and freeing you into life-long [legal] disability with his gargantuan **** of [In]Justice™ for failure to report and pay that last $40 in income tax!<p>Ben Franklin on security and liberty, or something.