discrete-math

[elder berry]

woah the writing is so pretty

and yeah, it's correct

another way to show practically the same thing but faster, it is noting that if a+7b = 2k and b+7c = 2s, (for some integers k, s) then a+7c = (a+7b) + (b+7c) - 8b = 2k + 2s - 8b which is divisible by 2

[sharp locust]

i came up with a simple proof for this (basically generalized proof for ramsey) but i dont understand the proof in the handout

theres some typos in here i think

i think theres a typo here

how to choose a (k+1) subset from a k set

also this is my proof:

We prove a more general statement. We claim there exists a least integer $HR_k(l_1,l_2,\ldots,l_r)$ such that if $n\geq HR_k(l_1,l_2,\ldots,l_r)$ and all the $k$-subsets of an $n$-set $S$ are $r$-colored, then there exists an $i\in{1,2,\ldots,r}$ such that all the $k$-subsets of some $l_i$-subset of $S$ have color $i$.

We proceed with induction on $k$ and $l_1+l_2+\cdots+l_r=m$. The base cases are $k=1$ and $l_1+l_2+\cdots+l_r=r$, both of which are trivial.

Assume the statement for $k-1$ (for all $l_1+l_2+\cdots+l_r$) and $k,l_1+l_2+\cdots+l_r-1$. Let
[
h_i=HR_k(l_1,\ldots,l_i-1,\ldots,l_r)
]for all $i\in{1,2,\ldots,r}$. We claim
[
HR_k(l_1,l_2,\ldots,l_r)=HR_{k-1}(h_1,h_2,\ldots,h_r)
]works. Let $n\geq HR_k(l_1,l_2,\ldots,l_r)$ and $S$ be a $n$-set with all the $k$-subsets $r$-colored. Choose an element $x\in S$. Let each $(k-1)$-subset $A\subset S\setminus{x}$ be colored with the color of the $k$-subset $A\cup{x}\subset S$. It follows that there exists an $i\in{1,2,\ldots,r}$ such that all the $(k-1)$-subsets of some $h_i$-subset of $S\setminus{x}$ have color $i$. Let this $h_i$-subset be $T$. By the induction hypothesis, there exists either a $j\in{1,\ldots,i-1,i+1,\ldots,r}$ such that all the $k$-subsets of some $l_j$-subset of $T$ have color $j$, or all the $k$-subsets of some $(l_i-1)$-subset of $T$ have color $i$. If the former, we are done. If the latter, we can add $x$ into the $(l_i-1)$-subset to get a good $l_i$-subset of $S$. Thus the statement holds for $k,l_1+l_2+\cdots+l_r$. $\square$

[vital dew]

Kevin Yang

[tight hound]

The inequality you are being asked to prove is equivalent to 2^(n-1) ≥ 1

[grim tapir]

not sure why these 2 points are true tbf

[restive void]

first one:
isolate r -> if you can divide a and b by d, then you can divide a linear combination of them. if that side can be divided by d, then r can be as well.

use the same logic for the second one

[restive void]

I ripped these from my prof's lecture notes if they help here since you are doing congruence mods i assume

[grim tapir]

yeah i just formed some equation and it said r/d = something that we know is an integer

[novel ore]

can i get a hint to show that if for rationals a1, a2, b1, b2, if a1 - a2 is an integer and b1 - b2 is an integer, then a1b1 - a2b2 is an integer?

wait what this is not true

[coral parcel]

No, definitely sounded too good to be true.

[novel ore]

oh shit yeah i forgot we were talking about the additive group of rational numbers

was trying to show that the given equivalence relation was a congruence relation on Q

but forgot it was under addition

[coral parcel]

Build an NFA for all the strings either are too short or contain the forbidden subsequence; convert to a DFA; interchange accepting and non-accepting states?

Nondeterministic finite auomaton.

I told what my immediate approach would be. ¯_(ツ)_/¯

[sharp locust]

complimentary counting + pie maybe

depends on what the binary string is i think

[glacial flame]

I seem to be getting rusty; when we say that A does not (necessarily) imply B, is there a nice equivalent notation for this (other than a slash through implication)? Is this notation even "right?"

$A \not\implies B \equiv ?$

[vital dew]

JJCUBER

[outer portal]

Personally I think $\neg(A \implies B)$ is more clear but I think people would understand if you used the slashed through arrow

[vital dew]

mandelbruh

[glacial flame]

Does that mean that this statement is different from A does not necessarily imply B?

Since not necessarily seems to be a much weaker statement

[outer portal]

If you want to talk about necessity it might be better to use modal logic

"It is not necessary that A implies B" would be $\neg \square (A \implies B)$

[vital dew]

mandelbruh

[outer portal]

https://en.wikipedia.org/wiki/Modal_logic

[ivory badge]

A => B should be false iff A true and B false kinda thing, so if they’re predicates in a sense you could put $\neg \forall x (A(x)\implies B(x))$

[vital dew]

The great Sharp

[sharp locust]

theres overlap

if two sequences exist at the same time

it depends on the sequence

yes

if the sequence is random its different than if the sequence is just 11111111

wdym

for example if its 11111111

then

111111111

contains 2 of those sequences

however

if the sequence is something random like 10011010

you cant have 2 such sequences exist at the same time

whats a subsequence here

suppose the sequence ABCDE

is ACE a subsequence

o

ok

theres an otis application problem on this

[ivory badge]

You can probably do a DFA like what troposphere suggested

[sharp locust]

https://web.evanchen.cc/upload/otis-app-ix.pdf

C.3

[haughty garden]

What type of class is this?

There’s a nice-ish dynamic programming solution which counts the number of such strings

But I’m not sure if this is an algorithms class

[sharp locust]

^ C.3

[haughty garden]

Yeah so naturally a dynamic programming solution could be good because it is inherently a recurrence relation

[sharp locust]

ok so

[haughty garden]

But the dp approach is kinda convoluted

[sharp locust]

let the string be s

let s' be the string without the last digit

yes

obviously s' doesnt contain the sequence

let the sequence be r

and the remove the last digit of r

call it r'

if s' contains r' then the last digit of s cannot be the last digit of r

done

[ivory badge]

How is this obvious

[sharp locust]

wdym

[ivory badge]

101000 contains 101

[sharp locust]

i mean it cant

i know

s' cant contain r is what i meant

[ivory badge]

But if r is 101

Then 10100 still has it?

[sharp locust]

but 101000 is not a valid string

[ivory badge]

Why isn’t it

[sharp locust]

^

[haughty garden]

It’s more that we’re building up all of the valid strings from whatever the base case is

I think

[ivory badge]

Yeah why is that not a valid string

[sharp locust]

its not a good string

it contains 101

[ivory badge]

Ok so you already suppose that s doesn’t contain it

[sharp locust]

ye

thats what we are counting

its assumed

[ivory badge]

You’re supposed to count the strings of length n

That don’t have it in it

[sharp locust]

s is of length n

[ivory badge]

Yes, but s’ is n-1 clearly

[sharp locust]

use recurrences

induction

thats the point

[ivory badge]

Hmmm

[sharp locust]

the whole point is that s' is smaller than s so you can apply induction

[ivory badge]

Well what exactly is the induction you apply

[sharp locust]

wdym

i havent worked out the details

[ivory badge]

Well you now have s’, which contains neither r, r’

[sharp locust]

its just an outline

[sharp locust]

s' can contain r'

if it does then the last digit of s cant be the last digit of r

[ivory badge]

What can you do with it, ya know what I mean

Right right

[sharp locust]

find all strings s' not containing r

[ivory badge]

Which means there’s exactly one s to that s’

[sharp locust]

find all strings s' not containing r'

find all strings s' containing r'

[ivory badge]

then a lil bit of 2x+y

[glacial flame]

I see, thanks!

[glacial flame]

Ah yeah that makes sense

[grim tapir]

not sure how they can get to -7^3

[coral parcel]

23 == -7 (mod 30)

