Wikipedia:Reference desk/Archives/Mathematics/2012 September 9

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

September 9

Isomorphism between G/N x N ~= G

Is there always an isomorphism between the quotient of a group G and a normal subgroup N with the direct product of N to G?

G/N × N ≈ G

Is there a theorem for that? --helohe (talk) 12:39, 9 September 2012 (UTC)

No, because it's not true. The simplest counterexample is $G=S_{3}$, which contains normal a subgroup generated by the 3-cycles, $N=\langle (123)\rangle$. Then $G/N\cong \mathbb {Z} _{2}$, but $G$ is not abelian, so $G\ncong N\times \mathbb {Z} _{2}$. — Preceding unsigned comment added by COVIZAPIBETEFOKY (talk • contribs) 13:16, 9 September 2012 (UTC)

I think it should work if you use the semidirect product instead. —Kusma (t·c) 08:35, 10 September 2012 (UTC)

This fails even for abelian groups: C₄/C₂ ≃ C₂, but C₄ is not isomorphic to $C_{2}\rtimes C_{2}$. In general, G is the semidirect product of N and G/N if and only if the exact sequence $1\longrightarrow N\longrightarrow G\longrightarrow G/N\longrightarrow 1$ is right split.—Emil J. 15:25, 10 September 2012 (UTC)

Thank you for the correction. —Kusma (t·c) 07:11, 11 September 2012 (UTC)

Finding the constituent numbers in a list that add up to partial totals

I was wondering of there was a methodology I could use for future reference for a problem I had the other day. I had 28 undated invoices, each with amounts and I had three checks that I knew were payments, each of more than one invoice on that list but not which ones and they were not in any order and I had to match the payments to which invoices they covered. Complicating matters, I also knew that the checks were only partial payment of the total invoices--they would match exactly some combination of the invoices but not all. I took me a few hours to actually figure it out by trial and error, playing with the numbers in excel, and I know there has got to be a better way. Let me provide the actual numbers and the solution so you'll know what I mean (I also think there might be a computer program that might solve this but I had no idea how to look for such a program). Here goes:

Invoices

$18.43
$23.91
$7.32
$234.65
$10.13
$11.55
$34.60

$67.37
42.81
$75.44
$233.45
$98.43
$91.36
$31.04

$72.94
$58.38
$26.48
$95.02
$78.45
$66.57
$48.30

$57.67
$49.30
$23.86
$87.88
$89.47
$35.33
88.40

Checks

check 1: $327.79
check 2: $437.66
check 3: $381.18

As you can see, I've color coded the solution. The red invoice amounts equal the red check exactly, and the same for green and blue and the uncolored were those invoices that were not paid. But I started with no idea which invoices equaled which checks. I never want to have to do this again blindly.--108.54.25.10 (talk) 13:35, 9 September 2012 (UTC)

The most obvious answer is to keep better track of things in the first place (date your invoices), so you don't need to try to figure it out after. However, a trial-and-error program is the obvious solution. If you want, I could even write you one and send it to you. However, there is the possibility of multiple solutions. StuRat (talk) 14:53, 9 September 2012 (UTC)

This is the Subset sum problem. Taemyr (talk) 15:02, 9 September 2012 (UTC)

