Follow

I have five stacks of three blocks. I can join two stacks together, or split a stack.
How many splits and joins do I need to do to end up with three stacks of five blocks?

· · Web · 3 · 1 · 2

My real question is: for A stacks of B blocks into B stacks of A blocks, is it ever the case that the strategy that minimises joins is not the same as the strategy that minimises splits?

@christianp No, I don't think so. There are suboptimal ways of doing splits and joins, but if you are only considering the optimal cases, there's only one way to minimize joins, and that's by minimizing total segments, and to do that you must minimize splits.

Answer (attempt) 

@christianp 2 splits, 4 joins.

@christianp

4 joins 2 splits one way:
3 3 3 3 3
-> 6 3 3 3
-> 5 1 3 3 3
-> 5 4 3 3
-> 5 7 3
-> 5 5 2 3
-> 5 5 5

4 joins 2 splits another way:
3 3 3 3 3
-> 6 3 3 3
-> 9 3 3
-> 12 3
-> 15
-> 10 5
-> 5 5 5

4 joins 2 splits a third way:
3 3 3 3 3
-> 6 3 3 3
-> 5 1 3 3 3
-> 5 1 6 3
-> 5 1 5 1 3
-> 5 5 2 3
-> 5 5 5

don't have the time at the moment to generalize but i did not expect to get the same thing from three different approaches

That second one is perhaps the most telling.

Oh, but for A|B that "stack everything" is not optimal, of course. What about gcd(A,B)>1, so in the smallest interesting case 4,6? There you can get 4j2s, better than the stack-all 5j3s.

Sign in to participate in the conversation
Mathstodon

The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!