practice problems pending

Q1) Let A be a set of m positive integers, where m >= 1. Show that there is a non-empty subset (B) of (A) such that sum of all elements in B is divisible by (m).
S1)
Let's create prefix sums like this:
S1 = a1
S2 = a1 + a2
...
Sm = a1 + a2 .. am

If any one of S1,S2...Sm has a 0 remainder we are done.
If not, then at least 2 of them have same remainder.
Then:
Sk - Sj = 0 mod m
If k > j
Then Sk - Sj = ak + a_{k-1} ... a_{j-1}
So these are the required elements.

Q2)

 Let (A) be a subset of ({1,2,...,2n}) such that (|A|=n+1). Show that there exist (a, b in A) such that gcd(a,b)=1.

Part 2: Can we also say the same thing when |A| = n?

S2)
There are at least 2 consecutive numbers in A.

Proof by PHP:
{1,2}
{3,4}
...
{2n-1,2n}

Each number belongs to one bucket out of these 'n' buckets.
If there are n+1 numbers, at least 2 of them will fall into same bucket.

Proof by contradiction(not very solid):
Let's say A has only non-consecutive numbers.
Then it can have only n numbers at max.
Since it has n+1 it's not possible.

And 2 consecutive numbers have gcd as 1 by Euclid algo.
gcd(k,k+1) = gcd(k,1) = 1

Part 2: No

Q3 Show that given any set of 5 numbers, there are 3 numbers in the set whose sum is divisible by 3.
S3)
3 buckets(remainder by 3)
Using PHP:
At least 1 bucket will have >= 2 elements.

Case 1:
If one bucket has >= 3 elements, pick 3 from the same bucket. Done.

Case 2:
No bucket has 3 but 2 of them have 2.
Then one of them has only 1.
Now pick one from each bucket. Done.