May28

Combinatorial Puzzle

Posted on by
Standard

This is a continuation of previous post:

How many distinct numbers can be formed by using four 2s and the four arithmetic operations +,-,\times, \div.

For example:
1 = \frac{2+2}{2+2}=\frac{2}{2}\times\frac{2}{2}
2 = 2+\frac{2-2}{2}=\frac{2}{2}+\frac{2}{2}
3 = 2+2 - \frac{2}{2}
4 = 2+2+2-2 = (2\times 2) + (2-2)
(note that some binary operations do not make sense without parenthesis)

I have no idea about how to approach this problem (since I am not very comfortable with combinatorics). So any help will be appreciated.

Edit[29 May 2017]: This problem has been solved in the comments below. 

15 responses

  1. My intuition would be that the maximum positive integer you could form is 16, and then it would be a matter of trying to form the numbers 1 to 16…might be wrong though 😀

    Like

    • Yes, 16 appears to be the upper limit. What I wish to prove is that you can’t form 7 using this (I guess). But to be able to prove this I want an algorithm which I enables me to list all the possible numbers that can be formed by this.

      Like

      • Yeah I also got stuck on 7. As far as I can see, though, there are only five possible arrangements of parentheses, so I am now trying to write a program that will put in all 64 sign combinations into each of the five arrangements (so 320 combinations to check).

        Like

          • I wrote the program and the only positive integers it returned were 1, 2, 3, 4, 5, 6, 8, 10, 12 and 16 , so there are 10 such positive integers.
            The five arrangements of parentheses (orders of operations) I used were:
            ((2 * 2) * 2) * 2
            (2 * (2 * 2)) * 2
            (2 * 2) * (2 * 2)
            2 * ((2 * 2) * 2)
            2 * (2 * (2 * 2))
            where any of the three operations are used in place of each *. I generated a list of 64 strings like “msd” (multiply, subtract, divide), using a three-digit base four integer to count them, and then read off each string to substitute the right binary operations into the brackets.
            Obviously this method leads to lots of duplicates – when all the * operators are multiplication, all five bracket arrangements give 16. So I just got rid of duplicates and chose the positive integers.
            I did spot several mistakes in the code while I was writing it so I might not be correct. However you can check that you can indeed form the above integers.
            I assumed you were interested in positive integers but since the question asked simply for distinct numbers, we can also add the following numbers: 0, 5/2, 3/2, -4, -6, -1, -2, 1/2, 1/3, -3/2, 1/4, 2/3, -3, -1/2. I haven’t checked these though!

            Like

            • It’s a really nice observation that for a given set of 4 numbers we can use only 3 binary operations. But you can use negative sign to convert 2 to -2 (using few more parentheses). Hence, I guess we can always generate the corresponding negative integers for the positive integers. Maybe you can share the code using something like https://repl.it
              Moreover, as per these results, we can only generate the reciprocals of 2, 3/2, 4 and 3. This is very interesting.

              Like

            • Oh I didn’t count sticking a minus sign in front as an operation. But you might be able to do more than just flip the sign of the resultant number, depending on the order of operations – I don’t know.
              The code is written in Visual Basic (kind of a beginner language) – which https://repl.it doesn’t seem to support … 😦

              Like

            • I can’t get it to work…keeps giving me errors…
              If you have visual studio though here’s the code and you can paste it in
              It’s very horrible code though, it might be hard to understand

              Dim output As New List(Of Double)()
              Dim x As String = “”
              Dim opcombos(63) As String
              Dim oplist As New List(Of String)({“a”, “s”, “m”, “d”})
              Private Sub Form1_Load(sender As System.Object, e As System.EventArgs) Handles MyBase.Load
              For i = 0 To 63
              opcombos(i) = “”
              Next
              For m = 0 To 3
              For n = 0 To 3
              For p = 0 To 3
              opcombos(p + 4 * n + 16 * m) += oplist(m)
              opcombos(p + 4 * n + 16 * m) += oplist(n)
              opcombos(p + 4 * n + 16 * m) += oplist(p)
              Next
              Next
              Next

              For Each z In opcombos
              x = z(0)
              Dim a1 As Double = f(2, 2)
              x = z(1)
              Dim a2 As Double = f(a1, 2)
              x = z(2)
              Dim a3 As Double = f(a2, 2)
              output.Add(a3)

              x = z(1)
              Dim b1 As Double = f(2, 2)
              x = z(0)
              Dim b2 As Double = f(2, b1)
              x = z(2)
              Dim b3 As Double = f(b2, 2)
              output.Add(b3)

              x = z(0)
              Dim c1 As Double = f(2, 2)
              x = z(2)
              Dim c2 As Double = f(2, 2)
              x = z(1)
              Dim c3 = f(c1, c2)
              output.Add(c3)

              x = z(1)
              Dim d1 As Double = f(2, 2)
              x = z(2)
              Dim d2 As Double = f(d1, 2)
              x = z(0)
              Dim d3 As Double = f(2, d2)
              output.Add(d3)

              x = z(2)
              Dim e1 As Double = f(2, 2)
              x = z(1)
              Dim e2 As Double = f(2, e1)
              x = z(0)
              Dim e3 As Double = f(2, e2)
              output.Add(e3)

              Next

              Dim solution As String = “”
              For Each n In output.Distinct.ToList
              If n > 0 And n Mod 1 = 0 Then
              solution += ” ” + n.ToString
              End If
              Next
              MsgBox(solution)
              End Sub

              Private Function f(p, q)
              Select Case x
              Case “a”
              Return (p + q)
              Case “s”
              Return (p – q)
              Case “m”
              Return (p * q)
              Case “d”
              If q 0 Then
              Return (p / q)
              Else
              Return (p * q)
              End If
              End Select
              End Function

              Liked by 1 person

            • You should be able to download it for free if you want but you can probably get the gist of what it’s saying anyway since it is beginner-friendly. Some of it is pretty lame coding – for example, the function f multiplies its inputs rather than divides them if the divisor is zero.
              (Otherwise it would crash!) Ask me if anything doesn’t make sense – it could be a genuine mistake

              Like

            • Ah I just also noticed on the seventh line from last, the copy and paste seems to have got rid of some punctuation…it should read q0 (which means q is not equal to zero)

              Like