18
\$\begingroup\$

Consider a binary operator \$*\$ that operates on a set \$S\$. For simplicity's sake, we'll assume that \$*\$ is closed, meaning that its inputs and outputs are always members of \$S\$. This means that \$(*, S)\$ is a magma

Let's define some basic terms describing the properties of \$*\$. We can say that \$*\$ can have any of these properties, if they hold for all \$a,b,c \in S\$:

  • Commutative: \$a*b \equiv b*a\$
  • Associative: \$(a*b)*c \equiv a*(b*c)\$
  • Distributive: \$a*(b+c) \equiv (a*b)+(a*c)\$, for some binary operator \$+\$ on \$S\$

We can also define 3 related properties, for a unary operation \$-\$ on \$S\$:

  • Anti-commutative: \$a*b \equiv -(b*a)\$
  • Anti-associative: \$(a*b)*c \equiv -(a*(b*c))\$
  • Anti-distributive: \$a*(b+c) \equiv -((a*b)+(a*c))\$

Finally, we define 3 more, that only describe \$*\$ if the complete statement is true for \$a,b,c \in S\$:

  • Non-commutative: There exists \$a, b\$ such that \$a*b \not\equiv b*a\$ and \$a*b \not\equiv -(b*a)\$
  • Non-associative: There exists \$a, b, c\$ such that \$(a*b)*c \not\equiv a*(b*c)\$ and \$(a*b)*c \not\equiv -(a*(b*c))\$
  • Non-distributive: These exists \$a,b,c\$ such that \$a*(b+c) \not\equiv (a*b)+(a*c)\$ and \$a*(b+c) \not\equiv -((a*b)+(a*c))\$

We now have 9 distinct properties a binary operator can have: commutativity, non-commutativity, anti-commutativity, associativity, non-associativity, anti-associativity, distributivity, non-distributivity and anti-distributivity.

This does require two operators (\$-\$ and \$+\$) to be defined on \$S\$ as well. For this challenge we'll use standard integer negation and addition for these two, and will be using \$S = \mathbb Z\$.

Obviously, any given binary operator can only meet a maximum of 3 of these 9 properties, as it cannot be e.g. both non-associative and anti-associative. However, it is possible to create a function that is, for example, neither commutative, anti-commutative or non-commutative, by creating an operator \$*\$ such that \$a*b = b*a\$ for some inputs and \$a*b = -b*a\$ for others. Therefore, it is possible to create an operator that meets fewer than 3 of these properties.


Your task is to write 9 programs (either full programs or functions. You may "mix and match" if you wish).

Each of these 9 programs will:

  • take two integers, in any reasonable format and method

  • output one integer, in the same format as the input and in any reasonable method

  • be a surjection \$\mathbb Z^2 \to \mathbb Z\$ (takes two integers as input and outputs one integer). This means that for any distinct output, there is at least one input that yields that output

  • uniquely exhibit one of the 9 properties described above.

This means that, of your nine programs, one should be commutative, one associative, one distributive over addition, one anti-commutative, one anti-associative, one anti-distributive, one non-commutative, one non-associative and one non-distributive.

Your programs must each exhibit exactly 1 of these 9 behaviours, and violate the other 8. For example, multiplication would be banned, as it is commutative, associative and distributive. However, this also means that 6 of your programs must not be e.g. any of commutative, anti-commutative or non-commutative. How you reconcile this is up to you.

This is ; the combined lengths of all 9 of your programs is your score, and you should aim to minimise this.

Additionally, you should include some form of proof that your programs do indeed have the required properties and do not satisfy the other properties. Answers without these are not considered valid.

Alternatively, your answer may be in the form of a proof of impossibility. If this is the case, you must prove that there are no such operators that are valid answers to this. You do not have to show that all 9 properties are impossible to exhibit - only one - in this proof. In this case, there can only be one answer, which, by default, will be the winner.

