[Guest]

You are blindfolded and given an 3 by 4 jigsaw puzzle. You pick up a random piece to start with and then another. you check if they go together in any way and if they don't, drop one and repeat. If they do, you put them together and pick another piece and see if that fits with any of the pieces in your hand. if not, drop it and repeat.

what is the expected number of pieces you will pick up?

harder part:

you are given an M by N puzzle. In terms of M and N, what is the expected number of pieces you will pick up?

[curr3nt]

Is the tested piece dropped back into the pile to be picked again?

Worst case I count 49 picks if there are two piles, picked and not picked.

[Guest]

the tested piece is dropped back into the original pile.

the question asks for the expected value, not worst case.

[Guest]

There are only 12 pieces (3X4) that's all you can pick up. If you pickup the same piece a second time, that is still only one piece picked up.

[fabpig]

to only pick up 12. In a 4x3 jigsaw, only the 2 central pieces do not have straight edges. These can be selected by feel and must join together in one position. Now we have left the 4 corner pieces and 6 others with only 1 straight edge. Select 1 of the 6 with 1 straight edge and it must join one of the 2 central pieces at some position. Repeat for the remaining 5, and then do a similar operation on the corner pieces.

[k-man]

to only pick up 12. In a 4x3 jigsaw, only the 2 central pieces do not have straight edges. These can be selected by feel and must join together in one position. Now we have left the 4 corner pieces and 6 others with only 1 straight edge. Select 1 of the 6 with 1 straight edge and it must join one of the 2 central pieces at some position. Repeat for the remaining 5, and then do a similar operation on the corner pieces.

I wanted to post this solution, but the OP states clearly that you are picking up pieces at random, so feeling the edges is not allowed. It also only works for 3x4 puzzle, but fails for larger puzzles.

[fabpig]

I wanted to post this solution, but the OP states clearly that you are picking up pieces at random, so feeling the edges is not allowed. It also only works for 3x4 puzzle, but fails for larger puzzles.

Ah yes. Fair point, K-man. In my defence, can I say that I had my blindfold on when reading that.......? (I still like my - sorry our - solution)

[Guest]

Assuming that the pieces can only join adjacent pieces and not diagonal ones.

In a 3x4 grid each corner can only connect to 2 other pieces, the sides join 3 and the 2 central pieces can fit 4.

If you were to draw a corner you would have a 2/11 (18.18%) chance of getting a piece to fit.

If you were to draw a center you would have a 4/11 (36.36%) chance of getting a piece to fit. So if your lucky you really want that central piece.

I came up with a median number of 16 pick ups on average to complete the puzzle.

[curr3nt]

Counting the first random pick as one.

100,000 runs : Average = 18.61; Max = 78; Min = 12;

100,000 runs : Average = 18.59; Max = 74; Min = 12;

100,000 runs : Average = 18.57; Max = 85; Min = 12;

100,000 runs : Average = 18.59; Max = 75; Min = 12;

100,000 runs : Average = 18.59; Max = 72; Min = 12;

[Guest]

Counting the first random pick as one.

100,000 runs : Average = 18.61; Max = 78; Min = 12;

100,000 runs : Average = 18.59; Max = 74; Min = 12;

100,000 runs : Average = 18.57; Max = 85; Min = 12;

100,000 runs : Average = 18.59; Max = 75; Min = 12;

100,000 runs : Average = 18.59; Max = 72; Min = 12;

that seems to be about right, but I'm not sure since I found a bug in my own code. What do you get for 2 by 3 and 3 by 3?

[curr3nt]

Haven't tried those. I hard-coded the adjacent pieces...

[Guest]

a simple answer you will pick up all 12 pieces...

a worst case is you pick up one piece and then have 11 to go through, then you have 10 pieces, then 9, 8 and so forth

so then you would need to pick up

1 + 11 = 12

12 + 10 = 22

22 + 9 = 31

31 + 8 = 39

39 + 7 = 46

46 + 6 = 52

52 + 5 = 57

57 + 4 = 61

61 + 3 = 64

64 + 2 = 66

66 + 1 = 67 pieces touched

for the M x N puzzle follow the same pattern

but its just a gues

[Guest]

I wrote a program that gives the exact expected value in fraction form and although it gets horribly slow very quickly as numbers increase, I managed to get the following results:

for any 1 by n puzzle, the expected value is (n²+2)/3

for any 2 by n puzzle, the expected value is (n+1)²/2

