[VA] My 2024's very first little teaser

[Valentin Albillo]

      
Hi, all,

In my OP I said 8 days ago: "If I see interest I'll post in a few days two different solutions". Regrettably, I've seen very little interest indeed but never mind, first I want to thank power forum's members PeterP and J-F Garnier for their interest in this teaser and for posting very nice working solutions, congratulations guys, much appreciated !

Now I think that a little disquisition is in order. I created this teaser several months ago and it was originally intended to be an April 1st Special mini-challenge, which typically are particularly weird or puzzling, usually seeming extremely difficult or even impossible to solve, see for example:

Short Sweet Math Challenge 18 April 1st Spring Special
Short Sweet Math Challenge 15 April 1st Spring Special
Short Sweet Math Challenge 20 April 1st Spring Special

As such, the original teaser's second requirement was simpler yet much more demanding than the one I specified for this "decaffeinated" version, which simply forbids using some operators (+, -, *, /, etc.,) and is way, way easier to solve, almost trivial when judging by the usual difficulty of my challenges. Not so with the original April 1st version, whose difficulty I greatly reduced in order to post it as an easy, affordable 2024's First Teaser, which I hoped would attract some considerable interest and likely a decent participation.

Well, no and no, actually it's got one of the lowest interest and participation rates in any of my challenges, next to none on both counts but as I said above, never mind, I'm posting here my two solutions: the elegant one for the (a) case below, and the shorter one for the (b) case below. Both solve the two variants of the teaser, the current easier one and the April 1st one, the latter replacing the second requirement (no +, -, *, /, etc.) by this one:

2. Two choices; (a) You must use just one and only one math operation in all, or (b) just one and only one math operation and just one and only one variable.

which is obviously much more difficult to meet and might seem impossible to people who know how demanding evaluating permanents is. Even the naive definition requires 17 math operations (12 multiplications and 5 additions), and the best working solution by PeterP uses 6 executions of DET and 1 of DOT, plus 4 matrix variables, while the one by J-F uses 4 executions of DOT plus 5 variables. Thus, reducing that to just 1 math operation and 1 variable seems complicated, to say the least.

The sleuthing

If we're constrained to use just one math operation in all, it can't be a scalar operation but a matrix operation, and a cursory examination of the ones available quickly reveals that the only possible choice is the DET (determinant) operation and no other. The question is: can the Permanent evaluation be accomplished in terms of the Determinant ?

Well, for the 2x2 case it actually can, like this:

     Per( | a  b |   =  a*d-b*c = Det( | a -b |
          | c  d | )                   | c  d | )

so the question now becomes: for matrices M of dimension 3x3 and bigger, can we reassign the signs of their elements in such a way that the determinant of M' equals the permanent of M ?

Regrettably, it can be proved that this is not possible, no sign reassignment will make it work for arbitrary matrices 3x3 and bigger. But this is not the end, we can still wonder whether substituting each element of M by a linear combination of the elements could result in a matrix M' having det(M') equal Per(M). Alas, again this is provably impossible for arbitrary matrices M of dimensions 3x3 and bigger.

Is this the end ? No, we've been considering a matrix M' of the same dimension (say nxn) than the original matrix M, but if we consider a matrix M' of dimension m with m>n, then the elements of M can be assigned to M' in such a way that Det(M') = Per(M) and indeed there exist matrices and assignments with minimal dimensions at most m = 2^n-1, for instance:



Actually, that m > n and that m should grow exponentially with n (e.g. m = 2^n-1) is all but expected, since if m were polynomial in n then the cost of computing the permnaent would also be polynomial, which though unproved it's still extremely unlikely, as the best known deterministic algorithms require exponental running time and non-exponential ones would result in P=NP, which is believed (but not proven) to be impossible.

The implementation

Now that we have the 7x7 matrix above whose determinant is the permanent of any given 3x3 matrix, we can use the DET keyword as the only math operation, and the implementation is straightforward, just requiring an optimized way to assign the original 3x3 elements to the 7x7 auxiliar matrix.

My "elegant" solution, which solves both the current teaser (no +, -, *, /, etc.) and case (a) of the April's teaser is this 4-line, 158-byte piece of code:

1  DESTROY ALL @ OPTION BASE 1 @ DIM M(7,7)
2  DATA 0,A,D,G,0,0,0,0,1,0,0,I,F,0,0,0,1,0,0,C,I,0,0,0,1
3  DATA C,0,F,E,0,0,0,1,0,0,H,0,0,0,0,1,0,B,0,0,0,0,0,1
4  INPUT A,B,C,D,E,F,G,H,I @ READ M @ DISP DET(M)

Notice that other than the DATA statements, we only do four single-statement things: DIMension the 7x7 matrix, INPUT the 3x3 elements from the user, assign all nine elements at once to their proper locations in the 7x7 matrix with a single READ, and compute and output the sought-for permanent's value with a single DET.

It uses 9 scalar variables, while my "shorter" solution solves both the current teaser and case (b) above as it uses just one variable and is 3 lines, 131 bytes long (in my OP I said 135 bytes, but then realized that the customary DESTROY ALL isn't needed and removing it saves 4 bytes from the 135):

1  OPTION BASE 1 @ DIM M(7,7) @ MAT M=IDN @ M(1,1)=0
2  INPUT M(1,2),M(7,1),M(3,6),M(1,3),M(5,1),M(2,6),M(1,4),M(6,1),M(2,5)
3  M(4,5)=M(3,6) @ M(3,7)=M(2,5) @ M(4,7)=M(2,6) @ DISP DET(M)

In this version, INPUT not only gets the 9 elements from the user but also automatically places them at their proper locations in the 7x7 matrix, then a few assignments place the remaining elements where they belong, while a previous MAT..IDN statement (this is not a math operation, just an assignment) took care of the 1's in the main diagonal and the 0's elsewhere.

Let's run any of them:

   >RUN
       ? 1,7,2,-3,4,-1,2,3,1 [END LINE] → -36

Regards.
V.