TT's Maths Thread

[zzdfa]

yea all makes sense now, nice

[TrueTears]

yea all makes sense now, nice

lol, I just don't think it's rigorous enough, I mean I basically generalised a specific case, everything is just based off it, it just doesn't seem right to me >_<

[zzdfa]

:s
you proved that there is a bijection between

 the set of all MSS containing n+1 <-> the set of all MSS of n-1

and

the set of all MSS not containing n+1 <-> the set of all MSS of n




therefore

f(n+1)=f(n)+f(n-1)

its completely rigorous. dont worry ;p


edit: then again, rigorous is subjective. so if you dont feel its rigorous you find out why and then plug the gap until your 100% convinced.

[TrueTears]

Oh right I see, lol I didn't even think of bijection while doing this question.

[kamil9876]

with TT's permision, 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

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.

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.

[TrueTears]

Yeah in conjunction to kamil's set of questions, these are the final set of combinatorics questions:

1. Let denote the number of ways in which a set of elements can be partitioned into non-empty subsets. For example, , corresponding to:











Find a recurrence relation for .

2. For positive integers with , define to be the number of different partitions of a set with elements into non-empty subsets. For example, , because there are six 3-part partitions of the set :













Show that for all

a)

b)

c)

3. Find a combinatorial argument to explain the recurrence:

[zzdfa]

my proof of 2):

we have k disjoint arithmetic sequences. Let be the set of naturals in the i th sequence.

Define

it is easily shown that



and

for all n (because every n is in exactly one )    (1)

so we can make arbitrarily small.

thus we can also make arbitrarily small.

first inequality is the triangle inequality, 2nd one is due to the (1).

therefore


corollary: replace N by Z and the theorem still holds, this can be seen by considering a 2 sided sequence in Z as 2 one sided sequences in N and
applying the above. i think. 0 probably screws something up.


lolz number 4 was on my mth1112 exam ;p

[kamil9876]

yeah i chose because I wasn't sure what 'infinite arithmetic progression' means exactly, i meant to put but then wondered what would happen if we had this: {-1,-2,-3....} and {0,1,2,3....}. (althought if u count the former as negative it does work ). However I think a good definition would be that an arithmetic progression with a_i and common difference d_i is with positive d. Then the theorem is definitely true and zero doesn't matter since we're only performing addition (and if we have such a partition, we can always "translate it" (shift) and we still get another partition ie: change reference frame )

[kamil9876]

lolz number 4 was on my mth1112 exam ;p

what a cool subject!

also: my soln is same as yours only that I don't use limits but just choose a suitable n that is divisible by all the common differences (like for instance the product of the differences). But the same idea in that you saw that it's a statement about "density". I've seen others solve this one with generating functions but I prefer our type of soln since it seems more natural.

[TrueTears]

I completely screwed up my first attempt at this, but I realised the trick as I was driving home from a jam

Let   be the number of minimal selfish subsets of .  Consider some .  We wish to find all the minimal selfish subsets of of cardinality .

We first note that our minimal selfish subsets cannot contain any element less then , as the existence of such an element allows us to easily construct a selfish subset, which shows that our original subset is not minimal.

Membership in our set is restricted to and elements between and up to (and including) .  Therefore we have elements to choose from to make our minimal selfish subsets from.  In addition, since our set has cardinality , then for each potential subset we must choose numbers to create a full set.

Therefore the number of ways of creating a minimal subset of of cardinality is .  Summing this over all valid lengths, we find that , which is of course a generator of the general Fibonacci sequence.

lol just had a read of your solution dcc, it makes mine look so retarded, I understand all except for the last bit.

How do you show , is a generator of the general Fibonacci sequence?

[kamil9876]

i remember doing the same soln as dcc when i first saw this q, i found out it's fibonacci by using pascal's identity.

[TrueTears]

So we must prove

[TrueTears]

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

lol kamil I got your 4).



Let's use strong induction.

Base case:

Call our positive integer .

Let .

. Where is a fibonacci number and .

Inductive hypothesis:

Assume that every positive integer less than or equal to satisfies the condition that they can be represented as a sum of Fibonacci numbers, no two of which are consecutive.

Proof:

Consider the interval between and (inclusive).

Every number in this interval can be written as where

Clearly

Which means

But using our inductive hypothesis, every positive integer less than or equal to satisfies the condition.

Which means satisfies the condition.

This implies all the satisfies the condition and so does

satisfies the condition.

[TrueTears]

1. Let denote the number of ways in which a set of elements can be partitioned into non-empty subsets. For example, , corresponding to:











Find a recurrence relation for .

Consider the specific case for .

Let us consider this element set:

Obviously the element must be in every partition.

Let us denote the set that the element is in 'size ' where tells us how many elements are in that partitioned set.

For example, the partitioned set has size .

Consider size 1, we have:



But how many ways can we partition ? Well there are ways to partition it.

Thus for size 1 there are ways.

Consider size 2, we have:



For the 'some other element' we have choices and then for the 'Three element set' we have ways to partition it.

In total we have ways

Consider size 3.

We would have ways

Size 4: ways

Size 5: ways

In total:

Now let's generalise:

Say we have a element set.

[kamil9876]

2.)
a.)

a)

if we have n elements a_1,a_2... then the only way to partition them into one subset is to leave the set as it is.
b.)

b)

we have 2 sets, A and B and each of the n elements must belong to one set only. Hence we have to make n choices, each either A or B, there are 2^n ways of doing this. However one such allocation is "every element in A", and "every element in B", and we cannot have that since that would mean B or A is empty, respectively. Hence ways of doing this. Furthermore the sets A and B are indistinguishible (if we "swap" the sets we still count it as the same partition). Hence we divide by 2, giving the result.

c.)

The example actually gives you a clue for this (it's the case for n=4). By splitting n objects into n-1 non-empty subset, it's neccesary that all of them have cardinality 1 except one of them, which has cardinality 2. Therefore it's just a matter of choosing 2 object to go into this special set, and then the rest of the elements are the single-element sets. hence

3.)

I actually derived this formula as an attempt to solve q1, but didn't seem too helpful.

Suppose we put all the partitions that contribute to {n,k} into a set, A, and those that contribute to {n,k-1} in another set, B.

Now suppose we introduce a new element, x. Then the set of partitions that contribute to {n+1,k} can be made in two ways: Choose a partition from A, place x into some subset in this partition. Since there are {n,k} things in A, and k subsets to choose from each, there are k{n,k} ways of doing this. Another way to make a partition that would contribute to {n+1,k} is to select a partition from B, and simple introduce the set {x} into it. This gives {n,k-1} new partitions. Hence in total it's the sum k{n,k}+{n,k-1}