How to solve these equations?
We are given following equations:
a1 ^ a2 ^ a3 = A
a2 ^ a3 ^ a4 =B
a3 ^ a4 ^ a5 =C
a4 ^ a5 ^ a6 =D
a5 ^ a6 ^ a1 =E
a6 ^ a1 ^ a2 =F
Here A,B,C,D,E,F are given and ^ denotes bitwise XOR.
How can we solve these equations to find a1 a2 a3 a4 a5 and a6?
a1 ^ a2 ^ a3 = A
a2 ^ a3 ^ a4 =B
a3 ^ a4 ^ a5 =C
a4 ^ a5 ^ a6 =D
a5 ^ a6 ^ a1 =E
a6 ^ a1 ^ a2 =F
Here A,B,C,D,E,F are given and ^ denotes bitwise XOR.
How can we solve these equations to find a1 a2 a3 a4 a5 and a6?
Well you could start with A ^ F = a1 ^ a2 ^ a3 ^ a6 ^ a1 ^ a2
Anything exclusive-or'ed with itself is 0, so you can cancel out a1 and a2 from that expression.
It's just a matter of working through successive steps like that to isolate each one.
Anything exclusive-or'ed with itself is 0, so you can cancel out a1 and a2 from that expression.
It's just a matter of working through successive steps like that to isolate each one.
what about solving a general case i.e finding a1 .... an through n equations consisting of 3 terms as above??
they are all zero. That works. They are all one, that also works. (just being silly, because with no values for A-F I set them all to zero and all to 1)
that aside, are you solving for bits here, or numbers?
Substitution seems likely. I would try C&D first.
a3 ^ a4 ^ a5 =C
a4 ^ a5 ^ a6 =D
a3 ^ a4 ^ a5 ^ a4 ^ a5 ^ a6 = C^D
a4 ^ a5 ^ a4 ^ a5 (these cancel out, I think, right?)
leaving a3^a6 = C^D
which could mean that a3 = C and a6 = D if I did that right.
It could also be that a3 = D and a6 = C. But its a start. I just realized its the same as above just different starting point.
you may know more with the values of C&D. If C^D is 0, then either C and D are both zeros or C==D, for example (so either way C==D if the result is zero).
if you keep doing these you should be able to get the whole left hand side down to A-F.
do the whole thing. resolve A^B^C^D^E^F and drop all the cancelled terms out. See what is left.
it may also be useful to review xor:
https://en.wikipedia.org/wiki/Exclusive_or
that aside, are you solving for bits here, or numbers?
Substitution seems likely. I would try C&D first.
a3 ^ a4 ^ a5 =C
a4 ^ a5 ^ a6 =D
a3 ^ a4 ^ a5 ^ a4 ^ a5 ^ a6 = C^D
a4 ^ a5 ^ a4 ^ a5 (these cancel out, I think, right?)
leaving a3^a6 = C^D
which could mean that a3 = C and a6 = D if I did that right.
It could also be that a3 = D and a6 = C. But its a start. I just realized its the same as above just different starting point.
you may know more with the values of C&D. If C^D is 0, then either C and D are both zeros or C==D, for example (so either way C==D if the result is zero).
if you keep doing these you should be able to get the whole left hand side down to A-F.
do the whole thing. resolve A^B^C^D^E^F and drop all the cancelled terms out. See what is left.
it may also be useful to review xor:
https://en.wikipedia.org/wiki/Exclusive_or
Last edited on
| jonnin wrote: |
|---|
| which could mean that a3 = C and a6 = D if I did that right. It could also be that a3 = D and a6 = C. But its a start. |
Sure it *could* mean that, but it probably doesn't.
I don't believe the system of equations posed in the OP has a solution.
This is for a CodeChef problem, btw.
https://www.codechef.com/DEC18A/problems/INTXOR
| Browni3141 wrote: |
|---|
| I don't believe the system of equations posed in the OP has a solution. |
I agree.
Try, for example, (row 6) XOR (row 1) XOR (row 3) XOR (row 4): you will get 0 = ....
Last edited on
depends on what A-F are. its certainly solved if all A-F are 0 or all A-F are 1.
Otherwise, you could get no solution very easily, and you could get multiple solutions as well I believe ?
0 = is fine, as long as the other side is also zero.. but you have a very good point :)
Of course its codechef. Who else comes here asking difficult pointless (fun, but pointless) questions?
Otherwise, you could get no solution very easily, and you could get multiple solutions as well I believe ?
0 = is fine, as long as the other side is also zero.. but you have a very good point :)
Of course its codechef. Who else comes here asking difficult pointless (fun, but pointless) questions?
Last edited on
The system has rank 4, so it either has no solutions or a lot of solutions, depending on A-F.
Topic archived. No new replies allowed.