TT's Maths Thread

[zzdfa]

and just to put your mind at ease about your little question, you can construct a set for any given x as follows:
find the greatest n such that sum 1 to n is less than x. add n+1. the sum of this set is, at most, n more than x. thus the element corresponding to the difference between the current sum and x can be removed from your set. done

edit add some clarifying examplezz

so for example {1,2,3,4,5,6,7,8} and we want to get 23.

go 1,2,3,4,5,6 sum =21

add the next number, 7 to make it go over 23

1,2,3,4,5,6,7   sum = 28

then remove the 5 to make the sum exactly 23:

1,2,3,4,6,7 sum=23

[kamil9876]

ok I will try prove out of interest your question about whethr for all there exists some set such that .

I will try a proof by induction:

Base case: obviously b=1 has a solution A={1}

Inductive hypothesis: suppose b has a solution A, we will now try a solution B for b+1 (provided )

If A was to have a "gap" like: {.... a,a+k...} where k>1 then we can merely delete a and introduce a+1 and we are done. Likewise, if say you have the set {...a} where a is the largest element and not 30, then just swap a with a+1.

Now if A did not have a gap or largest element less than 30 then it must not contain 1, (otherwise it is the WHOLE set and b=465 and there is no solution for b+1). Therefore in this case, just introduce 1 and you're done.

edit: beaten by zzdfa

[Ahmad]

I'll show an alternative induction, because it illustrates an important idea in induction. Which is that it's often simpler to prove a more general statement. Another useful thing to think about when trying a solution by induction is that it's often helpful to prove a stronger statement, since it gives you more power in the inductive step.

Let be the statement: for all natural numbers n, there exists a subset of with element sum any given number in .

The base case is trivial, do it for n = 1 and n = 2. So suppose is true, so that from we can form the element sum of any given number in . Now consider the subsets of which don't contain k+1, this is just the set of subsets of A_k, from which we can form , by adding the element k+1 to each of these subsets we can form , so we can form all numbers from to , as required.

[kamil9876]

Yeah when i went to take a leak I thought of about 10 other proofs by induction, and this one is still a new one

[Ahmad]

You think of maths while taking a leak. Nice.

[TrueTears]

Yeah when i went to take a leak I thought of about 10 other proofs by induction, and this one is still a new one

LOL

[kamil9876]

You think of maths while taking a leak. Nice.

sometimes I deliberately go without the need to, just purely as a source of inspiration.

[kamil9876]

3. Let be a set with elements. In how many different ways can one select two not necessarily distinct or disjoint subsets of so that the union of the two subsets is ? The order of selection does not matter. For example, the pair of subsets represents the same selection as the pair

Suppose we have

Each element of S must have one of these three muttually exclusive properties:

1.) it is in only
2.) it is in only
3.) it is in

(you may already tell that this is similair to your previous ice cream problem)

hence we have choices for each element of S. Hence different combinations of choices.

(note though that my solution regards and as two different things. )

[/0]

Let be the statement: for all natural numbers n, there exists a subset of with element sum any given number in .

Why do mathematicians insist on proving things like this? :/

[TrueTears]

Let be the statement: for all natural numbers n, there exists a subset of with element sum any given number in .

Why do mathematicians insist on proving things like this? :/

Once you understand why, you will become a true mathematician.

jk jk

[TrueTears]

3. Let be a set with elements. In how many different ways can one select two not necessarily distinct or disjoint subsets of so that the union of the two subsets is ? The order of selection does not matter. For example, the pair of subsets represents the same selection as the pair

Suppose we have

Each element of S must have one of these three muttually exclusive properties:

1.) it is in only
2.) it is in only
3.) it is in

(you may already tell that this is similair to your previous ice cream problem)

hence we have choices for each element of S. Hence different combinations of choices.

(note though that my solution regards and as two different things. )

But doesn't the question say and are the same?

[kamil9876]

probably. Fix it. gogogo

[TrueTears]

probably. Fix it. gogogo

Oh wait I got it.

Let

So each element can either be in or in or in .

So we can have something like:

and

and

Which is an overcount since we don't care about order.

This means each pair is counted twice rather than once.

But there is one exception: If we picked all the elements in to be in then we have only counted that once.

[TrueTears]

Just another Q, I can do it algebraically but what about a combinatorial argument method?

Find a formula for

Since

Let and








So yeah what is a combinatorial way? Nvm I got it.

Notice how can be rewritten into

So just imagine objects gets split into piles containing objects each.

If you pick objects from the first pile then you must pick objects in the second pile.

This means you are basically picking objects out of objects.

[kamil9876]

Let be the statement: for all natural numbers n, there exists a subset of with element sum any given number in .

Why do mathematicians insist on proving things like this? :/

Once you understand why, you will become a true mathematician.

jk jk

It's an interesting phenomena: is claiming something to be trivial a sign of genius, or a sign of ignorance?