\$\endgroup\$
4
  • \$\begingroup\$ Sandbox. This has been discussed a decent amount in chat, and appears to be a very difficult challenge. This is an easier version I have in the Sandbox \$\endgroup\$ Jun 15 '21 at 20:19
  • \$\begingroup\$ "Obviously, any given binary operator can only meet a maximum of 3 of these 9 properties, as it cannot be e.g. both non-associative and anti-associative" What about the constant zero function on Z: forall a,b, a*b = 0. Then * is both commutative, associate and distributive, and anti- all three of those. \$\endgroup\$
    – Stef
    Jun 16 '21 at 13:13
  • \$\begingroup\$ In reference to Robin Ryder's answer, if \$(ab)= 4\$ hours, or \$(ab)= \pi /3\$ radians, then \$4(a∗b)=−2(a∗b)\$ and \$a∗b \neq 0\$ \$\endgroup\$
    – Yijapod
    Sep 23 '21 at 5:41
  • \$\begingroup\$ The question specifies \$S = \mathbb Z\$, which has no zero divisors. \$\endgroup\$ Sep 23 '21 at 8:19
20
\$\begingroup\$

Proof of impossibility

The only anti-distributive operator when \$S=\mathbb Z\$ is such that \$\forall a, \forall b, a*b=0\$.

Indeed, suppose that \$*\$ is anti-distributive. Then \$*\$ has the following property, for all \$ a,b,c\in\mathbb Z\$:

  • (D) \$a*(b+c) = - (a*b+a*c)\$

(In my notation, \$*\$ has precedence over \$+\$.)

Take \$a,b \in \mathbb Z\$. By (D),

\$a*(2b) = a*(b+b) = - (a*b + a*b) = -2(a*b)\\ a*(3b) = a*(2b+b) = -(a*2b + a*b) = -(-2(a*b) + a*b) = a*b\\ a*(4b) = a*(2b+2b) = -(a*2b + a*2b) = -(-2(a*b) -2(a*b)) = 4(a*b)\\ a*(4b) = a*(3b+b) = -(a*3b + a*b) = -(a*b + a*b) = -2(a*b) \$

Hence \$4(a*b) = -2(a*b)\$ and \$a*b=0\$.

We thus have that \$\forall a,\forall b, a*b=0\$.

The only anti-distributive operator is therefore always equal to \$0\$. In particular, it is commutative, anti-commutative, associative, anti-associative, distributive, anti-distributive, and not a surjection. It is therefore impossible to exhibit an operator which is only anti-distributive.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Do you have any thoughts on this one? Just asking because we want to avoid another impossible challenge. \$\endgroup\$
    – Bubbler
    Jun 16 '21 at 8:01
  • \$\begingroup\$ @Bubbler Thanks, I'm thinking about it. I don't think there exists an anti-distributive surjective operator when S=Z... \$\endgroup\$ Jun 16 '21 at 8:40
  • \$\begingroup\$ @xnor Nice and terse! I was editing in a variation of my proof while you were commenting. Indeed, anti-distributivity implies that all products are 0 when \$S=\mathbb Z\$. There might be a non-0 solution with \$S=(\mathbb Z/2\mathbb Z)^k\$ instead. \$\endgroup\$ Jun 16 '21 at 9:01
  • 6
    \$\begingroup\$ (Replacing with a bit cleaner proof) Here's a neat way that I think works to show that anti-distributivity implies any product equals zero for \$S=\mathbb{Z}\$. We have \$ a * b = a * (b+0) = - (a * b) - (a * 0)\$, so \$ a * b \$ must be half of \$-(a * 0)\$ in the standard integer sense. This implies that the product \$ a * b\$ doesn't depend in \$b\$ but only on \$a\$, say \$ a * b=f(a)\$. Then, the anti-distributivity rule \$a * (b+c) = -(a*b + a*c) \$ gives \$f(a) = - (f(a)+f(a))\$ so \$f(a)=0\$, and thus any product is \$0\$. \$\endgroup\$
    – xnor
    Jun 16 '21 at 9:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.