And (-7)³ = -(7³)

Curiously, in the rest of the computation it looks like they really mean (-7)³ even though they write -7³.

Because -7³ is definitely not the same a -7² × -7, but it is the same as (-7)² × -7. Sigh.

[grim tapir]

yeah so they are congruent you mean?

-7 (mod 30 ) = 23 (mod 30) okay

[grim tapir]

sure

just a random youtube video dont think they would check that hard

[coral parcel]

Yes, the standard notation $a \equiv b \pmod{n}$ for congruence is often written a == b (mod n) in plain text.

[vital dew]

Troposphere

[grim tapir]

in RSA , how did they come up with these values exactly seems a bit random yk

what is the significance of gcd(b, phi(n)) = 1

[unreal stump]

Because you want b^-1 to exist

[grim tapir]

oh yeah the multiplicative inverse only exists for b if its relatively prime fair

with phi n

yeah so for n its made so its like factored into 2 primes for sure

cause you could just have a random composite number but i presume it breaks the security guarantee obbv

[unreal stump]

If n is not a semi prime, you can factorize it pretty quickly

Suppose n has like 1000 bits,(i.e. n > 2^999), if it were semi prime,i.e., n= p*q, worst case you will have to search through a significant part of the <=500 bit primes, to gain any information about n.(i.e. while bruteforcing)

If it instead were factorizable as p*q*r, now we need to search through a significant part of only <=333 bit numbers, if you are bruteforcing

In general you would be able to deduce some information with lesser effort, if n is not semi prime

@grim tapir so basically instead of having to bruteforce upto 2^(n/2) numbers, you would have to brute force through a much much smaller set

Well there can be non brute force exploits, but even for brute force this is weaker

[grim tapir]

ight

they calculate b aswell ig too to get the fully private key

acc nah nvm they have b

[unreal stump]

Well b is public tho

[grim tapir]

yeah

[grim tapir]

so this is what RSA does the semi prime method

how did they acc calc 10453 in that example

[unreal stump]

Well just like use extended Euclidean

[grim tapir]

okay let me check that again tbf

so our A =4057 and B = phi(n) then?

4057 x b^-1 = 1 mod (16637), so yeah use ee thing should be calm

[vital dew]

Indra

[grim tapir]

how exactly does the exponent link to the multiplicative inverse calculation for a ?

sumn to do with this ig

[coral parcel]

The modulus does need to be square-free for encryption to be reversible.

[grim tapir]

i dont see how eulers theorem has any relation to this bit

its completely different i swear

should it not be gcd(b,n) ?

also if it mods with some value n, that means the plaintext is limited to that n ig

[grim tapir]

like we use phi(n) right because it needs p and q to be calculated ofc

thats the only reason for phi n ig

[grim tapir]

like this is my current understanding of it just a bit weird the ab = 1 mod \phi n bit.

[grim tapir]

what is this on about, dont understand the reasoning

[somber ginkgo]

x = {1,2,3} ;A = {1,{1,2},{{1,2,3}}}
is X subset of A?

can u answere this guys?

and what are the power set?

[quiet girder]

What do mean by that? Are you asking to ask for the power set of set x = {1,2,3} or the one for set A = {1,{1,2},{{1,2,3}}}? Or the power set some subset X of A?

[ruby zephyr]

Hi! I'm trying to calculate Catalan numbers. I reached the point in which I know an important property of its generating function f. The exercise tells me to consider g = x*f and show that g = x + g^2. I did that. Now the final step is finding the coefficients of g but I don't know how.

[ruby zephyr]

for X to be a subset of A, every element of X should be an element of A, but for example, 2 is in X but not in A

[unreal stump]

Well you can rewrite that as
g^2-g+1/4= 1/4-x, i.e. g(x) = 1/2 + sqrt(1/4-x) or g(x) = 1/2 - sqrt(1/4-x)

You find which one is the correct g by checking and cross verifying the coefficients

I guess you can compute coefficients of sqrt(1/4-x) using generalized binomial

[ruby zephyr]

How do I know sqrt(1/4-x) exists in C[[X]]

Because it is a ring if I'm not mistaken and quadratic equation works on fields

[unreal stump]

Because this is kind of a thing
https://math.stackexchange.com/questions/732540/taylor-series-of-sqrt1x-using-sigma-notation

[ruby zephyr]

