Random Number Quiz

[PuzzlerUK]

Hi, I am looking to see if anyone can help with regards to an excel math formula to help me solve and generate an unusual math puzzle I came across recently.

I loved the puzzle and am interested in trying to develop a formula for it in Excel but to no avail.

The puzzle presented 25 random numbers from 1 to 100. From these 25 numbers, 5 numbers added up to a value provided. You had to examine all of the 25 numbers and work out which ones added up to the value. An interesting design.

I can generate 5 random numbers and work out how 5 of these can add up to a given value, however have no idea how to generate 25 random numbers of which only 5 of the random numbers add up to a given value.

Can anyone help?

 

[shg]

I don't think that's going to happen with a formula. You'd have to ratchet through all the combinations and check their sum.

There is a way to find the number of combination that total to a given sum using generating functions. There are, for example, 460,300 5-combinations of {1,2,3,...,100} that total 252 (and the same number for 253).

Solver might eventually get there, but it has no special propensity for solving that type of problem.

You could create a table with 53,130 rows that contains all the combinations of 25 choose 5 and check the sum on each row with a formula. Once you do the non-recurring part, the answers for a given problem with be near instantaneous.

 

[PuzzlerUK]

Thanks, is it possible to generate 5 random numbers from 25 numbers (randomly chosen from 1 to 100) whose value adds up to a provided number for example 36.
There may be more than one solution using the other 20 numbers, but excel would provide one answer using a formula?

 

[shg]

Simple in code, but no way I know of using formulas -- but there are better formula guys here than YT.

 

[lrobbo314]

Of the 25 random numbers, are duplicates allowed?

 

[PuzzlerUK]

No

 

[diddi]

Definitely a VBA job. Generate the 25 numbers, then check the combination totals, counting each total in an array. then check the array for single solutions. you might end up with many solutions from the same set of numbers so you yet many puzzles in 1 go

 

[diddi]

 

[Eric W]

If you're trying to create a puzzle where you generate 25 numbers, and there is a unique solution where 5 of them add up to a particular sum, I can think of a couple ways to do it. Neither is great, but might lead to something more workable.

The first is pretty trivial. Include the numbers 1-5, set the target to 15, and it's pretty obvious that any other number would result in a total greater than 15.

The second option is to select 20 numbers that are equivalent to 1 mod 6, then include 5 numbers that are equivalent to 0 mod 6. Then set your target to the sum of the 5 numbers that are equivalent to 0 mod 6. A little modulus arithmetic tells us that including any of the 1 mod 6 numbers would result in a number that has a remainder of 1-5, so it can't sum to the target number. We know the original creators of the puzzle didn't do this, since there are not 20 numbers equivalent to 1 mod 6 less than 100.


Next topic, if you want a formula to find certain values that sum to a given value, it can be done, but your condition of having 25 numbers to choose from is just out of reach. Consider:

Dynamic functions.xlsm
	A	B	C	D	E
1	Nums		# of vals	Target	Count
2	67	0	20	331	5
3	72	0
4	85	0
5	1	0		1187
6	58	0		1187
7	42	0
8	61	0
9	6	0
10	60	0
11	100	1
12	19	0
13	97	0
14	91	1
15	29	0
16	93	1
17	51	0
18	49	0
19	14	0
20	3	1
21	44	1
22	71
23	90
24	17
25	59
26	81
Sheet4

Cell Formulas
Range	Formula
D5	D5	=MATCH(D2,MMULT(--MID(BASE(ROW(INDIRECT("1:"&2^C2-1)),2,C2),TRANSPOSE(ROW(INDIRECT("1:"&C2))),1),OFFSET(A2,0,0,C2,1))*(LEN(SUBSTITUTE(BASE(ROW(INDIRECT("1:"&2^C2-1)),2,C2),"0",""))=E2),0)
D6	D6	=MATCH(D2,MMULT(--MID(BASE(SEQUENCE(2^C2),2,C2),SEQUENCE(,C2),1),OFFSET(A2,0,0,C2,1))*(LEN(SUBSTITUTE(BASE(SEQUENCE(2^C2),2,C2),"0",""))=E2),0)
B2:B26	B2	=MID(BASE($D$6,2,$C$2),ROWS($B$2:$B2),1)
Press CTRL+SHIFT+ENTER to enter array formulas.

The D5 formula works in Excel 2013 and newer, the D6 formula works in Excel 365 with the new array formulas. The D5 formula fails after 20 values because (in part) it uses ROW to create an array of values, and Excel 2013+ has only 2^20 rows. The D6 formula uses SEQUENCE instead, but it too fails after 20 due to lack of resources. After all, internally it's doing matrix multiplication on an array with millions of rows and dozens of columns.

Either version figures out all 2^n possibilities, then excludes any that use more or less than 5 numbers. This is very inefficient. There is an algorithm that calculates only the combinations we want, but I don't know how to build that into a formula, it's definitely a VBA task.

Given all this, this formula might work to solve some of your puzzles. If the numbers are randomly selected, there will probably be many solutions. So try the formula, see if it works. If not, sort the input list differently and try again. If you try again and still don't get an answer, it may be that whoever created the puzzle did use some math tricks to ensure only one answer, and one or more of the needed numbers are in the bottom 5 values.


Over all, solving this kind of problem is pretty tough. See:

Subset sum problem - Wikipedia

en.wikipedia.org

Also see this thread, especially posts 8 and 7:

minimum no. of cells in a row that add up exactly to a target number

Need to highlight the minimum no. of cells in the range starting from Column C till CX for each row, such that these add up to exactly the target number. Also would like to have the list of these numbers in descending order and the cell numbers of these numbers. In case same number is available...

www.mrexcel.com

That has a couple of VBA routines designed to solve the general case of this problem.

So there you are, more than you ever wanted to know.

 

[diddi]

this was my solution...

Sub Puzzle()
    Dim Puz(100) As Long, PuzTots(500) As Long, PuzNums(25) As Long
    Dim Nums As Long, Tot As Long, Slns As Long, RNum As Long
   
    ' select 25 numbers, tag as 1 in the Puzzle array
    While Row < 25
        RNum = Int(Rnd() * 100) + 1
        If Puz(RNum) = 0 Then
            Puz(RNum) = 1
            Row = Row + 1
        End If
    Wend
   
    ' assign the 25 selected numbers to the PuzNumbers array
    For Row = 1 To 100
        If Puz(Row) = 1 Then
            Nums = Nums + 1
            Cells(Nums + 2, 1) = Row
            PuzNums(Nums) = Row
        End If
    Next Row
   
    ' cycle through the combinations and tally the totals in PuzTotals array
    For Row1 = 1 To 21
        For row2 = Row1 + 1 To 22
            For row3 = row2 + 1 To 23
                For row4 = row3 + 1 To 24
                    For row5 = row4 + 1 To 25
                        Tot = PuzNums(Row1) + PuzNums(row2) + PuzNums(row3) + PuzNums(row4) + PuzNums(row5)
                        PuzTots(Tot) = PuzTots(Tot) + 1
                    Next row5
                Next row4
            Next row3
        Next row2
    Next Row1
   
    ' pick the solutions from the PuzTot array where the count = 1
    For Row = 1 To 500
        If PuzTots(Row) = 1 Then
            Slns = Slns + 1
            Cells(Slns + 2, 3) = Row
        End If
    Next Row
End Sub

calculation was virtually instant despite the apparent length of the loops.