Fun questions :)

[kamil9876]

How nice of you to come at the right time and distract me from studies

attempt at Q4:

53=13*4+1

meaning that there must be one column with at least 5 dots.
By a similair technique: there is at least ANOTHER column with 4 dots.

Having put some dots in one column and some more in another. We have used up at most 13+1=14 dots.

53-14=39. 39=3*11+6.

Meaning that there must be another column with at least 4 dots.

Having done 3 columns now, we have used up at most... err... 13+2=15 dots.

53-15=38. 38=3*11+5.

so there must be ANOTHER column with at least 4 dots.

Can you see what I'm doing so far? I think we may get the result, or at least some decent upperbound from this.
Like so far we have done 4 columns. one has 5 dots, and three others have 4, have we reached a situation where it is neccesary to have a rectangle? I did this from drawing a bar graph for each column. 

[zzdfa]

nice i didn't notice that
"having put some dots in one column and some more in another. We have used up at most 13+1=14 dots."

 the best i could get before was 5 columns with 5,4,3,2,1 dots


theres a slight mistake though, don't think it changes anything for the first few columns:

"Having done 3 columns now, we have used up at most... err... 13+2=15 dots. "

Code: [Select]

a a
a
a
a
a a
a
a
a a
a
a
a
a
a    
there are 16 dots in 3 columns above.
   

[kamil9876]

Pigeonhole problems are so fun lately. I've been trying out some combinatorial number theory for the past week quite fun I'll show you some fun problems. It's mostly recreational but there is some serious work on it such as Van der Waerden's theorem, Erdos-Ginzburg-ziv, Szemeredi, Dirichlet and the still unsolved Erdos conjecture (where Terry Tao-Green theorem is a special case of). Most of the harder stuff I'm too noob for atm :/ but some olympiad problems are nice

[kamil9876]

nice i didn't notice that
"having put some dots in one column and some more in another. We have used up at most 13+1=14 dots."

 the best i could get before was 5 columns with 5,4,3,2,1 dots


theres a slight mistake though, don't think it changes anything for the first few columns:

"Having done 3 columns now, we have used up at most... err... 13+2=15 dots. "

Code: [Select]

a a
a
a
a
a a
a
a
a a
a
a
a
a
a    
there are 16 dots in 3 columns above.
   

ahh yeah true, lol I thought of the exact same thing! (hence the err) but then I did it in my head and thought it wasn't a concern. I knew some details of my attempt would be wrong but I was convinced the genereal idea would be right. 17 is the max though yeah? this would only decrease the remainder by 2, so it would be 3, so the latter part of the argument would still apply.

edit: I'm actually alright at this pigeonholing most of the time, like I sometimes have a good intuition that can guide me to an idea but I sometimes have problems with making my proof rigorous. :/ dunno how to fix that in general for this technique.

[zzdfa]

Yea, I came across that problem because I was looking for pigeonhole problems, specfically the ones like 3.3.21 & 3.3.20 & 3.3.6 in TAACOPS, where you have to get them in the same pigeonhole then 'subtract' them, because I had to look up the answers for all of them so I wanted practice with that technique.   I thought the 13x13 was going to be easy shit (53=4*13+1 lol obvious), so I was going to do it to boost my confidence. didn't work lol.

I'm actually alright at this pigeonholing most of the time, like I sometimes have a good intuition that can guide me to an idea but I sometimes have problems with making my proof rigorous. :/ dunno how to fix that in general for this technique.

really? don't you just write out what your pigeonholes are and what your pigeons are and then show that if m pigeons go into a hole then we have the desired property?

[kamil9876]

TAACOPS?

really? don't you just write out what your pigeonholes are and what your pigeons are and then show that if m pigeons go into a hole then we have the desired property?

Nope I don't because I make a lot of logical leaps . Like ussually I have this mentality "let's try to find the minimal case.... aha... we can't have anything less than minimal". So it's more ituitive and sometimes I miss out. I guess sometimes I can make it more rigorous by turning it into a "a proof by minimal counterexample", but who has time with that when you're not even sure if the solution will be fruitful anyway?