for 3 by 3:29879/2187 or approximately 13.66209419295839

for 3 by 4:812521/39366 or approximately 20.640171721790377

that last one took my computer six minutes to complete while the one before it took only 11 seconds...

naturally, I'm not going to try 3 by 5...

[k-man]

Your result is a bit different than curr3nt's, so I'd say at least one of you still has some bug(s) to catch

[curr3nt]

Sub test()

Dim neighbors(12) As String

Dim picked(12) As String

Dim pieces(12) As String

Dim pick As Integer

Dim i As Integer, j As Integer

Dim count As Long

Dim piece_count As Integer

Dim fit As Boolean

Dim order As String

Dim row As Long

Application.Calculation = xlCalculationManual

Randomize

neighbors(1) = "|2|5|"

neighbors(2) = "|1|3|6|"

neighbors(3) = "|2|4|7|"

neighbors(4) = "|3|8|"

neighbors(5) = "|1|6|9|"

neighbors(6) = "|2|5|7|10|"

neighbors(7) = "|3|6|8|11|"

neighbors(8) = "|4|7|12|"

neighbors(9) = "|5|10|"

neighbors(10) = "|6|9|11|"

neighbors(11) = "|7|10|12|"

neighbors(12) = "|8|11|"

For row = 1 To 100000

For i = 1 To 12

picked(i) = "N"

pieces(i) = i

Next

pick = Int(12 * Rnd()) + 1

order = pick & "|"

For j = pick To 11

pieces(j) = pieces(j + 1)

Next

picked(pick) = "Y"

piece_count = 11

count = 1

While piece_count > 0

pick = Int(piece_count * Rnd()) + 1

count = count + 1

fit = False

For i = 1 To 12

If picked(i) = "Y" Then

If InStr(1, neighbors(i), pieces(pick)) > 0 Then

fit = True

i = 12

End If

End If

Next

If fit Then

order = order & pieces(pick) & "|"

picked(pieces(pick)) = "Y"

For j = pick To piece_count - 1

pieces(j) = pieces(j + 1)

Next

piece_count = piece_count - 1

End If

Wend

Sheets("bin").Range("A" & row).Value = Left(order, Len(order) - 1)

Sheets("bin").Range("B" & row).Value = count

Next

Application.Calculation = xlCalculationAutomatic

End Sub

Your result is a bit different than curr3nt's, so I'd say at least one of you still has some bug(s) to catch

[Guest]

Sub test()

Dim neighbors(12) As String

Dim picked(12) As String

Dim pieces(12) As String

Dim pick As Integer

Dim i As Integer, j As Integer

Dim count As Long

Dim piece_count As Integer

Dim fit As Boolean

Dim order As String

Dim row As Long

Application.Calculation = xlCalculationManual

Randomize

neighbors(1) = "|2|5|"

neighbors(2) = "|1|3|6|"

neighbors(3) = "|2|4|7|"

neighbors(4) = "|3|8|"

neighbors(5) = "|1|6|9|"

neighbors(6) = "|2|5|7|10|"

neighbors(7) = "|3|6|8|11|"

neighbors(8) = "|4|7|12|"

neighbors(9) = "|5|10|"

neighbors(10) = "|6|9|11|"

neighbors(11) = "|7|10|12|"

neighbors(12) = "|8|11|"

For row = 1 To 100000

For i = 1 To 12

picked(i) = "N"

pieces(i) = i

Next

pick = Int(12 * Rnd()) + 1

order = pick & "|"

For j = pick To 11

pieces(j) = pieces(j + 1)

Next

picked(pick) = "Y"

piece_count = 11

count = 1

While piece_count > 0

pick = Int(piece_count * Rnd()) + 1

count = count + 1

fit = False

For i = 1 To 12

If picked(i) = "Y" Then

If InStr(1, neighbors(i), pieces(pick)) > 0 Then

fit = True

i = 12

End If

End If

Next

If fit Then

order = order & pieces(pick) & "|"

picked(pieces(pick)) = "Y"

For j = pick To piece_count - 1

pieces(j) = pieces(j + 1)

Next

piece_count = piece_count - 1

End If

Wend

Sheets("bin").Range("A" & row).Value = Left(order, Len(order) - 1)

Sheets("bin").Range("B" & row).Value = count

Next

Application.Calculation = xlCalculationAutomatic

End Sub

Unfortunately, I don't even know what language that is, let alone how to interpret it... I'm only a beginner programmer and I only know python...