(correct me if I'm wrong)

[unreal stump]

I assume you just like change some terms and get what you want from this

[ruby zephyr]

Ok, I'll try with that

Thank you

[true venture]

How does the last step work to get (1+x)^n?
What if B_n-1 was B_n-k?

[true venture]

Wait I kinda get it cause you would recursively multiply (1+x)(1+x) n times

[ruby zephyr]

That happens if B_0 = 1 though.

[ruby zephyr]

I have this question:
Let $P$ and $Q$ be finite posets. Let $P \times Q$ be a poset with this order: $(p_1, q_1) \leq (p_2, q_2)$ if $(p_1 \leq_P p_2) \wedge (q_1 \leq_Q q_2)$. Prove that $\mu_{P \times Q}((p_1,q_1),(p_2,q_2)) = \mu_P(p_1, p_2) \cdot \mu_Q(q_1, q_2)$.
$\mu$ is defined by:$\$
$\mu(x,y) = \zeta^{-1}(x,y)\$
$\zeta(x,y) = \left{\begin{matrix}
1\ if\ x \leq y\
0\ if\ x \nleqslant y
\end{matrix}\right.$

[vital dew]

Casiel368

[ruby zephyr]

I proved that $\zeta_{P \times Q}((p_1,q_1),(p_2,q_2)) = \zeta_P(p_1, p_2) \cdot \zeta_Q(q_1, q_2)$ and I'd love to just "take inverse" in both sides but that is sadly not possible. What can I do?

[vital dew]

Casiel368

[true venture]

Oh yea

[urban berry]

hey can i post a proof here?

i have a small question about my proof for the triangle inequality

[tame trail]

may i ask how do i approach to prove this?

[unreal stump]

Well you can construct a bijection from [0,1] to [a,b]

That should give you that they have the same cardinality

The bijection f would be
||f(x)=a+(b-a)x||

[tame trail]

oh ok i'll try!

[tame trail]

what was ur thought process to come up this function?

[unreal stump]

I mean the natural approach is to find a bijection that maps 0 to a and 1 to b

And well the first time that should come to your mind is polynomial functions

[tame trail]

i understand, thx for ur help!

[wheat grove]

I've been thinking about the definition of the contraction of a matroid --- would it imply that for any i in I', i is a subset of Z?

because if there exists some x in i which isn't in Z, i union Z is a superset of Z+x which can't be in I as Z is a basis

[little prism]

Z is a basis of Y. not of X

you could try translating this into the language of linear independence as an example

[chilly hemlock]

how to find alpha?

sorry, i meant sigma

[little prism]

do you know what sigma (x1, x2, x3, ..., xn) sigma^-1 is equal to?

[wheat grove]

oh oops i see

[young zenith]

I've been stuck on this for a while and don't really know how to approach question 3

[grizzled ore]

By third question you mean the the multiple choice?

[young zenith]

nah the tn problem

[grizzled ore]

Try computing t4

By hand and seeing you can notice something given your prior computations

Is certainly a way of starting to approach the problem

Which may help

[young zenith]

ye I tried that

I dont see anything

[grizzled ore]

Well what values did you get

[young zenith]

t2 = 4, t3= 8, t4= 21

and t5 isn't really feasible to list out all of them

[grizzled ore]

Yeah

So note that you have 1 basis element of length 1, 3 of length 2, and 1 of length 3

So if you want to construct a legal string of length n, it suffices to look at what legal strings already exist for n-1, n-2, and n-3

[young zenith]

you lost me

[grizzled ore]

I think to say more would be giving the answer away

[young zenith]

fk ok

[grizzled ore]

v; ww, xx, yy; zzz

Noting that they will not "interfere" with each other

[young zenith]

the only conc I get from that is that ww, xx, yy will have the same number of legal strings

my head hurts

[grizzled ore]

What I am trying to say is that how ever you get your legal string of n letters, you can remove the last legal basis element (say from the right), and end up with some n-1, or n-2 or n-3 length string

Now it suffices to count how many copies of t_i, for i=n-1, n-2, n-3; you need

But given that you already computed an example, this should be fairly doable; the proof also follows similarly

[young zenith]

uhhh

im sorry i feel so dumb

[grizzled ore]

It's OK, this problem is not that straightforward

If you've spent too much time on it already, it may help to take a break and come back

[young zenith]

ok so i = 5 has 21 legal copies, in which 8 legal strings of i = n-1, 4 of i = n-2 and 1 of i=n-3?

now how do i get how many of copies them i need

[grizzled ore]

I'm not sure I understand what you mean

I used the index i because typing on mobile is a pain

I need to go now, sorry

[young zenith]

fk can you please tell me the asnwer real quick I learn the best that way

its a practice for a reason

@grizzled ore its a= 1 b = 3 c= 1 isn't it

[grizzled ore]

Yes

For the last question, if you need a hint to get started: ||a palindrome legal string of length n is completely determined by what is occurring in the first ceil(n/2) letters; intuitively, what happens in the left side and middle||

[chilly hemlock]

@little prism Solved it but thanks anyway

[ruby zephyr]

Please?

[ivory badge]

I think that's a different kind of inversion, but if you want to show it's an inverse under an operation try multiplying them

[ruby zephyr]

$\mu$ and $\zeta$ are functions in the incidence algebra of the poset, so when I write inverse it's the inverse of the algebra

[vital dew]

Casiel368

[ruby zephyr]

$\mu*\zeta = \delta$ where $\delta(x,y)$ returns 1 if $x=y$ and 0 if $x\neq y$

[vital dew]

Casiel368

[ivory badge]

Right right, how difficult is it to just multiply it out to show it works as expected

[ruby zephyr]

How would I multiply?

I mean, I have this: $\mu_{P \times Q}((p_1,q_1),(p_2,q_2))$ and this: $\mu_P(p_1, p_2) \cdot \mu_Q(q_1, q_2)$. The product on the second expression is the real product, not the product between functions. Also, I don't have a closed general expression for $\mu$ because it depends on the poset, so it is not possible to work out the products by definition. It is the case with $\zeta$ though. It is easy to show that it satisfies the property just by definition.

[vital dew]

Casiel368

[grim tapir]

confused for this tbf

why are they taking the gcd(p-1, q-1)

and where did (p-1)(q-1) come from exactly

Like it makes sense they are prooving that specific exponent produces 1 mod p based on some semi prime pq but cant link it together ig

example above got mod 15, showed the exponent was 4 by breaking into the prime factor congruences things

but yeah not sure fully what this theorem is saying

[scenic latch]

its eulers function

phi

since phi(prime) = p-1

and also the GCD(prime, another prime) = 1 always so thers no point to do that

[inner otter]

yes it should have arrows

[tardy sun]

q6?

[ivory badge]

what is (y-x)+(z-y)

Rational+rational=rational

z-y=c/d means z=y+c/d too

[unreal stump]

"Q shifted by an irrational constant along with Q"

Those are the classes

[frozen rune]

i second this motion^

[unreal stump]

Ok so all equivalent classes will be of the form [x]={x+q| q \in Q}

If x is rational this Q itself

Otherwise you get all the shifted sets

[ivory badge]

+q and -q are the same

because q and -q are both in Q

[ivory badge]

No

I’m saying there’s no need for two of those expressions

And why do you have like “both x & y must be rational”

[steep blaze]

can anybody tell me what is the value of x: X + 1 = 0

[steep blaze]

plase tell

[tight hound]

Please don't troll

[haughty garden]

Well clearly x and X are different so we cannot tell

[steep blaze]

Correct! i wanted to test common sense.

actually i am in 9th grade

can i ask questions here

please

because i like discord than any math solving website

i like math so much

math is fun

why isn't anybody talking to me

did i make a bad impression

by asking that question

can anybody be my friend

i am suffering from loneliness

i am new on discord

hello

please say anything

it's my maths exam on tuesday

i am preparing for it

so maybe if i can ask some doubts

[weary tiger]

lol

[steep blaze]

please don't make fun of me

i thought it was a helpful server

[weary tiger]

i mean bro u shouldn't propably talk about your problems to random people on discord

it's kinda weird

[steep blaze]

sorry

can anyone please send me extra questions on heron's formula class 9

only important questions

[brave rock]

Not sure why you're posting this in #discrete-math and not #geometry-and-trigonometry

I googled "heron's formula questions" and got a lot of results, for instance this site. Is this helpful for you? https://www.vedantu.com/maths/herons-formula-important-questions

[steep blaze]

thank you so much

i will pay attention from now onwards

@frozen runehello

[uneven silo]

hi

@steep blaze

[quick meteor]

Thanks in advance!

[unreal stump]

f is clearly not injective

Im(f) is a proper subset of N

So it is not surjective

[little prism]

standard notation for the image of f

[honest holly]

f({0}) = f({1})=2

[brave rock]

Not lm, but im.

If $f \colon A \to B$ then $\operatorname{im}(f)$ is defined as ${f(a) \mid a \in A}$ and is a subset of $B$.

im stands for image.

It's a pity the bot is down.

Exercise: Prove that f is surjective iff im(f) = B

[weary tiger]

So I have three sheets for a final upcoming up, and I need the answers to the review sheets as I cant find them online

Anyone willing to help?

[inner otter]

do you have a specific problem?

[weary tiger]

I need help with the whole sheet

at least most of it

[brave rock]

I would suggest just asking your quesitons

[weary tiger]

can i take a picture

of the sheet

its easier that way

[inner otter]

sure. and show your work, too

[weary tiger]

know

how to solve the problems

[quiet tendon]

does anyone know the general formula for this

I thought inside the brackets was the same letter

so x for example

[inner otter]

what do you mean?

[quiet tendon]

so I thought it was f^-1(f(A)) and f(f^-1(A))

[honest holly]

what have you tried?

it would be a good exercise to figure out the right formula

[steep blaze]

hello

[mystic valve]

Do you guys know what math we will learn in year 9

Pls give me some hits

So I can pre study first

[quiet tendon]

anyone can explain why these 2 equations are equivalent

I always knew they were but never derivated it

nvm

I see it

[coral parcel]

It will almost certainly be more efficient to use your time to make sure you are completely and effortlessly familiar with the stuff from earlier years.
If you have all the prerequisites fully mastered already ... then it would seem you're not someone who needs to "pre-study" at all anyway.

[quiet tendon]

this is realy confusing but first question is to have circle table with 8 people and 8 charis and second question is about n people and n chairs

whereas they can't have the same neighbour

I understood that rotating part so the formula becomes n! / n but he adds a mirroring term idk why must be a mistake

[coral parcel]

You haven't shown the question this is an answer to. But it looks like it is a situation where "the same sequence of persons, but listed counterclockwise instead of clockwise" is also something you need to count.

[quiet tendon]

In how many ways can eight people be seated at a round table with eight chairs?
where two placements are considered the same as each person in both
placements has the same left and right neighbour?

In how many ways can n people be placed around a round table with n chairs
where two placements are considered the same as each person in both
placements has the same neighbors?

if that's the case why didn't the first question where there is 8 people have also considered the counterclockwise part

[coral parcel]

Because in the first case the left neighbor in one arrangement must also be the left neighbor in another before you consider them the same.

In the second case, it's enough that the left neighbor in one arrangement is one of the two neighbors in the other one.

 A B      G F
H   C    H   E
G   D    A   D
 F E      B C

These two arrangements count as the same in the second case (for example C's neighbors are B and D in both of them). But it doesn't count as the same in the first case because C's left neighbor is D in one of them and B in the other.

[quiet tendon]

ahh I think I see what u mean say left neighbor is B and right neigbour is C then when u swap it it's still considered the same in part b therefore the counterclockwise plays a role whereas in part a it's not the same

[quiet tendon]

ahh I see thank you for helping

although I find it hard to see on my own that I also had to consider the counterclockwise part

[coral parcel]

That's just up to experience, I'm afraid.

[quiet tendon]

ye I guess, because I am slowly seeing specific cases where they keep adding for example first the rotation part now the mirroring part and prob there are more

[quiet tendon]

In how many ways can a group of n persons be divided into two equal groups (with
n ≥ 0)?

why does he times 1/2

[meager prawn]

nC(n/2) counts the number of possible first groups which each correspond to a pair (a, b)
However you want all the {a, b} so order doesn't matter, so you divide by 2

[quiet tendon]

but doesn't combination already takes into consideration that order doesn't matter?

[meager prawn]

Not the same order

It ignores the ordering of people inside group a

You want to ignore the order between a and b

[quiet tendon]

uhh what u mean by a and b exactly?

can u do like an example of a group of 4 for example

[meager prawn]

First and second group

[quiet tendon]

oohh so u mean

combination switch the group too

[meager prawn]

The 1/2 comes from the order of the groups, which we want to ignore

[quiet tendon]

ye so u mean like if firtst group comes first with the exact same people or the other groups comes first right?

[meager prawn]

I think

[uncut herald]

Yeah that’s exactly right. It becomes more clear if you think of it as multinomial coefficients and don’t use the notational shorthand, ie instead of (n n/2), using (n n/2, n/2) which denotes that category 1 holds n/2 and category 2 holds n/2. The categories are distinguishable, yet they aren’t in the problem

More generally think about it in terms of if it’s divisible by 3, how can we divide among 3 equal groups? Well then we see (n n/3, n/3, n/3), but that is if the categories themselves are distinguishable, but since they aren’t, you divide by 1/3! so any arrangement of the 3 groups are the same as long as they contain the same people

This easily extends further

[quiet tendon]

ahhhh

I never knew that combination was also distinguishing the groups itself

but now I understand it

[uncut herald]

Without multinomial coefficients you might consider (n n/3)(n-n/3 n/3) to be equivalent to (n n/3, n/3, n/3)

Well it is

[quiet tendon]

ye tbh at first I alr considered like a multinomial and I saw that inside the groups the order didn't matter

but I didn't knew combination was not ignoring the fact that order of groups were distinguishable

[uncut herald]

I mean binomially specifically for the problem “selecting” group 1 and leaving group 2 gives you a different “selection” than “selecting” group 2 and leaving group 1

But in the end they are the same groups

[quiet tendon]

ye I never saw it that way I just thought combination means order didn't matter so it must have considered that they are the same

[quiet tendon]

I guess I know it for the next time I hope I see it then

[uncut herald]

Another fun problem to work on in the same vein, how many ways can you make a circle of 7 people if two circles are considered the same if everyone has the same neighbors

[quiet tendon]

uhh I think I alr did excercise but let me calcualte it

[quiet tendon]

a

I did this one

is it 1/2 * 6!?

[uncut herald]

Yep

[quiet tendon]

ye on this excercise I didn't understood the 1/2 part

but someone explain it was because

if u go counterclockwise

u have like still the same neighbours but switched and that's still considered the same

so then u gotta havve like 7! / 7* 2

[uncut herald]

Here’s the way I do it, take each circle and make it a list ie ABCDEFG circle is the same as GABCDEF and so forth, so those 7 circles are the same for every case

But now consider

[quiet tendon]

ye I did it this way too

[uncut herald]

GFEDCBA which is a different permutation than ABCDEFG

But the same circle

ie every circle portrayed as a list is portrayed by 2 permutations

[quiet tendon]

is this counterclockwise?

[uncut herald]

Just look at the neighbors

Everyone has the same ones yes

[quiet tendon]

I see what u mean

I think I did the exact same

or the thought process is the same I mean

well I guess I understand it now

[quiet tendon]

it was just frustrating at the first time when i couldn't understand it

[uncut herald]

Have you covered multinomial coefficients yet

[quiet tendon]

ye I did alr

btw can I ask another question

[uncut herald]

Alr so here’s one of my favorite ones. You have 3 red socks, 3 blue socks, 4 green socks in a box and if socks of the same color are indistinguishable, how many ways can you draw out 8 socks

[quiet tendon]

this is a hard one

I know how to do if u want to draw out 10 socks

oh wait 10 socks is just 1

[uncut herald]

Yeah no order does matter sorry

The order in which you draw them out

[quiet tendon]

ah

ye I am not so sure how to do this one

because either I take alot of situations which prob isn't the way to do

I wanted to do smth like 10! / 3! 4! 3! but I am not taking 10 socks

[uncut herald]

Yeah do each individual case

Ie you can do (8 1, 3, 4) two ways

[quiet tendon]

so it had to been like 10! / 1! 4!3!2! + 10! / 3! 2! 3! 2! + 10! / 3!4!1!2!

but I am not so sure

because he can also take combinations of this

[uncut herald]

Let category 1 be red, category 2 be blue, and category 3 be green

Then we see there’s 8!/1!3!4! + 8!/3!1!4! + 8!/2!3!3! + 8!/3!2!3! + 8!/3!3!2! + 8!/2!2!4!

ie there’s only 6 ways this can end up

For each of them the multinomial coefficient describes the number of ways you can end up with that result

[quiet tendon]

ah I see so this will be the answer then right>

[uncut herald]

Yes

[quiet tendon]

can I ask a differnet question

[uncut herald]

Sure but I may not be able to answer it

[quiet tendon]

Let n, k ∈ N with k ≤ n. Calculate the number of pairs (A, B) with A, B ⊆ Nn, |A| = k, |B| = m and
A ∩ B = ∅.

I don't understand why he takes n - k for B

I thought it was just n

[uncut herald]

It says A and B are disjoint

Their intersection is empty

[quiet tendon]

no I understood that

but like

if A subset of Nn with k elements

and B subset of Nn with m elements

then they are definitely already disjoint

because to start with they don't have the same amount of elements

[uncut herald]

No disjoint means none of the elements are the same

Not that they aren’t the same set

[quiet tendon]

oh

oh wait

ye

[quiet tendon]

so if it wasn't explicitly said that A and B are disjoint

I should've taken B subset of Nn right?

then it would've become nC(m) right

[uncut herald]

No if it’s not given you can’t do the problem

[quiet tendon]

but isn't it also necessarily to know wether k or m is bigger?

[uncut herald]

This problem is essentially asking (n k, m, n-k-m)

[quiet tendon]

but wait I understand the n k part

but like if m is bigger and u do n - k u won't get the numbers bigger then k right?

[uncut herald]

You have n elements. You want to choose k of them and then choose m elements that are in n, but aren’t in k of which there are n-k.

This is the same as choosing m elements of n and then choosing k elements of n-m

[quiet tendon]

I need to choose m elements that are in n but aren't in A right?

[uncut herald]

Right

There are n-k options

[quiet tendon]

but all the elements in A are of length k

[uncut herald]

It’s saying that each time you select an A it has k elements

[quiet tendon]

yes

but the n-k part is a bit hard to understand

can u maybe give an example

[uncut herald]

Sure let’s do a concrete one

n=5, k=2, m=2

[quiet tendon]

yes

does it btw need that k and m is equal or not?

[uncut herald]

No

[quiet tendon]

ah okay

but equal is easier right?

[uncut herald]

Not at all same process

[quiet tendon]

ah

[uncut herald]

It’s just saying, take out two elements of {1, 2, 3, 4, 5}

And then take out 2 elements of the remaining ones

[quiet tendon]

ye so for A there are 5C(2) options if u choose A first

[uncut herald]

5C2 yeah

[quiet tendon]

ye

and then

uhm

[uncut herald]

3C2 for B

[quiet tendon]

oh u can't choose the same number agian?

[uncut herald]

Like one solution is ({1, 3}, {2, 5})

Because A and B are disjoint

[quiet tendon]

ah but smth like 1,3 and 1,5 can't be the case?

[uncut herald]

Yeah, specifically the fact that A and B are disjoint means that can’t happen

[quiet tendon]

ahh

so if A chose the number 1 and 3

that means B can only choose from 2 4 and 5

[uncut herald]

Yes

[quiet tendon]

and thats for every case

[quiet tendon]

so like A choose 2 number then B choose of the leftover 3 and that continues till A has chosen every possible combination do I see it like this?

[uncut herald]

If they aren’t disjoint then (n k)(n m) is all the options

Yeah

[quiet tendon]

ahh I see

[quiet tendon]

I think I should practice more now

thank you for helping

[uncut herald]

And if they give you like A intersects B = 1, the problem gets a little harder

In that case it should be (n k)(n-k m-1)(k 1)

[quiet tendon]

they did give a different one

but it's not disjoint

Let n, m, k ∈ N with m ≤ k ≤ n. Determine the number of triples (A, B, x) with A ⊆ B ⊆ Nn, |A| =
m, |B| = k and x ∈ B \ A.
(Don't forget to give a full explanation.)

I don't understand the k m part again

well I considered it

but like

well I tihnk I somewhat udnerstand it

[uncut herald]

Wait oh A is in B

Lol

[quiet tendon]

ye

so u choose B first

that means n k

and then u choose A

and A is subset of B

so therefore of the k elements that are of B

u choose m

[uncut herald]

Yeah (n k) for B, (k m) for A, and k-m for x

[quiet tendon]

but my initial thought was n m for A because I thought if

the bigger subset of n already choose all possible combination

[uncut herald]

Always to check if you understand the problem make a concrete example

[quiet tendon]

then the smaller subset of n can't get a dfiferent combination which is in N but not in b

[uncut herald]

Ie m=2 k=3 n=5

Select 3 components out of 5, of those 3, select 2 for m, and the remaining element must be x

The book I’m using though I also have a problem, in an m x n matrix, find the number of ways to arrange 0s and 1s such that there are an even number of 1s in every row and column.

Given m=2 I have sum from j to floor of n/2 of (n 2j) or you could say sum from even k to n of (n k)

But the problem gets confusing with m>2

[quiet tendon]

but in this case they aren't disjoint right?

[uncut herald]

Yeah they aren’t

First you select B and then A

[quiet tendon]

but it has to be a subset of B

[quiet tendon]

but in this case if u choose a subset of B or a susbset of N with 2 elements

won't they be the same always?

[uncut herald]

m and k are just the number of elements of A and B

Not specific ones

[quiet tendon]

ye I know but I meant like

uhm

A is a subset of B but also of Nn

so is there an case where it is an subset of B but not of Nn

so like B is 123 145 135 234 235 345

if A is subset of B

then it's automatically subset of N right?

[uncut herald]

Yes

A subset of Nn

[quiet tendon]

but then I am saying (n m ) and (k m ) are same

which isn't the case right

[uncut herald]

Which is a subset of all natural numbers

Which is a subset of Real numbers

[quiet tendon]

uhh Nn means like all natural numbers till the subscript n

[uncut herald]

I know

[quiet tendon]

ah

[uncut herald]

Weird notation but I got it

Point being

Everything is a subset of something else

[quiet tendon]

ye I understand that point

[quiet tendon]

but my problem with understanding lies in this

[uncut herald]

They aren’t the same

[quiet tendon]

ye

I know that part

but like

uhm

[uncut herald]

Just because B is a subset of Nn and A is a subset of Nn that doesn’t mean they are selected out of the same pool

Because we could then extend that logic to

B is a subset of Nn and Nn is a subset of N so (infinity k) = (n k)

[quiet tendon]

ah I see

so u always take the smallest pool

[uncut herald]

You take the pool you select out of

[uncut herald]

Thoughts on this?

[quiet tendon]

let me check

[uncut herald]

Wait actually maybe I have an idea on something

[quiet tendon]

what u mean

[uncut herald]

We consider that the mth row is a “corrector” row

Ie it just fixes all the currently odd columns if we ensure each row has an even number of 1s

Therefore as long as we ensure each row has an even number of 1s as shown above

[quiet tendon]

but 1 mth corrector row might not be nough

[uncut herald]

The only existing restriction is that we have an even number of currently odd columns

But as each row contains an even number of ones

Any time they don’t overlap you are creating 2 odd columns

Hence the number of columns that are odd by the mth row is always even

Therefore we just “build” m-1 rows according to our formula that produces even rows and the mth row has no freedom

That’s crazy

[quiet tendon]

oh I see

is that also the answer in the solution book?>

[uncut herald]

This problem wasn’t given a solution

[quiet tendon]

oh

why not

[uncut herald]

Apparently in the first editions of enumerative combinatorics professors loved the book and the problems so much but every currently solved problem (there are unsolved problems in the book but they are too difficult to assign as hw or test) was given a solution

So in the recent editions he added problems with no solutions given, usually in the 2 to 3- range which are suitable for grad students to work together on

As that’s who the book is intended for

[quiet tendon]

u are a grad student?

[uncut herald]

Nah I’m self studying but the book is super dense I only got through like one proof and some exercises yesterday

Like a single page on permutations

There’s 350 pages of stuff

And 350 pages of exercises and solutions

[quiet tendon]

ah so u are like undergrad student but sometiems doing the like realy hard excercises

[unreal stump]

How does it compare to Bona's "A walk through combinatorics"

[uncut herald]

Haven’t done that one but I’m sure Google knows

[unreal stump]

Well this books sounds more balanced

[uncut herald]

Generally though people treat his 2 volume series more like encyclopedic than as a specific course, problems rated 4 difficulty are generally done in research papers, some 3s are too difficult even and he just cites a few published solutions

[unreal stump]

Why is it that combi books are always filled with problems that belong in a research paper

[uncut herald]

Because they are so simple to explain yet so hard to do

The matrix one I just think I found a solution to

Rated 2 difficulty

[quiet tendon]

do u still have time for 1 more question?

[unreal stump]

Is the answer (m-1) 2^{n-1}

[quiet tendon]

I don't understand how they got the D

[unreal stump]

Ok,mb each row can take 2^{n-1}

There are m-1 free rows

[uncut herald]

I put (m-1)sum across even k up to n of nCk

Probably a simplification yeah

[unreal stump]

So it should be 2^{{n-1}{m-1}}?

[quiet tendon]

is 0 btw also part of the natural numbers?

[unreal stump]

Yea even sum is 2^{n-1}

[uncut herald]

Yeah then multiply by m-1 free rows

I think

[unreal stump]

So 2^{n-1} 2^{n-1}...?

m-1 times

[uncut herald]

I believe that’s right

[unreal stump]

Then it is this

That's actually a surprisingly nice form

[uncut herald]

The next part is for odds

[quiet tendon]

can someone explain the part how they calculate D

[unreal stump]

Both are odd?

Well it should be exactly the same

Sum of odd k is also 2^{n-1}

[uncut herald]

Yeah except overlapping odds create evens on the last row maybe

[unreal stump]

Well last row is the correction row

Same as the even case

[uncut herald]

Well but like the matrix 1110 over 0111 and there isn’t a last row that solves it

Because it would be an even number

[unreal stump]

If you are considering 2 rows, only 1 is free

[uncut herald]

No 3 rows

[unreal stump]

If 3 rows, consider
1110
0111
0110

Ah

I see

[uncut herald]

Last row has an even number of ones

Tricky

That’s why part 2 Ig

[unreal stump]

Are we sure we don't come across the same problem in even case

[uncut herald]

In evens it works

[unreal stump]

Ok total number of 1s = even
Total number of 1s excluding last row= even

[uncut herald]

Basically because even - even = even

[unreal stump]

I feel like this would be either 2^{m-1}{n-1} or 0 kind of thing

Like it's either all or nothing

[uncut herald]

It’s not though cause identity matrix solves all of them

And a permutation of the rows of an identity

But clearly can’t be all the ways

[unreal stump]

If total number of rows is even, then 2^{m-1}{n-1} should work

Because odd-odd

mb

[uncut herald]

01110, 11100, 00001 yeah I think so

Cause then 01101

Hmm

No

Doesn’t work

Then we have an even number on the right column

[unreal stump]

Yea

Is the difficulty of this higher

[uncut herald]

2+

[unreal stump]

This feels like something like the name game

*nim game

[uncut herald]

I think you need 2 set rows but you can swap them

So maybe it’s 2^((n-1)(m-2)+1)

[unreal stump]

I feel like we may have something like m-2 free rows

[uncut herald]

I think that’s right

[unreal stump]

Well also m has to be odd

[uncut herald]

Nope identity always solves

But you add 1 to account for the fact you can change their order

Considering there has to be symmetry with m and n

Well it has to be consistent with m=2 n=1 having no solutions

I think it’s 0 if m and n have different parities

[uncut herald]

Ahhh yeah you are right!

0 if m and n have different parities

Otherwise that’s the formula I believe

[unreal stump]

How do you know you get everything if it's feasible?

[uncut herald]

Intuition and playing around with the numbers rn but maybe you only need one correction row if they have the same parity

I’m pretty confident based on how the numbers come out

[unreal stump]

Good point

[uncut herald]

Just like put anything down that has the right rows given the parity rule

And the one correction row seems to work

There’s probably a fairly simple proof

[unreal stump]

My idea was have m-2 free rows, let the second last row be a row that corrects the parities such that exactly an odd number of columns have even parity

And last row will be 1s in these columns

I am not sure if that would work because the second last row may have an even no of 1s

[uncut herald]

If you can make a 4x3 work

I don’t think there’s any matrix that does that and 4x3 is large enough we should be past any non pattern issues

And then considering like odd x 1 and even x 1 it’s obvious why only odd x 1 works but that size is small

[unreal stump]

.

[uncut herald]

Oh you mean considering that

My bad

[unreal stump]

Maybe this works when m and n have same parity?

[uncut herald]

Pretty confident any “building” of m-1 rows can be corrected though

For that case

Like build a 3x5 and put the first two rows randomly with odds

Should always be a valid corrector row

If the 1 row corrector theory is correct

I believe it’s “almost obvious” now and that’s the attitude I like to have when trying to prove something as Grothendieck would say

Much easier to prove an answer you have intuition for than try to come up with something from nothing

[unreal stump]

I mean we both agree on the answer

We are arguing about the intuition

[uncut herald]

Here's another problem, given n, r, s, as positive integers, find the number of ways to select r odd numbers out of Nn and s even numbers out of Nn if no two numbers can be neighbors

[unreal stump]

Feels like you have to induct on r and s here

[uncut herald]

I've seen a solution but I'd like to see how people would approach it

Because the solution isn't immediately intuitive to me

[unreal stump]

So my idea is like given r-1 odd numbers and k possible spots for even numbers,(removing all the adjacent even numbers) how will k reduce on adding one more odd number

Well ig it can reduce either 2 or 1(if consecutive to previous largest odd number), if you are adding in a strictly increasing manner

That seems like a nasty recurrence

[uncut herald]

Oh my bad the question is N(2n) not Nn

Doesn't really change the process

[unreal stump]

Ok this approach is really not good

[uncut herald]

What they said is create an ordered solution set S: 1 <= a1 < a2 < a3... a(r+s) <= 2n and compress according to the following formula bi = ai - 2(i-1), giving a multiset M {a1, a2-2, a3 -4... a(r+s)-2(r+s-1)}. Since we can find a unique S given r odd elements and s even elements from the multiset of N(2n-2r-2s+2) and then ordering them weakly increasing to get M, then decompressing M -> S we can choose any r of the odd elements of this multiset, of which there are n-r-s+1 and then s of the even numbers, again n-r-s+1, we can multichoose ((n-r-s+1 r))((n-r-s+1 s))

Which changing multichoose to binomials, (n-s r)(n-r s)

[unreal stump]

That's a lot

[uncut herald]

This one was rated 2+

My guess is those ratings are for him, the writer of the textbook

[unreal stump]

Definitely

[uncut herald]

ie, even some 2s are not immediately clear how to approach

While 3s may take hours or days to solve for an experienced combinatorist

[unreal stump]

Looking at problems like this, I don't think I want to touch a combi book

Well atleast not place so much emphasis on solving everything (because it's impossible)

[uncut herald]

Well my guess is most undergrad textbooks would probably give you like 1 difficulty problems so that you thoroughly get how to use each thing and some 2 difficulty ones, clearly some of these 5s are there for papers to be written

[unreal stump]

Well Bona's book is also exactly like this

Very difficult problems

Ok it's probably easier than this

Does this feel like a (2+) to you?

[uncut herald]

Probably like a [2-] but like I don’t see an immediate solution

The reason this one is considered hard is a lot because there's so many topics in such a short space it doesn't really teach you how to do any problems, like the only problems it teaches you how to do are the proofs for the stuff you need to solve the exercises. Ie a 1 difficulty problem would be to figure out how many permutations of w: [7] -> [7] have type (1, 3, 0, 0, 0, 0, 0) because he proves a formula that generates that

And the proof is kinda hard

I'm working on that problem I think I am making progress btw

My injection is f(L) being a lattice path defined by taking a lattice path L from (0, 0) to (k, n-k) which is an ordered set of n elements ex: (1, 0) and ey: (0, 1) and changing the (n-k)th ey to an ex therefore producing a lattice path from (0, 0) to (k+1, n-k-1). If only I could find a way to guarantee injection cause it’s not easy

There are (n k) lattice paths L and yet (n k+1) lattice paths J from (0, 0) to (k+1, n-k-1), there must be more lattice paths J than L if k < n/2 as there exist lattice paths J that are not covered by f(L), for example all lattice paths J that start in ex are not covered in k < n/2

by symmetry we can swap ex and ey to show that we have reflection about k=n/2

Eh my function is not an injection actually for example L1 = {ex, ey, ey, ex, ey} and L2 = {ex, ey, ey, ey, ex} produce f(L) = {ex, ey, ey, ex, ex}

[unreal stump]

Ok this feels like it is in the same league as your matrix question

[uncut herald]

What if we change the second last ey to ex if the function ends in ex?

maybe

hmm

[unreal stump]

{ex,ex,ey,ey,ex}
{ex,ey,ex,ey,ex}

These 2 have same image

[uncut herald]

yeah

[unreal stump]

Ok,I don't think you could have figured this out. This is pretty non intuitive

[uncut herald]

Yeah these techniques are coming outta nowhere

[uncut herald]

The idea is that given any weakly increasing sequence in N(2n-2r-2s+2), which we can generate by taking a multiset of s even numbers, then a multiset of r odd numbers, then overlaying the sets and ordering from least to greatest weakly, we can find a solution set S by transforming using the indices in a way that maintains parity and ensures no two elements are next to each other

So we multichoose from the odd elements of N(2n-2r-2s+2) and then from the evens

[uncut herald]

Although now we know some more tricks for lattice paths

Also there's gotta be more ways to generate an injection that works

Oh, less geometrically speaking, they went from the end of L backwards, swapping ex’s to ey’s and ey’s to ex’s until they net one ey to ex converted

I think

We see that if k > n/2 this doesn’t work for all L to f(L) since for some if you go all the way to the beginning you will still have converted more ex to ey than ey to ex

[native berry]

im taking discrete structures next semester - does anyone recommend any good books or online resources to help me get a head start?

[little prism]

check the syllabus of the course and maybe they recommend a book. "discrete structures" is very unspecific and could do quite a bit of stuff

[native berry]

They do but its pretty expensive. ("Susanna S. Epp, Discrete Mathematics with Applications")

I was hoping to grab something thats priced well and can set me up for the course, its basically just discrete math but centered towards CS

[little prism]

oh you want to buy a book? your university doesnt give you access to books? if only there were websites like that on the internet

anyway, there is probably some stuff in the book channels

[uncut herald]

Huge amounts of free math pdfs

[weary tiger]

Hello guys. I have the following exercise: Let G be a tree. Find an algorithm that has O(|V(G)|) time for preprocessing, such that for any vertices x,y, we can find an x-y-path in G in O(dist(x,y)) time.

I had the following idea, however im not sure if it works:
My idea was to first do to BFS (starting at the root r) and assign a unique prime number p(v) to every vertex in the graph "in an ascending way", so p(v) < p(w) if v is the parent of w. This can be done by taking an increasing list of prime numbers p_1 , ... , p_n, and whenever we add a new vertex to the BFS queue, we give it the next prime, so r gets assigned to p_1, the next vertex gets assigned to p_2 and so on. Furthermore, for every node v we save an array containing all ancestors of v and define Q(v) as the product of all the prime numbers corresponding to these nodes. Now, Q(v) is a unique number for every v with unique prime decomposition which precisely encodes which ancestors v has. For two nodes x,y we can thus find their least common ancestor by finding the largest prime number that divides both Q(x) and Q(y), hence we can just iterate over all prime divisors of x (starting at the biggest one) and find the first prime divisor that also divides Q(y).

The BFS is done in O(n), and finding the largest prime divisor of Q(x),Q(y) needs dist(x,y) steps in the worst case. However, we need a list of prime numbers p_1, ... , p_n to begin with, is this a problem?

[uncut herald]

I’ve found free copies to download on pretty much any book

[uncut herald]

Enumerative Combinatorics, A Walk Through Combinatorics are two for example I found immediately

[weary tiger]

Yeah now that i think about it, this doesnt work since finding the first n prime numbers already is O(nsqrt(n)) ...

[true venture]

Looking at compositions where the absolute value of the differences between neighboring parts are only 1, there is the recurrence $f(n,k)=f(n-k,k-1)+f(n-k,k+1)$ where $f(n,k)$ is the number of compositions of this kind of n, with first part k.
Then writing a generating function $A_k (x)$ for some k and summing over all $n$ we get

$A_k=\sum_{n\geq k} f(n,k)x^n$
For $k>0$, $n\geq k$, and $A_0=0$

Then for the recurrence we can write,

$A_k=\sum_{n\geq k} f(n-k,k-1)x^n + \sum_{n\geq k} f(n-k,k+1)x^n$

Which in terms of $A_k$ is

$A_k = (A_{k-1}+1)x^k + A_{k+1}x^k$

$A_k = (A_{k-1}+A_{k+1}+1)x^k$

Then to generate the sequence of compositions for n, sum $A_k$ over all $k$.

[vital dew]

jo_fish

[true venture]

Does this make sense as a generating function? I have seen generating functions for coin fountains and sandpiles(which are similar to these compositions) written as a continued fraction, would that be a better form?

[weary tiger]

Ok nvm i found a much easier solution, im dumb

[kind vigil]

What’s the cactus that I would use to solve this?

Like my books just says it equals 23 with out actually showing why using calculus

I’m kinda guessing we would use a limit I’m just a little confused on what limit? Is it the limit x-> 1/2^+. (367-n) / 366?

[brave rock]

They didn't use a limit. They just calculated it. In fact, they say it: "After considerable computation [...]"

They used a calculator to multiply the numbers together.

[kind vigil]

But what if I wanted to use calculus to solve it how would it be done?

[brave rock]

When you have a hammer, everything looks like a nail.

Don't use calculus when it doesn't apply.

[weary tiger]

I'm not sure how to find the elements of this set: {x ∈ R : x^2 = 3} can someone help?

[brave rock]

can you put into words what the elements of the set are?

[weary tiger]

This is a set of all things of form x^2 = 3 such that x is a member of the real numbers

[brave rock]

Quite the opposite

it is every element x of the real numbers such that x^2 = 3

we wouldn't typically say "of the form x^2 = 3", this doesn't make sense

[weary tiger]

Oh, that's what I learned from a book

[brave rock]

Now, do you know all the real numbers such that x^2 = 3? If you do, then you've found the elements of the set.

[weary tiger]

I don't know how to find all the real numbers such that x^2 = 3

[brave rock]

I think you'll find that you do know exactly the numbers such that x^2 = 3

maybe you could try solving the equation x^2 = 3 for x

[weary tiger]

ok ill try that

[uncut herald]

Okay I’ve been stuck for an hour, I’m attempting to show that if we are given n+1 columns each of length n composed of 0s and 1s as entries, there exists some n x m matrix where m is between 1 and n+1 inclusive such that the sum of every row is even

I said without loss of generality we can assume every column is unique and not entirely composed of 0s otherwise it’s trivial

It screams of pigeonhole principle but I can’t find a way to use it

[kind vigil]

• or - 3

[weary tiger]

https://www2.cs.uh.edu/~arjun/courses/ds/DiscMaths4CompSc.pdf

[weary tiger]

That's what I found before but I wasn't sure why it was the case

[brave rock]

This is wrong.

3^2 is not equal to 3.

[weary tiger]

yeah

[kind vigil]

O I mean squarroot 3

[brave rock]

OK, while this is correct, I think you should have left Syn to figure this out himself.

[kind vigil]

O sorry 😢

[weary tiger]

I will still solve it myself

[brave rock]

I'm interested in this question. Can you be more specific about the parameters of the nxm matrix, is it just that every column in it is taken from the nx(n+1) matrix? Also, I assume that all numbers in sight are integers haha

[uncut herald]

Every m and n are integers yeah

[brave rock]

I meant in particular the entries of the matrix

[uncut herald]

And yeah you nailed it

All are 0’s and 1’s

[brave rock]

OK

I see that on rereading now lol

[uncut herald]

There was another problem but after converting to the matrix thing I just need them to be 0 mod 2 to solve it, so 0’s and 1’s are fine

[brave rock]

OK, so I assume you've realised that there are 2^{n+1} possible choices for candidate nxm matrices?

wait wait hold on, I overcounted

should just be 2^{n+1} - 1 (fixed it)

[uncut herald]

The original question is to show that for every set of size n+1 of integers where every integer is factorable into the first n primes there exists a subset which when taking the product of all its elements produces a perfect square

[brave rock]

yup alright, well continuing

(since this is totally equivalent)

There are 2^n possibilities for the sum of its columns

(mod 2)

so we do get two matrices with possibly different ms but the same column sum

now here's the big trick

[uncut herald]

Ahhh

[brave rock]

No there's more

If these matrices have totally distinct columns (as in, they choose different columns from the matrix) then we just pool those columns and we're done

But what if they have some columns in common?

I think you should take it from here.

I'm pretty sure I can see the argument

[uncut herald]

Any columns in common we just squish together and ignore the rest

[brave rock]

Well would that give us an even sum?

[uncut herald]

Like it auto solves given any repeat columns

[uncut herald]

Yes I noted that part I think here

Unless I am misinterpreting

[brave rock]

No that's not it

Let's say matrix A chooses columns 1, 2, and 3. Let's say matrix B chooses columns 1, 2, and 5.

If I smoosh these together, you'd get a matrix with columns 1, 2, 3, and 5, right?

And this would typically not have an even column sum

When I'm saying column 1, I mean the first column from the big nx(n+1) matrix

[uncut herald]

Right okay I follow

[brave rock]

there is a way of fixing this problem, maybe you can see it

[uncut herald]

I’ll work from what you have here and let you know if I find something

[brave rock]

OK 👍

[uncut herald]

Should this be rows or am I confused on this

Like from left to right summing

You get either a 1 or 0 mod 2 in each row

As you go down

[brave rock]

So there are n entries in the sum

there are two options for the first one, namely 0 or 1

there are two options for the second entry

so on so forth

so in total, there are 2^n possible sums.

[uncut herald]

So the “sum column” of the columns of each n x m matrix

[brave rock]

Yes

[uncut herald]

Has 2^n possibilities

Okay I was just unsure on that

[brave rock]

This is how we apply the pigeonhole principle.

But we're past that. I suggest you think directly about the problem that I brought your attention to.

We have two matrices with the same sum, and they may choose some of the same columns from the nx(n+1) matrix

how can I, using this information, find a matrix whose sum is 0?

[uncut herald]

You just remove the columns that overlap

Is that it?

[brave rock]

Can you explain why you think that works?

[uncut herald]

Well if it works if the columns are distinct, then take all the non distinct parts and remove them, resulting in essentially the sum of the distinct parts

[brave rock]

That's a bit of a rough explanation, but yes

it is correct. This is really due to the fact that adding and subtracting is the same, mod 2

[uncut herald]

It’s my first week doing combinatorics lol

I need the slack xD

[brave rock]

I think you'll find it's easier to prove using the language of subsets

but good job

[uncut herald]

I’m really appreciating how elegant that was but how do you ever think of it that fast? Like damn

These combinatorics questions (especially creating bijective proofs) seem so difficult to me compared to things like analysis and linear algebra (and elementary number theory), is that because I haven’t had practice working with sets in this way/seeing similar problems before?

[brave rock]

practice and intuition

Here's a similar problem that might help you see the idea I had here.
Suppose there are 500 people, all with integer ages. Show that no matter what these peoples' ages are, you can always choose a set of these people whose ages sum to a multiple of 500.

Of course, the number 500 doesn't matter. If you like, replace it with n.

This was the exact problem I had in mind when I saw your question.

[uncut herald]

I’m pretty sure I’ve seen a VERY similar problem to this one, so here goes: let the symbol ai indicate the age of the i’th person. Now construct the partial sums of a1 < a1+a2 < … < a1+…+a500. If none of them are a multiple of 500, then each one is a remainder r between 1 and 499 beyond a multiple of 500. Since there are 499 remainders and 500 sums, conclude that two of them must have the same remainder r by pigeonhole. Subtract these two partial sums to get a sum of ages that must then be a multiple of 500 and consists of a submultiset of the 500 ages.

That assumes a minimum age of 1

I think

Actually not necessarily lol, cause 0 is a multiple of 500 so if any are 0 that instantly solves the problem

You could order a1, a2, … weakly from least to greatest and then see that since the same argument applies in fact there is always a multiset of the ages such that you don’t “skip over” any ages that sums to a multiple of n

That is by skip over I mean take a(i) and not a(i-1) or a(i+1) given the selected multiset has more than one element

[true venture]

By proving this can we say given a set of n numbers ranging from 1...(n-1) there will always exist at least one partition of n within the set?

What is the maximum number of partitions that can exist in the set? Does that differ for n?

[uncut herald]

Well technically it would be considered a multi set

[true venture]

also don't think it is true. The set of all values n-1 is not a partition of n.

[uncut herald]

It’s not true

[true venture]

A set containing at least one 1

Lol

[uncut herald]

It would have at least one multiset containing a multiple of n

When summed

[true venture]

Nice

[true venture]

Ah yes, forgot what a set was

[uncut herald]

However if this is the problem you thought of when relating it to my problem, maybe you thought of it differently. ie (2^500 - 1) options excluding the empty set for ages to select and then sum, but only 2^499-1 (2^498+2^497+…+2^0) ways to make a composition of every number less than 500 = number of ways to make a composition of not 0 mod 500?

Which means there must exist selections that have repeat compositions mod 500 - unless there are already 0 mod 500 compositions which makes all of this unnecessary. Hence subtract those repeat compositions by removing the parts that compose the remainder mod 500, which results in only the composition which was a multiple of 500

[uncut herald]

Super rigorous lmao

[young zenith]

Hi, Im not too sure on how to approach this last problem, anyone have any ideas?

[patent jetty]

Looking for someone with decent discrete math knowledge pls dm me

[snow axle]

https://dontasktoask.com

[uncut herald]

You have done the first part yes?

Depending on how you’ve drawn the graph there should be a striking feature

[young zenith]

i guess v1 and v4 are the only ones not in triangles

[uncut herald]

In order to get from one of the triangles to the other, you must cross V1V4

[young zenith]

yes

so there is triangle v1 -> v2->v3

[uncut herald]

V2V5 are in separate triangles

Reduce the question

[young zenith]

then v6->v5->v4 are seperate

[uncut herald]

How many walks are there that traverse V1V4 an even number of times and end up in a separate triangle

[young zenith]

i guess in all of the walks

[uncut herald]

? Describe your logic

[young zenith]

u can't traverse between v2 and v5 without traversing v1 and v4

[uncut herald]

That’s correct

Find a path between v2 and v5 of any length that crosses V1V4 twice

Then tell me the path

There’s an interesting feature about all such paths

[young zenith]

idk u can't cross v1 and v4 twice without getting to v5

[uncut herald]

Can you correct that statement please

Okay

Point being, if you cross V1V4 an odd number of times in a walk

You end up in the other triangle

If you cross an even number of times, you end in the same triangle

How does that help us with the question

[young zenith]

uh.. here u dont end up in the other triangle but u end up in the one u started in?

[uncut herald]

So the question wants you to go from V2 to V5, so traverse triangles. It asks you to do this in a way you cross V1V4 an even number of times

We know you cannot traverse triangles if you cross V1V4 an even number of times

So how many walks are ther

[young zenith]

0

[uncut herald]

There you go

[young zenith]

damn ok, ty

u explained it so well

[uncut herald]

Similarly if it asks you to go from any vertex in one triangle to any vertex in the same triangle but cross V1V4 an odd number, it can’t be done

[young zenith]

yep

thanks so much

[outer bridge]

in group theory is monoid always closed under a binary operation?

[brave rock]

in group theory we don't typically think about monoids lol

But yes, a monoid is most certainly closed under its defining binary operation.

Ask about abstract algebra in #groups-rings-fields

[umbral blade]

In this scenario am I allowed to check the truth values of (p ? q) ? r and p ? (q ? r) to determine if its is associative?

[brave rock]

Of course

Why would be there a rule against that?

There might be some clever way to avoid doing that work, but that doesn't mean the long way is disallowed

If you'd like to look for a clever way, here's a hint: can you write p ? q in terms of operations you already know? Maybe look carefully at the table and see if you can describe its behaviour in words

[umbral blade]

is that the expected to way to check for associativity via truth tables?

[brave rock]

There is no one expected way

For what it's worth, every truth table like this can be described in a fairly nice way, so if you like you can simply describe it in a convenient way and look for a proof or counterexample from that alone

If you wanted to, you could also just look at every case.

Neither of these methods are 'expected' by default.

You are allowed to be creative in mathematics!

[umbral blade]

Got it. Also I am wondering if this logic makes sense

If i want to check for commutativity for p ? q by creating truth values for q ? p

since we know when p = T and q = F then p ? q = T

[brave rock]

So you could just say that T ? F = T

[umbral blade]

then q ? p would = F because looking at the truth table when F is on the left side and T is on the right side it = F ?

[brave rock]

Yes, and what do you infer from this?

[umbral blade]

Well if I do it for all truth values I determine that its is not commutative?

[brave rock]

You have already determined it is not commutative

[umbral blade]

I see

because i had to switch the orders

[brave rock]

it doesn't matter what else is there; if there is even one case in which p ? q is not q ? p, then it is not commutative

Conversely if you want to show it is commutative you must cover all cases.

As it happens, showing T ? F = F ? T is sufficient. I will leave you to think about why.

In this case, you have shown that ? is not commutative.