Fun questions :)

[zzdfa]

Idea makes sense, I haven't had time to go through it thoroughly, but I noticed...

"This means that inside rectangle ABCD we must have at most 5+11=16 dots"

shouldn't it be 5+12=17?

[kamil9876]

LOL yes, just realised, made some arithmetic mistakes so not sufficient(55 instead of 53 works), but close heh.

[Over9000]

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

Looks like you got a turn a symbol there ()

[kamil9876]

[Over9000]

lololololol

[kamil9876]

Taken from TT's thread since with the rapid page growth of the thread these would probably be left unnoticed:

I'll post the following problems i found quite fun in the past month or so and are sort of related to combinatorics. I invite everyone to solve. I tried to put it into an ascending order of difficulty (first few are give aways, last one probably not so).

1.)Fifty numbers are chosen from the set {1, . . . , 99}, no two of which sum to 99 or 100. Prove that the
chosen numbers must be 50, 51, 52, . . . , 99.

2*.) is partitioned into k (disjoint) arithmetic progressions, all of infinite length, with common differences . Prove that
zzdfa's solution

3.) You want to color the integers from 1 to 100 so that no number is divisible by a different number of
the same color. What is the smallest possible number of colors you must have?

4.) Prove that any positive integer can be represented as a sum of Fibonacci numbers, no two of which are consecutive.
True Tears' solution

5.) Given 81 positive integers all of whose prime factors are in the set {2, 3, 5}, prove that there are 4
numbers whose product is the fourth power of an integer.

6.) A 2002 x 2004 chessboard is given with a 0 or 1 written in each square so that each row and column contain an odd number of squares containing a 1. Prove that there is an even odd number of white unit squares containing 1.
(source had "even", but I believe it should be odd)


7.)Let n be a positive integer, and let X be a set of n+2 integers, each of absolute value at most n. Show
that there exist three distinct numbers a, b, c in X such that a + b = c.


8.) The set of positive integers is divided into finitely many (disjoint) subsets. Prove that one of them, say
, has the following property: There exist a positive integer m such that for any k one can find numbers such that ;


*An extension to probelm 2 is that the two greatest common differences must be equal, though I don't think this result is elementary enough for this thread.

[kamil9876]

bump. and new problem:

A man has 42 grapes and eats at least 1 each day. On the 28th day he eats the last lot. Prove that there is some set of consecutive days where exactly 15 grapes were consumed.

[Ahmad]

Let be the total number of grapes eaten from day 1 up until the ith day (inclusive). Then is strictly increasing and so is a collection of 28 distinct numbers from 1 to 42. Consider the pairings {1,16}, {2,17}, ..., {k, k+15}, ..., {27, 42}, since there are 27 sets and the take on 28 distinct numbers, there must exist two numbers j and k (j < k) such that and are in the same set, and so differ by 15. But then from day j+1 to day k (inclusive) the man has eaten exactly 15 grapes. Hopefully k << 28 because we wouldn't want him to eat rotten grapes, certainly not!

[jimmy999]

I decided to have a go at some of these. The first one is an alternative solution to question 16.

As we know that
Then
So as

Hence we get
We can separate this into
Which gives us
Now the
Hence

[brightsky]

1. Using the pigeon-hole principle to solve the problem:

Pigeons: 50 selected numbers

Holes:

Case 1 - 49 holes are defined by {1, 98}, {2, 97}, {3, 96}, {4, 95}, {5, 94}, ..., {49, 50}. ==> 99 is isolated

Case 2 - 49 holes are defined by {1, 99}, {2, 98}, {3, 97}, {4, 96}, {5, 95}, ..., {49, 51}. ==> 50 is isolated

From Case 1, because 50 = 49*1 + 1, we see that one hole must have two pigeons. That is, if we use 50 of the numbers from 1 - 98, there would be at least one pair that would give a sum of 99. Hence, we can deduce that 99 must be in the 50 selected numbers.

From Case 2, because 50 = 49*1 + 1, we see that one hole must have two pigeons, again. That is, if we use 50 of the numbers from 1 - 49, 51 - 99, there would be at least one pair that would give a sum of 100. Hence, we can deduce that 50 must be in the 50 selected numbers.

With that in mind, consider the pattern:
50, 49, 51, 48, ...3, 97, 2, 98, 1, 99

It is clear that any two consecutive terms in the sequence cannot coexist in the set of 50 numbers. We know that 99 and 50 must be in the 50 selected numbers, and we are only restricted to selecting 50 numbers. Hence, the numbers must be 50, 51, 52...99.
Hence, the numbers in the set must be 50, 51, 52, 53, 54,...,99.

[kamil9876]

was looking good. However:

Because 98 can, 2 cannot

Is not a correct deduction. Because "can" and "must" are two different things. In order to prove 2 cannot definitely be in there, it would suffice to show 98 must, but this is very different to can.

[brightsky]

Ok, thanks. Shall edit it.

[kamil9876]

I didn't mean that you merely used the wrong words, but the concept. How do you justify "1 cannot, therefore 98 must". What if we didn't pick 98 nor 1, then we would avoid a sum to 99 as well.
Though looking back at your partitions in 'case 1' and 'case 2' I don't think this is such a big logical leap as I first thought. (and actually looks more similair to my solution).

[brightsky]

Ah ok, I get what you mean. Would this be a better proof...

[kamil9876]

wow that's a very good one (you're last paragraph alone is a solution!).