/sci/ - Science & Math

Prove that it is unsolvable, then we'll talk.
But looking at it may be 2n-1 , just a guess.

>>12664008
You already solved it retard

>>12664027
I think he means in general, like for a 17x17 square grid for example

>>12664008
7

Fill in a big H

>>12664008
If 1x1 is allowed, nxn is allowed

GUYS THE ANSWER SHOULD BE A FORMULA LIKE 2N-1 (WHICH IS OBVIOUSLY WRONG)

>>12664032
i want a general formula that applies to all square grids 3x3 7x7 9x9...

>>12664008
Those aren't even squares. Fuck you.

the person who says 2n-1 is a ball

>>12664008
How the fuck is the second one forming a rectangle? The middle square has no x, so there's no rectangle. What exactly are the rules here? You can just magically and arbitrarily fill in blank squares to make a rectangle?

>>12664025
4x4 grid. 8 > 7.

>>12664008
Most you can do is one entire row and one entire column. Anything else would constitute the last corner of a rectangle.

So like the other anons said: n + n -1 = 2n-1

>>12664088
Yeah, you are right. Not sure how to generalize such a informal question though, how would we express it in a more mathematical way?

>>12664058
4 corners form a rectangle sorry for not specifying

>>12664090
nope when grids get larger that one entire row one entire thing fucks up

>>12664090
That isn't even the max on a 3x3 what.
If you worded this in a way that wasn't retarded it would be easier than fuck to solve.
I suspect the theoretical maximum is 3(n-1)

X X -
X - X
- X X

>>12664140
Your answer is wrong entitled retard it doesnt work on 6x6

>>12664088
x x x -
x - - x
- x - x
- - x x
9 > 8
low iq mental midget, back to pol with you

>>12664098
>>12664140
I also found six on a 3x3 chart. But your formula is also incorrect. I fit 10 into a 4x4 chart.

The answer might be a triangle sum, n(n+1)/2

>>12664150
Nevermind, fucked up the 4x4. The max might be 9.

>>12664146
show the solve with more.

>>12664140
6x6 grid. 17 > 15

>>12664150
>>12664150
n(n+1)/2
is wrong in 6x6 you can fill 16

>>12664008
You made a new thread for this? Christ, I'm over in /mg/ talking to nobody like an idiot. Check my post over there.
>>12664181

>>12664032
Doesn't work. The four corners make it bad.

>>12664185
Bruh...
That isnt even 6x6

>>12664185
that is a 6 by 7...

>>12664192
hooly shit someone actually worded this problem right.

>>12664192
Can that shit tell me how many cells in 7x7

Any two squares with edge contact become a rectangle. Both examples in the OP image contain rectangles.

Checkerboard is the only answer.

>>12664260
Checkerboard is literally the most wrong answer

>>12664230
It can help find a lower bound, but I have no idea how to prove if it's best possible. [math]K_7[/math] has 21 edges. Divide by 7. We want three edges per row. Fortunately, that's totally possible, since a 3-clique has three edges. So put three filled cells in each row.

Here's my attempt. If this doesn't actually work, tell me.

>>12664260
>redefine the problem just to shit on OP

>>12664192

no that doesnt work on 9x9

>>12664278
yup that works

>>12664278
what do you mean by edges btw?

You can put 52 crosses on a 13x13 square.
You can just grab the incidence matrices of the finite projective planes to get solutions.

>>12664278
Attempt #2: 8x8. [math]K_8[/math] has 28 edges. Divide by 8; we want... 3.5 edges per row. That's impossible. But we can have 7 rows of 3 and 1 rows of 4 for a total of (3*7)+6=27 edges.
... Wait.
Shit. There's nowhere to put one last cell in the last row. Either my algorithm didn't work, or we need to distribute cells to rows differently.
I'm open to suggestions on this one.
>>12664326
Edges in a graph.
https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)
In this case, an edge is just a pair of columns containing filled cells in a row. When you convert a row in the grid to a clique in [math]K_n[/math], a pair of filled cells becomes an edge in the clique. If two of those cliques share an edge, it means that the corresponding rows have filled cells in the same columns, and that's bad.

>>12664326
>>12664372
This clusterfuck is my attempt to draw what it looks like in my 7x7 example >>12664278. Each colored triangle is a 3-clique corresponding to a row in the grid. No two rows share filled cells in two columns (I hope,) and no two cliques share an edge. In this case, something really nice happens - every possible edge in [math]K_7[/math] is accounted for.

>>12664371
Gorgeous. Is there any particular reason why this works?

What if you computed from the opposite direction? Computed every single possible rectangle for a grid and removed whatever square was integral to the most rectangles. Then you repeated the process. Every step you would remove the largest possible number of rectangles until you got to 0.

>>12664434
https://doi.org/10.1016/0012-365X(85)90029-9

>>12664008
a square is a kind of rectangle