Looking at the most brute force approach of just trying every amount in one of 4 categories (including those that don't match anything), I get an unmanageable 4^28 possible combos, or some 72 quadrillion. That approach is definitely out. A more elegant approach might be to just look at which items add up to the lowest total first. StuRat (talk) 15:17, 9 September 2012 (UTC)

Interesting. Do you know of an existing program online to plug in numbers and get a solution? If not, I will take you up on that offer Stu (I use macs, which I thought you might need to know to make the program work for me) My email is ammtss AT yahoo DOT com. By the way, they are not my invoices. I am an attorney matching proof to make a coherent presentation to a jury on a property damage suit; the invoices are for building supplies paid to a third party by my client for the rebuild after massive flood damage. There were some clues in the invoices that helped me narrow down into categories and mix and match from there or I don't think I could have done it.--108.54.25.10 (talk) 15:31, 9 September 2012 (UTC)

That explains it then. I was wondering how anyone could solve such a complex problem by hand. StuRat (talk) 16:50, 9 September 2012 (UTC)

I have some bad news for you. When I said there might be multiple solutions, that was apparently an understatement. I wrote a program to solve it, and came up with 623 possible solutions. Your solution was the 11th. Here's just one more (the 63rd):

  78.45
  58.38               91.36
  57.67               89.47
  48.30               75.44
  35.33               72.94
  23.91    233.45     42.81
  18.43     98.43     34.60
+  7.32   + 49.30   + 31.04
=======   =======   =======
 327.79    381.18    437.66

So, the solution you found and presented in court may not be correct. Therefore, even with a program, you will end up with a large number of possibilities, and no way to know which one is correct. I'm afraid you're down to either presenting the evidence as your client gave it to you, getting your client to give you better info, or lying in court and claiming that one of the solutions you found is the correct one, when you really don't know that. StuRat (talk) 05:51, 10 September 2012 (UTC)

What strikes me about the figures is they seem rather peculiar. There's no duplicates and they don't look like the prices people charge and don't evem look like ones with some tax added. The first digits don't follow Benford's law at all. I've had unfortunately soemtimmes had to deal with money which hadn't been properly tracked and there's all sorts of things one can check - the people who wrote a checque, what kind of item the amounts correspond to, the dates etc. In this case your client can probably ietmize most of the things bought and when and a check with the suppliers catalogue could then say for the ones that were remembered what the price was. The dates of the remainder with a list of where the others fit would then prompt more and might suggest what was being worked on at the time. Dmcq (talk) 16:40, 10 September 2012 (UTC)

I would never try to brute-force problems like this, and you don't have to. First of all, you don't need to check 4^28 combinations, you can split the problem and try to cover the smallest check first.

That would be 2^28 combinations if brute-forced, but you can sort the items by size and take the biggest item that will "fit." Let's say you want to cover the $327.79 check first. The $233.45 item will fit so it'll reduce the problem to another one, namely, "Try to cover the remaining $94.34 using the remaining 27 items." The $98.43 item won't fit but the $91.36 item will - that'll be layer 3, and you'll immediately see that there is no solution to the remaining $2.98. So you backtrack to recursion layer 2 and try the next item on the list, $89.47. etc, etc.

The point is that you can eliminate large classes of solutions quickly, for example that neither the combination 233.45+91.36 nor 233.45+89.47 is part of the $327.79 check.

And what happens to the other items can be determined if/when you have all solutions to the $327.79 anyway. Any solution will eliminate some of the 28 items, so by solving the smallest check first, you'll even save quite a bit of work later on.

Maybe some backtracking of the invoices or the checks can narrow the possibilities a bit. I doubt that it can kill 622 of your 623 solutions though. The quantities are still odd. They look close to equidistributed between $0 and $100, except that items below $5 are multiplied by 100; this looks like a made-up math problem rather than actual invoices.

Kudos to Dmcq, you beat me to Benford. - ¡Ouch! (^{hurt me} / _{more pain}) 07:07, 11 September 2012 (UTC)

The approach you list is close to what I did in my program, although I started with the smallest item, not the largest. I'm amazed at how fast the program is (about 4 seconds of real time on my low-end PC, increasing to 53 seconds if I take the time to print out the results), considering how utterly unworkable the full brute force approach is. StuRat (talk) 16:58, 11 September 2012 (UTC)

Benford's law can only be applied to data that are distributed across multiple orders of magnitude. Ssscienccce (talk) 17:57, 11 September 2012 (UTC)

Here's the list of all 623 solutions:

(I removed the 200+KB of text that was here; it is permanently archived at [1]. -- BenRG (talk) 00:35, 12 September 2012 (UTC))

Same link, but shorter (and not forcing SSL) is this. --CiaPan (talk) 07:27, 12 September 2012 (UTC)

StuRat (talk) 20:12, 11 September 2012 (UTC)

To clarify: I tried to match invoices to the smallest check because I was hoping that the number of invoices would be small. There's a better approach WRT worst case:

-Add a 4th check which makes the sum of checks equal the sum of invoices. I.e.

Check 4 = (invoice 1 + invoice 2 + ... + invoice 4) - (check 1 + check 2 + check 3).

By introducing that virtual check, you can simplify the problem to an "every invoice is in exactly one check" type of problem.

Then you can do a run over the data like the one I sketched in my previous reply, with the additional constraint that there must be at least one check covering only 28/4 = 7 or fewer invoices. This may or may not be the smallest check, though, and it can be the virtual one.

You might be unlucky and have to try all checks until you find the one consisting of 7 or less items, but there are

(28*27*26*25*24*23*22) / 7! = 1184040 possible 7-item picks out of 28, far fewer than 2^28, so the worst case has been vastly imorived.

Once you have one of these checks (say it covers exactly n invoices), you know that at least one of the remaining 3 checks covers at most

(28 - n) / (4 - 1) invoices. And so on.

For the record, I was only commenting on the odd distribution, rather than suspecting an actual DYOH violation. My aology if it looked that way. - ¡Ouch! (^{hurt me} / _{more pain}) 07:03, 13 September 2012 (UTC)

I accept your "aology" and agree that your method is "imorived". :-) However, even when you find the 7 item or fewer total, you still have quite a bit of work to do to solve the rest. And, since there are 623 solutions, you have to do all of this over many times. StuRat (talk) 05:14, 14 September 2012 (UTC)