Mathematics desk
< April 14	<< Mar \| April \| May >>	April 16 >

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.

April 15

Equations Over Ring

Hi, is solving a system of linear equations over the ring $\mathbb {Z} _{n}$ (integers modulo n), for some fixed n, in $P$ ? (references will be appreciated) — Preceding unsigned comment added by 185.32.179.222 (talk) 13:27, 15 April 2016 (UTC)[reply]

For a fixed set of equations surely the brute force method - checking each of the n elements in

\mathbb {Z} _{n}

- takes time that is linear in n. Or for fixed n and a variable set of linear equations, the time will be linear in the number of equations. So in

P

either way. Or have I completely misunderstood the question ? Gandalf61 (talk) 15:43, 15 April 2016 (UTC)[reply]

I meant that the equations are multivariate (in

m

variables), and thus there're

n^{m}

options using the brute force method. 213.8.204.18 (talk) 15:50, 15 April 2016 (UTC)[reply]

Ah. Understood. Finally. Gandalf61 (talk) 15:59, 15 April 2016 (UTC)[reply]

Diophantine equation#System of linear Diophantine equations may possibly be helpful in getting you started toward the answer. It has a reference down at the bottom of the section. Loraof (talk) 16:33, 15 April 2016 (UTC)[reply]

Specifically, you can easily convert the system over Z_n to one over Z. Replace each equation (lhs)=k (mod n) with (lhs)+ns_i=k, where the s_i's are new variables. Solving systems of equations over Z, uses a modified form Gaussian elimination. Gaussian elimination is polynomial time, at least if you don't take coefficient size into account, but I don't know if the modifications needed change that. I think it just involves applications of the Euclidean algorithm, also polynomial, so it should still be in P. Btw, if instead of determining whether there is a solution you're required to find a best approximation, i.e. maximize the number of equations that are satisfied simultaneously, the problem becomes NP-hard. Unless I'm mistaken this is the called decoding problem for linear error correcting codes. --RDBury (talk) 17:03, 15 April 2016 (UTC)[reply]

It's a great reduction from Z_n to Z! Thank you! 185.32.179.40 (talk) 19:10, 16 April 2016 (UTC)[reply]

Dice puzzle

This youtube video was posted a few days ago and I thought it might be of interest to the regulars here. There are two problems described, an easy one to kind of explain what's allowed, and a hard one which is left unsolved. --RDBury (talk) 20:04, 15 April 2016 (UTC)[reply]

Care to list them here, so we don't all have to watch the video ? StuRat (talk) 22:30, 15 April 2016 (UTC)[reply]

Simulate one fair die given three indistinguishable fair dice: answer take the sum of the three mod 6
Simulate two fair dice given three indistinguishable fair dice: answer...

--catslash (talk) 22:44, 15 April 2016 (UTC)[reply]

Sorry, I thought the video explained it better than I could so it would be easier to just watch it. Basically you have three dice rolled at the same time, and using anything that distinguishes one from the other, e.g. the value of the one closest to you, is cheating. In other words you just know low, middle and high values. You can simulate a single die by taking the sum modulo 6. You can simulate two die by assigning values to each of the 56 possible outcomes for the 3 die, but this requires consulting a table for every throw. So the question is can it be done with a simple rule as for a single die. Here simulate means that the probabilities work out the same, so e.g. you can't just take the low and high values. It's not entirely clear from the video how simple is simple enough to count as a solution, or whether you have to simulate two distinguishable die, two indistinguishable die, or the sum of two die, so just take your pick I guess. --RDBury (talk) 02:48, 16 April 2016 (UTC)[reply]

Implied in the mapping onto "36 categories" would be the first case: two distinguishable dice. Though I suspect he hadn't really thought about it. —Quondum 03:33, 16 April 2016 (UTC)[reply]

As an analogous solution, would tossing the three dice twice and summing the six results mod 12 work? EdChem (talk) 04:02, 16 April 2016 (UTC)[reply]

Nope, I'm sure this would not even remotely produce the distribution of a sum-of-two-dice. There would be a simple solution if two throws were permitted: use the single die result twice (i.e. mod 6 on each throw). —Quondum 04:16, 16 April 2016 (UTC)[reply]

It seems to me that there is an argument that there is no "neat" solution (one that does not involve at least some form of clunky table): The six cases of all three numbers the same must all be mapped to either one or two values, since this is the only way to get 36 equal-probability buckets. This inherently leads to an irregular mapping onto the 36 values. I'm assuming that we require two distinguishable die as the result, though I suspect a similar argument will rule out "neat" indistinguishable and sum cases. —Quondum 04:33, 16 April 2016 (UTC)[reply]

I think that there is no way to use a "clunky" table to map from sum-of-3 outcomes to sum-of-2 outcomes while preserving probabilities. The probabilities for the sum-of-2 values 2, 3, 4, ..., 10, 11, 12 are (multiplying through by 6/6 to get a convenient denominator) 6/6³, 12/6³, 18/6³, ..., 18/6³, 12/6³, 6/6³. The probabilities for the sum-of-3 values 3, 4, 5, 6, ..., 15, 16, 17, 18 are 1/6³, 3/6³, 6/6³, 10/6³, ..., 10/6³, 6/6³, 3/6³, 1/6³, with all other values being greater than 10/6³. To get a matching probability of 6/6³, wlog take sum-of-3 value 5. To get the second probability also 6/6³, take value 16. Then to get probability 12/6³, the only way is to combine the sum-of-3 values 3 and 6 and 18. But then there's no way to combine values to get the other 12/6³ probability. Unless I've screwed up the arithmetic. Loraof (talk) 19:30, 16 April 2016 (UTC). Of course, it might be doable if you're allowed to put e.g. 1, 2, 3 and its permutations in one bucket while putting 2, 2, 2 in a different bucket even though it has the same sum. Loraof (talk) 19:46, 16 April 2016 (UTC)[reply]

Here's an algorithm that's simple enough to memorize and execute quickly. Let A, B, C be the input dice in an order that lexicographically minimizes the cyclic differences ((B−A) % 6, (C−B) % 6), where % is a remainder operator that returns a value in {0,1,2,3,4,5}. If those two differences are:

01, 02, 03, 04, 05: The first output die is 4, 5, or 6, whichever is congruent to A mod 3, and the second output die is the second difference (1, 2, 3, 4 or 5)
11, 12, 13: The first output die is the second difference (1, 2, or 3), and the second output die is A.
22: The first output die is 4 or 5, whichever is on one of the input dice, and the second output die is 6.
00: Double sixes.

-- BenRG (talk) 23:41, 16 April 2016 (UTC)[reply]

I can confirm that this works (via the method of an excel spreadsheet), nice one! — crh ₂₃ (Talk) 18:50, 18 April 2016 (UTC)[reply]