[zzdfa]

the art and craft of problem solving

and also

Code: [Select]

a a
a
a
a
a a
a a
a
a a
a
a
a a
a
a

4 columns, 18 dots, no rectangles. so 5,4,4,4 isn't enough.

btw there's about 80 different erdos conjectures

[kamil9876]

LOL oh I forgot about that one. There goes my career as a code breaker...

edit: oh well I guess the algorithm can be computed further so that eventually we get impossibility?

[zzdfa]

yes, i was thinking that, but then the errors from
"Having done 3 columns now, we have used up at most... err... 13+2=15 dots. " '
start to stack up and of course if you go too far you end up with 13 columns and less than 53 dots which is foolish ;p

[kamil9876]

I sort of bothered to calculate the algorithm further, creating some neater geometrical notation in the process haha, and so far i got: 5,4,4,4,4,4,4,3. Surely this must be close to impossibility. I'm off anyway, I think this should eventually if not already give impossiblity.

btw: i thoguht if this earlier but discarded it as stupid... what if we're talking about a geometrical rectangle, as in one where the lines are not neccesarily parralel to the lattice lines  :2funny: . But that's too complicated, whipping out the dot product etc. haha

[zzdfa]

haha yea, i forgot to mention, it does have to be parallel to the lattice lines

i had another idea, but im too tired to think it through and made a pretty picture instead:
\

i.e. stop thinking in terms of columns/rows
 at least it solves TAACOPS 3.3.5

strange how its 4*13+1=53 though, since we're looking for 4 points not 5.

hmm i did some experiments before and
5,4,4,4,4,4,4 does seem to be enough (well i only tried 1 configuration)

but even if this does yield the solution, there has to be a simpler way ;p

[kamil9876]

Mind you, I did make an algorithm to this that isn't really that tedious once you introduce some notation. In fact working out those next three 4's was purely numerical after extracting it from the geometry.

[zzdfa]

5,4,4,4,4,4,4,3 no rectangles

[kamil9876]

hah yes. I think I forgot to fix the first three colums up.

Okay, i promise this is my last shot for tonight: I was working to messily and quickly and forgot that i added some stuff into the first column: My best effort is really that the thirst 4 rows (with 5,4,4,4 as MINIMUM for each column, as calculated by my old method) have actually (7,5,5,5) as maximum(permute the order as you wish). Then I proved geometrically that in order to avoid having rectangles, the remaining columns must contain no more than 4 each( a consequence of the 5,4,4,4 minimum). But that still doesn't give enough information to readily give a contradiction since 22+4*9>53 :/. Oh well, worth a try but yeah, i can see that probably there should be a better way

[kamil9876]

Here's a new idea:

We know that there needs to be at least one sub-column(subset of points of a particular column) with 5 dots. Now say for example this subcolumn is {(1,1),(1,2),(1,3)(1,4)(1,5)} (the thing shaded in the picture below). That means that both    and    cannot be chosen at the same time Otherwise we get a rectangle. This means that inside rectangle ABCD we must have at most 5+11=16 dots. Therefore there are at least 53-16=37 dots left to put into rectangle AEFB. Hence we can solve the problem if we can solve the problem for a 13 x 8 lattice with 37 dots. Repeating the same procedure for this we can reduce the probelm to 8x8 and 25 dots ie: 37=4*8+5 so there must be at least one SUBROW with 5 columns.

I eventually reduced the problem to a 4 x 3 box with 8 dots, which is obviously impossible to avoid having a rectangle in this case (which can be worked out by this method!).

There is an intersting invariance to this problem, ie: my sub column didn't have to have consecutive y-values or couldve been starting from the top, the same conclusion applies since by swapping two dots your just really relabelling the y-values and not changing the 37 properties, although it's messier this way. Just like by swapping two rows or two columns you do not change the rectangleness(ie: if you had a rectangle, you will still have one).

edit: forgot to attach pic XD