Skip to main content
Puzzling

Return to Answer

added 136 characters in body
Source Link
athin
athin
  • 34.4k
  • 4
  • 73
  • 226

Update: Please read below (under the double underlines) explanation first before coming back here.

And here are some illustrations in action:

enter image description here

Update: Please read below explanation first before coming back here.

Update: Please read below (under the double underlines) explanation first before coming back here.

And here are some illustrations in action:

enter image description here

Improve the lowerbound
Source Link
athin
athin
  • 34.4k
  • 4
  • 73
  • 226

Update: Please read below explanation first before coming back here.

I just realized from user65284's answer that we can flip the pieces. Thus, the lowerbound can be increased to:

$21$ sets, named all configuration thickness of each pieces:

- (Red $4,4$) (Yellow $2,2$) (Green $1,1$)
- (Red $4,4$) (Yellow $2,1$) (Green $2,1$)
- (Red $4,4$) (Yellow $1,1$) (Green $2,2$)

- (Red $4,2$) (Yellow $4,2$) (Green $1,1$)
- (Red $4,2$) (Yellow $4,1$) (Green $2,1$)
- (Red $4,2$) (Yellow $2,1$) (Green $4,1$)
- (Red $4,2$) (Yellow $1,1$) (Green $4,2$)

- (Red $4,1$) (Yellow $4,2$) (Green $2,1$)
- (Red $4,1$) (Yellow $4,1$) (Green $2,2$)
- (Red $4,1$) (Yellow $2,2$) (Green $4,1$)
- (Red $4,1$) (Yellow $2,1$) (Green $4,2$)

- (Red $2,2$) (Yellow $4,4$) (Green $1,1$)
- (Red $2,2$) (Yellow $4,1$) (Green $4,1$)
- (Red $2,2$) (Yellow $1,1$) (Green $4,4$)

- (Red $2,1$) (Yellow $4,4$) (Green $2,1$)
- (Red $2,1$) (Yellow $4,2$) (Green $4,1$)
- (Red $2,1$) (Yellow $4,1$) (Green $4,2$)
- (Red $2,1$) (Yellow $2,1$) (Green $4,4$)

- (Red $1,1$) (Yellow $4,4$) (Green $2,2$)
- (Red $1,1$) (Yellow $4,2$) (Green $4,2$)
- (Red $1,1$) (Yellow $2,2$) (Green $4,4$)

Here I will give a lowerbound for (original) contiguous case, which is there are at least:

Here I will give a lowerbound for (original) contiguous case, which is there are at least:

Update: Please read below explanation first before coming back here.

I just realized from user65284's answer that we can flip the pieces. Thus, the lowerbound can be increased to:

$21$ sets, named all configuration thickness of each pieces:

- (Red $4,4$) (Yellow $2,2$) (Green $1,1$)
- (Red $4,4$) (Yellow $2,1$) (Green $2,1$)
- (Red $4,4$) (Yellow $1,1$) (Green $2,2$)

- (Red $4,2$) (Yellow $4,2$) (Green $1,1$)
- (Red $4,2$) (Yellow $4,1$) (Green $2,1$)
- (Red $4,2$) (Yellow $2,1$) (Green $4,1$)
- (Red $4,2$) (Yellow $1,1$) (Green $4,2$)

- (Red $4,1$) (Yellow $4,2$) (Green $2,1$)
- (Red $4,1$) (Yellow $4,1$) (Green $2,2$)
- (Red $4,1$) (Yellow $2,2$) (Green $4,1$)
- (Red $4,1$) (Yellow $2,1$) (Green $4,2$)

- (Red $2,2$) (Yellow $4,4$) (Green $1,1$)
- (Red $2,2$) (Yellow $4,1$) (Green $4,1$)
- (Red $2,2$) (Yellow $1,1$) (Green $4,4$)

- (Red $2,1$) (Yellow $4,4$) (Green $2,1$)
- (Red $2,1$) (Yellow $4,2$) (Green $4,1$)
- (Red $2,1$) (Yellow $4,1$) (Green $4,2$)
- (Red $2,1$) (Yellow $2,1$) (Green $4,4$)

- (Red $1,1$) (Yellow $4,4$) (Green $2,2$)
- (Red $1,1$) (Yellow $4,2$) (Green $4,2$)
- (Red $1,1$) (Yellow $2,2$) (Green $4,4$)

Here I will give a lowerbound for (original) contiguous case, which is there are at least:

Source Link
athin
athin
  • 34.4k
  • 4
  • 73
  • 226

Here I will give a lowerbound for (original) contiguous case, which is there are at least:

$6$ sets.

Visually, here are the sets:

enter image description here

The three pieces are colored red, yellow, and green; and:

The red one must be the outermost part (having a length of $8$), yellow must be in the middle (with the same implication), and the green must be in the innermost. They are all having a thickness of $1$, $2$, and $4$; thus leading there are $3! = 6$ sets.

To show that they are valid sets:

We can do binary! And we can solve independently between the row and column!

Practically speaking:

W.L.O.G. we solve the row first. Let's say that we will not cover the hole in $x$-th row. That means we want to cover $x-1$ cells above it. This $x-1$ ranges from $0$ to $7$ which can be written as a subset sum of $\{1,2,4\}$ (a.k.a. binary). We can then rotate each pieces such that if its thickness is required then one of its side must be put above the hole. We can solve the column with the same technique. As an example, putting the piece in "L" shape will cover the left side of the hole but not above it.

Just to illustrate, here are some examples to not cover cell at row $4$ column $2$:

enter image description here