Discrete Math Question 2

[fiery bridge]

1. Wait patiently for a helper to come along.
2. Once someone helps you, say thank you and close the thread with: ```diff
   +close

[finite sail]

This actually isn't true. Consider the set S = {1, 2, 3, 4, 5, 6, 7, 30}. The closest you can get is A = {1, 2, 3, 4, 5, 6, 7}, B = {30}, but in that case sum A_i = 28.

[plain portal]

What about S = {1 to 8}
A = {1,2,3}
B = {6}

[proper nexus]

No one said you have to use all the elements

There's {1,2} and {3}

Yes

Not every split has to work

It's just that theres at least one that works

Does that make sense?

Yes

Ok I'll try to solve it and then I'll help you

[proper nexus]

alright this is not that bad

so do you want a hint or a full solution @plain portal

Okay

From a set of 8 elements, the number of possible different subsets we can have is equal to $2^8$. However, we exclude the empty set, as the chosen subset cannot be empty. Since all elements of $S$ are less than or equal to 30, any subset of $S$ must have a sum less than or equal to $8 \times 30 = 240$; meaning \textit{each subset of $S$ has one of 240 possible values as its sum (0 to 240).} However, We have $2^8 - 1 = 255$ different possible subsets of $S$, then by the pigeonhole principle there is at least two subsets which have the same sum. \medskip\par

These two subsets are not necessarily disjoint. If they are, we are done. Assume they are not disjoint. They cannot be equal as we have assumed the subsets to be different, and we cannot have one be a subset of the other as then they would not have the same sum. Thus each of the two subsets has at least one element not in the other subset. Let $A=\left{a_1,a_2,\dots,a_i,q_1,q_2,\dots,q_r\right}$ and $B=\left{b_1,b_2,\dots,b_j,q_1,q_2,\dots,q_r\right}$ where $q_1,q_2,\dots,q_r$ are all of the shared elements. Let $A'$ and $B'$ be the nonempty subsets such that $A'=\left{a_1,a_2,\dots,a_i\right}$ and $B'=\left{b_1,b_2,\dots,b_j\right}$. Since $A$ and $B$ have the same sum, i.e. $a_1+\dots+a_i + q_1+\dots+q_r = b_1+\dots+b_j + q_1+\dots+q_r$, then $a_1+\dots+a_i= b_1+\dots+b_j$, meaning $A'$ and $B'$ are disjoint and have the same sum, as required.

Let me know if you don't understand something

[stone fractal]

Pyrodynamic

[proper nexus]

Disjoint means empty intersection

$A$ and $B$ are disjoint $\iff A \cap B = \emptyset$

[stone fractal]

Pyrodynamic

[proper nexus]

No

Their intersection is {3}

Ok

in plain terms, if they share any elements, we can remove those elements from both sets and they will still have the same sum

think about it

example: {1,2,3,4} and {6,4}

[harsh cape]

Right, disjoint just means that there is no number that's in both sets (I should say no element that's in both sets).

[proper nexus]

we can remove 4 from both and still have the same sum

[proper nexus]

Yes

@plain portal that's the general idea, and if there's a specific sentence you didn't understand let me know

[twin valve]

@frank hill has given 1 rep to @proper nexus

[proper nexus]

You're welcome :)

[harsh cape]

I'm brand new here, and what you @proper nexus typed is hard for me to read, because in fact I've never tried to communicate math over a text-based medium very much.

@proper nexus Don't worry about it though, I am just going to learn as I go of course. I'm just commenting.

[proper nexus]

It's challenging to write math on text, that's why we use TeX

You can see the bot's output tho? It's pretty readable

[harsh cape]

This particular problem is just a tiny bit much for me as I am getting started back into doing math again as well.

[harsh cape]

Ah, it's TeX.

Like LaTex?

[proper nexus]

I haven't seen that one properly but it should be similar

[proper nexus]

Yeah

The bot renders out what I wrote

[harsh cape]

I should learn that if I'm going to keep this up. Maybe I will, I still have to decide how committed I am.

[proper nexus]

Well, if you do end up learning it, good luck to you!