discrete-math

[weary tiger]

using combinatorial arguments

[obtuse lance]

I just mean it has an alternate proof but uses other tricks with finite differences

[weary tiger]

ah

how do i do the alternate proof?

induction?

[obtuse lance]

nah

[weary tiger]

algebra?

[obtuse lance]

so you can represent $$f(x)=\sum_{n\ge 0} (\Delta^n f)(0) \binom{x}{n}$$ which has $(\Delta^n f)(0)$ as the nth finite differences of f evaluated at 0. Then $$\sum_{k=0}^{x-1}f(k) = \sum_{n\ge 0} (\Delta^n f)(0) \binom{x}{n+1}$$

[vital dew]

Merosity

[weary tiger]

oh

thats complicated

[obtuse lance]

for your example, $f(x)=x^2$ just has finite differences evaluated at 0 as just 0, 1, 2 so $x^2 = \binom{x}{1} + 2\binom{x}{2}$ and then the sum $$\sum_{k=0}^{x-1} f(k) = \binom{x}{2} +2\binom{x}{3}$$

[vital dew]

Merosity

[weary tiger]

ok i see

so x would be n+1

[obtuse lance]

yep

[weary tiger]

hmm

and where do u get this function i do not understand

[obtuse lance]

point is summing over x choose n just turns it into x choose n+1, and getting coefficients in this basis is easy just taking finite differences and evaluating at 0

I think they call it a Newton interpolating sum or something like that

[weary tiger]

ah

is there another way?

because this way is hard to explain for me

[obtuse lance]

sure whatever you did probably

[weary tiger]

induction?

[weary tiger]

yes but i need another method

i need to show the LHS

i showed the RHS

[vale cairn]

Cut up $T$ into the sets $T_k = {(x,y, k) | x, y < k}

[vital dew]

Elliptic Potato
Compile Error! Click the reaction for more information.
(You may edit your message to recompile.)

[shell yew]

discrete calculus for the win

[weary tiger]

what do u mean?

[shell yew]

I have a question
if we take 4n vertices and label them 0 to 4n-1 (+ here will technically be modular addition)
and for every 1<=m<=2n and every 0<=a<=2n-1 join (2a, 2a + m)
what is the resulting self-complementary graph called?

[brave rock]

I'm not aware of any name for this but this is much easier to describe group-theoretically

You are looking at the integers mod 4n, which we write Z_4n

There is a subgroup of this, namely the doubles mod 4n, written 2Z_4n.

Now your graph has a line between (x, y) if and only if there is some element k in 2Z_4n such that x = y + k

Well in any case I'm not aware of any name for this except "the graph that nidlatam came up with." Not everything has some special name in mathematics.

[brave rock]

In other words, this relates elements that have the same parity. They are connected if both even or both odd.

Well, unfortunately I've misinterpreted your definition and this is incorrect. I'll maybe give it some thought again later.

[weary tiger]

I dont know where to start

how do i do this

i dont know how to use the bijective principle

i know what it is but do not know how to use it

a function is bijective if it is both surjective and injective

I need to establish that a mapping from $\mathcal{A} \to \mathcal{B}$ is injective (every B has exactly one A) and that it is surjective (every B has some A)

[vital dew]

Derivative

[stray reef]

before you can establish that for any kind of mapping

you need to actually have a mapping to do that with

[weary tiger]

yes can i try a test case?

Like choose X = {1,2,3}

[stray reef]

you can try making one for small values of n

[weary tiger]

yes

[stray reef]

but for the proof you will have to make something that works in the general case

[weary tiger]

yes thats the hard part

thats what I have been struggling with

[weary tiger]

well i could say

half will have n

half will not

so then, if we establish a mapping it is obviously bijective

[stray reef]

yes but that rephrase won't help you

[weary tiger]

how come?

[stray reef]

it's just "if we manage to do the problem then we do the problem"

[weary tiger]

ok i see

[stray reef]

ok so

let's say n=3

[weary tiger]

yes

[stray reef]

do you have a piece of paper on you

[weary tiger]

yes

im doing it on piece of paper rn

[stray reef]

write out all elements of $\mathcal{A}$ and $\mathcal{B}$ in two columns side by side

[vital dew]

|Ann⟩

[weary tiger]

yes

[stray reef]

and send me a pic

[weary tiger]

ok

so, yes this is bijective.

now we need to generalize it

[coral parcel]

{Ø} is not in A, but Ø is.

[weary tiger]

is there a difference?

[coral parcel]

Yes, they are different sets.
{Ø} is a set with a single element (and that element is the empty set).
Ø is a set that has no elements.

[weary tiger]

ah ok

[stray reef]

also there's a more sensible way to match them up

also uh

whitespace

[weary tiger]

yes sorry

[stray reef]

consider this

[weary tiger]

yes

so what could be the better way?

length is not good

[stray reef]

i have already told you

look at this picture

i rearranged yours a bit

so that the way that these sets are mapped to one another is actually better & generalizable

[weary tiger]

oh shit i didnt even realize

so the empty set maps to the set with only the n element

[stray reef]

btw you're gonna need to find a way to tell apart $A$ and $\mathcal{A}$ in handwriting if you wanna stick to the problem's notation

[vital dew]

|Ann⟩

[weary tiger]

yes i am doing it on latex

[stray reef]

k

can you write down the general rule suggested by what i showed?

and not just what ∅ gets mapped to?

[weary tiger]

{1,2...n-1} gets mapped to {1,2,....n}

[stray reef]

also "the set with only the n element" can be written in 3 characters

{n}

again

GENERAL

[weary tiger]

oh

i thought that was general

lol sorry

[stray reef]

it is as if i was asking you for a function's formula and you kept telling me shit like f(0)=1 or f(420)=69

you have so far only told me the value of your function at two possible inputs

[weary tiger]

haha yes my bad

[stray reef]

if you dont know how to write down a formula

[weary tiger]

yeah thats the problem

[stray reef]

then come up with a verbal description for what my mapping is doing

there does exist one

[weary tiger]

so every mapping has one less element than the other.

for example in {1,2} mapped to {1,2,3}, {1,2} has one less element

[stray reef]

wording

wording

and also that is not a complete description and you are failing to see the forest for the trees

[weary tiger]

each mapping has one set that does not have n, and the other does have n.

[stray reef]

you are kind of getting there but you are overcomplicating it still

it is just $A \mapsto A \cup {n}$, that's it.

[vital dew]

|Ann⟩

[stray reef]

and the inverse is $B \mapsto B \setminus {n}$.

[vital dew]

|Ann⟩

[weary tiger]

why the same B?

isnt it A to B

[stray reef]

i said the inverse

the inverse would go from $\mathcal{B}$ to $\mathcal{A}$...

[vital dew]

|Ann⟩

[weary tiger]

oh ok

so A maps to A U {n}

so thats the general sense?

so we have proved it?

i dont understand this notation

$A \mapsto A$

[stray reef]

because you are misreading it

[vital dew]

Derivative

[stray reef]

so let me write it down more fully

[weary tiger]

oh, i am sorry

i did not enounter this notation until today

sorry for my incompetence

[stray reef]

you define a map $\gamma: \mathcal{A} \to \mathcal{B}$ by $\gamma(A) = A \cup {n}$

[vital dew]

|Ann⟩

[weary tiger]

ohhhhhh

now i understand

[stray reef]

its inverse $\gamma^{-1} : \mathcal{B} \to \mathcal{A}$ will then be $\gamma^{-1}(B) = B \setminus {n}$

[vital dew]

|Ann⟩

[weary tiger]

f(A) = A with n

yessss

thank you!!!!!

i understand now 🥹

[vivid osprey]

Is the set $A={1,2,3,4,5,6}^\mathbb{N}$ uncountable? I know $B={1,2}^\mathbb{N}$ is uncountable, and it looks like $B\subset A$, so it must be uncountable too. Is this reasoning correct?

[vital dew]

Philip

[brave rock]

Yes

You can also show A is uncountable by a standard diagonalisation argument

[vivid osprey]

ah ok, cool, thanks

[runic sinew]

Who can help me

It is with boolean algebra

[coral parcel]

!da2a

[lofty cloud]

No need to ask “Can I ask…?” or “Does anyone know about…?”—it’s faster for everyone if you just ask your question! See https://dontasktoask.com/

[runic sinew]

It's an exam about boolean algebra

[twilit sundial]

!da2a

[lofty cloud]

No need to ask “Can I ask…?” or “Does anyone know about…?”—it’s faster for everyone if you just ask your question! See https://dontasktoask.com/

[pseudo star]

Is anyone familiar with probability

Im having a problem

In a question

A theif is about to rob a locker containing 3 rings with 6 digits on each ring probability of him being unsuccessful

[weary tiger]

what have you tried

[cursive nymph]

guys, can someone explain it to me: when we run RSA we need very big prime numbers

but as it turned out, in practice, implementations use primality tests that do not guarantee that the number is prime with probability 100%

and so how does RSA handles those cases?

/not studying cryptography systematically; just a shower thought I had/

[cursive nymph]

||99.9999999999999999% if he has a disc grinder ||

otherwise, I mean, c'mon, he doesn't have to run away after the first attempt: he can just bruteforce all of them

[cursive nymph]

whut

but isn't the point to find large big primes

[agile magnet]

https://crypto.stackexchange.com/questions/25878/rsa-with-probable-primes

basically the answer is that there are easy checks you can run after generating the probabalistic primes

to verify that they will encrypt and decrypt properly

[coral parcel]

Large primes are somewhat harder to find when generating keys, but much much harder to find for an attacker seeking to break the key.

[agile magnet]

they don't just generate the primes and go off ot the races

[agile magnet]

they aren't asking about attacks, just functionality

because forget security, RSA fails very quickly from a correctness standpoint if p, q aren't prime

[coral parcel]

They'll only pass a probabilistic primality test if they do work in RSA for "most" cleartexts (in the sense of decryption producing the original input that was encrypted),

[agile magnet]

they'll fail other tests though such as properly computing the Euler phi function

or the totient

but would they always encrypt decrypt properly?

[coral parcel]

I'm assuming that in practice a prime that passes the standard tests, they'll be something like Carmichael numbers (or nearly so) that still work in RSA.

I might be wrong, though.

[agile magnet]

yea Carmichael numbers are the numbers that I know that'll pass

I'm sure there are others

but those are exceedingly rare

I wonder if I can turn this into a CTF chal hmmmm

[coral parcel]

False passes in a probablisitc primality test with a reasonable number of rounds are also exceedingly rare.

[agile magnet]

yea

true

[coral parcel]

I'm mostly arguing heuristically here: If it was a halfway realistic chance that a composite would pass the primality test and go on to make a completely nonfunctional RSA key, the people developing such tests would simply have added "generate an RSA key with this number and try encrypting-decrypting a handful of random messages" as a final pass of the test.

[agile magnet]

If you're interested in this stuff

the only dedicated cryptography discord that I know of is the one run by [Cryptohack]

They're quite nice people

and a number of people in that server do cryptography research / work in cryptography so they'd be knowledgable about this stuff

and the goal of Cryptohack is to teach people cryptography

so they're welcoming of these questions

[cursive nymph]

oh, thank ya guys!

I will read the rest of the discussion tomorrow when I wakeup

[harsh oracle]

a shopkeeper sold an article for 3750 rs. if he had charged 24% less, even then he would have earned a profit of 14%. what is the original cost of the article?
a. 2850
b. 2717
c.3289
d.2500
choose the correct option and give me the steps

[stray reef]

!noans

[lofty cloud]

The purpose of this server is to help you learn, not to hand out answers. Do not ask someone to give you the answer directly.

[stray reef]

we won't just give you the answer

@harsh oracle did you want someone to do this for you? or did you want to learn how to do this yourself?

[harsh oracle]

learn and do it myself

[stray reef]

ok in that case

have you attempted the problem yourself?

[harsh oracle]

yap

[stray reef]

ok show your work and answer

even if you got the wrong answer it will be useful to know where you went wrong

could be a stupid arithmetic error, could be something bigger and more conceptual, etc...

[harsh oracle]

If the shopkeeper had charged 24% less, the selling price would be
100
%
−
24
%

76
%
100%−24%=76% of the original selling price.
So, the selling price with a 24% discount would be
0.76
𝑥
0.76x.

The problem states that even after selling at a 24% discount, the shopkeeper would still earn a profit of 14%. This means that the selling price is 114% of the cost price with the 24% discount.
So,
0.76
𝑥

114
%
0.76x=114% of the original cost price.

Let's set up the equation:
0.76
𝑥

114
%
×
𝑥
0.76x=114%×x

Solve for
𝑥
x:
0.76
𝑥

1.14
𝑥
0.76x=1.14x
0.76
𝑥
−
1.14
𝑥

0
0.76x−1.14x=0
−
0.38
𝑥

0
−0.38x=0
𝑥

0
x=0

Cost Price=
1+Profit Percentage
Selling Price
​

Cost Price

3750
1
+
0.14
Cost Price=
1+0.14
3750
​

Cost Price

3750
1.14
Cost Price=
1.14
3750
​

Cost Price
≈
3289.47
(rounded to 2 decimal places)
Cost Price≈3289.47 (rounded to 2 decimal places)

correct answer is 2500

[stray reef]

where did you copy and paste this from?

also your copypaste screwed up bad

[harsh oracle]

yeah

from message

typing is okay though

[stray reef]

...take a screenshot?

it's impossible to follow right now

[harsh oracle]

wait

1. If the shopkeeper had charged 24% less, the selling price would be 100%−24%=76%100%−24%=76% of the original selling price. So, the selling price with a 24% discount would be 0.76𝑥0.76x.
2. The problem states that even after selling at a 24% discount, the shopkeeper would still earn a profit of 14%. This means that the selling price is 114% of the cost price with the 24% discount. So, 0.76𝑥=114%0.76x=114% of the original cost price.
3. Let's set up the equation: 0.76𝑥=114%×𝑥0.76x=114%×x
4. Solve for 𝑥x: 0.76𝑥=1.14𝑥0.76x=1.14x 0.76𝑥−1.14𝑥=00.76x−1.14x=0 −0.38𝑥=0−0.38x=0 𝑥=0x=0
   This equation indicates that 𝑥x, the original cost price, is 0. However, this doesn't make sense. Let's reassess the problem.
   If the shopkeeper earned a profit of 14% on the article sold for Rs. 3750, then the cost price would be:
   Cost Price=Selling Price1+Profit PercentageCost Price=1+Profit PercentageSelling Price Cost Price=37501+0.14Cost Price=1+0.143750 Cost Price=37501.14Cost Price=1.143750 Cost Price≈3289.47 (rounded to 2 decimal places)Cost Price≈3289.47 (rounded to 2 decimal places)

what about now

[stray reef]

no, still bad.

i said to take a screenshot

please give me a screenshot

[harsh oracle]

im on pc thou

wait

there you go

[stray reef]

this is chatGPT.

!nogpt

[lofty cloud]

Please do not trust ChatGPT or similar AI tools for mathematical tasks, as they often generate output which "sounds correct" but has numerous factual or logical errors. Use of these AI tools to answer other people's help questions is strictly against server rules (see #rules).

[harsh oracle]

how do you know

[stray reef]

i've used chatGPT before, i know exactly what its output sounds like. + the font is the same as on its website.

this is not your work.

this is chatGPT's work, and it has screwed things up bad.

bad enough that we should start from scratch.

[harsh oracle]

well it din give me right answer

so if i change the font then its okay>

[stray reef]

do you agree to start from scratch and actually solve this problem properly?

[harsh oracle]

yeah

[stray reef]

ok, so let's do that.

[harsh oracle]

yeah

[stray reef]

there are three prices that we care about:

• sale price: the price at which the merchant actually sold the item. the problem gives us the sale price as 3750 INR.
• discounted price: the price after applying a 24% discount on the SP.
• cost price: the price that the merchant paid to get the item. percentage profit is based on this price.

do you understand this so far? don't try to do any computations yet.

only confirm or deny that you understand the stuff i wrote here.

[harsh oracle]

okay

i understand

[stray reef]

ok

so we are told this:

1. DP is equal to SP discounted bc 24%
2. if sold at DP, the merchant's percentage profit will be 14%.

given we know SP = 3750 INR, calculate the DP.

[harsh oracle]

okay set

[stray reef]

... obviously i also want you to tell me what you got.

so that i can tell if you are making a mistake or not.

[harsh oracle]

how to calculate dp

discounted bc 24% ?

mathify that?

[stray reef]

"mathify" is an interesting way to put it

[harsh oracle]

huh

[stray reef]

do you know how to apply a discount to a price? Y/N

[harsh oracle]

n

N

[stray reef]

do you know how to calculate percentage decrease?

Y/N

[harsh oracle]

N

[stray reef]

do you know how percentages work

[harsh oracle]

yup

[stray reef]

Y/N

ok

so

[harsh oracle]

100%-24%

[stray reef]

to apply a discount to a price means to decrease the price by that percentage of itself

[harsh oracle]

would be 76%

[stray reef]

ok, so 76% of SP is?

[harsh oracle]

.76 times 3750?

[stray reef]

calculate it

[harsh oracle]

2850

[stray reef]

ok

good

so the DP is 2850 INR.

[harsh oracle]

now the cost

frm DP?

[stray reef]

we know that the profit from selling at DP is equal to 14% of CP.

[harsh oracle]

ya

[stray reef]

therefore, DP = CP + 0.14*CP

[harsh oracle]

dp\1.14= cp

done

[stray reef]

/ not \

[harsh oracle]

|thanks>

2850/1.14=2500

which is the answe

[stray reef]

yes

you should NEVER use chatgpt to do your math homework.

never ever. zero exception.

[harsh oracle]

yaa i got that from this

[stray reef]

and if you try to pass off chatGPT's output as your own work, then people will know.

[harsh oracle]

so dp = cp + profit?

[stray reef]

profit is income minus expenses.

[harsh oracle]

since profit = .14*cp

[harsh oracle]

this

[stray reef]

if you try to memorize "dp=cp+profit" you will have a bad time.

[harsh oracle]

yeah

so another question?

[stray reef]

...

<@&268886789983436800> troll suspected

[harsh oracle]

not a troll

[stray reef]

well how are you jumping from basic finance to quantum mechanics

[harsh oracle]

i cant chatgpt this

[stray reef]

also neither of those two would fit in this channel anyway

[harsh oracle]

random intellectual Fluctuation

discrete math right

dont ban me

[round coral]

Lmaoooo “random intellectual fluctuation”

I’m still laughing

[hard stone]

This seems well above your current level, you should try to learn more math before tackling something like this

[vale cairn]

What's funny about this is like

I took a course in QM and idk what clebsch Gordon coefficients are

[fresh hull]

Q. During a 30-day period, a student studies at least one hour a day but no more than 4 hours a day, accumulating a total of 70 hours of study. Show that there must be a consecutive period of days during which the student studies exactly 10 hours.

I had this problem which I kinda solved, im having trouble with this one part

1. I declared a_i to be the number of hours studied on the ith day, so 1 <= ai <= 4
2. I declared b_i to be the number of hours studied from the first day to the ith day, so b_i = a1+a2+... a_i
3. I declared c_i = b_i%10. Since there are 30 values for b_i and only 10 for c_i, two must be congruent to each other
4. Let b_i = b_j (mod 10). Hence b_j - b_i = 10k [the difference between b_j and b_i denotes the number of hours studied between days i and j]

Now, the solution (chatgpt) told me to just assume k = 1

and show that bj - bi = 10

[stray reef]

bruh the cursive

[fresh hull]

I apologise

i could type out the problem if you need

[fossil mural]

During a 30-day period, a student studies at least one hour a day but no more than 4 hours a day, accumulating a total of 70 hours of study. Show that there must be a consecutive period of days during which the student studies exactly 10 hours.

[stray reef]

also

!nogpt

[lofty cloud]

Please do not trust ChatGPT or similar AI tools for mathematical tasks, as they often generate output which "sounds correct" but has numerous factual or logical errors. Use of these AI tools to answer other people's help questions is strictly against server rules (see #rules).

[stray reef]

also imo there's a better way to do this

[fresh hull]

but i used it for myself..

it worked so far i just need the k=1 case

[fossil mural]

chatgpt will often generate stuff that looks vaguely reasonable but is actually completely wrong

[fresh hull]

yeah makes sense

[fossil mural]

anyway yeah i'm not convinced this works
if you had 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 3, 3, 0, 0, 0, 0, 0

this contains the subsequence 3, 3, 3, 2, 3, 3, 3 (several times actually) which sums to 20

[fresh hull]

it cant be 0

[fossil mural]

but no subsequence sums to 10

[fresh hull]

minimum 1 hour

[fossil mural]

i know

[fresh hull]

or are those the remainders?

[fossil mural]

but the fact that this near-counterexample exists means a solution must actually use the fact that they can't have studied for 0 hours on any day

[fresh hull]

hmm

[fossil mural]

with the approach of "well the mod 10 values repeat" it's not obvious how it would work on any example that follows the rules but fail in this case

[stray reef]

may i suggest an alternative solution which goes in a completely different direction

[fresh hull]

sure

[stray reef]

let a_i be the total study time (in hours) from day 1 to day i inclusive, and let b_i = a_i + 10.
we aim to show that the list (a_1, a_2, ..., a_30, b_1, b_2, ..., b_30) has to contain at least one pair of duplicate values

[fresh hull]

this is what i tried before

But i got the range of the list as (1,80)

with 60 elements in it

[stray reef]

right yeah

so plain pigeonhole does not quite work

[fresh hull]

yeah

[fresh hull]

@ me if yall get anything

[coral parcel]

Study 2 hours 20 minutes each day.

[hard citrus]

what's the recommended book for discrete math? on undergrad level for stem? talking about the basics like sets, relations, functions, combinatorics, probabilities, graphs and trees and whatever else.

[coral parcel]

There's no such thing as a "the" recommended book; it varies too much which topic a given university's course with that name covers.

[hard citrus]

I'm sure there are known better books than others, and it's not for university per say just to solidify my understanding in few of these topics and learn from scratch others (like trees or graphs)

[elder berry]

I'm wondering where the origin of the name many-one reduction comes from for formal languages? I understand the many-one part, but how is it a reduction. When creating an analogue to NP problems and reducing one decision problem to another, the A reduces to B means that B is at least as hard as A, so it ain't reducin' anything you just convolute/complicate it xd

this is very much a real question, sorry if it seems as a troll

[coral parcel]

The meaning at the core is that to "reduce" a particular concrete problem is to convert it to another problem that is in some snse easier to solve -- e.g. if we want to compute 3·236 we can transform that to 236+236+236, and then we've "reduced" a multiplication problem to an addition problem.
Next step, we can speak of "reducing" a problem type to a different problem type that we already have a way to solve. That means giving an algorithm for transforming each instance of the problem type to an instance of the problem type we know to solve.
The final abstraction is now to use "reduction" to mean any algoritms that transforms problems of one type into problems of another type that have the same answer -- now without any thought of whether one is easier (or even possible) to solve than the other.

[elder berry]

Thanks for this! Makes a lot of sense

[wet flame]

where did the y go when they conclude xz belongs to L_pali

[wet flame]

i guess the only way this makes sense is if they count 0 as a natural number

[agile magnet]

What does the pumping lemma state?

Can you write it out here

[opal spire]

y^n = 0

[proven ibex]

im struggling to find my mistake in this question

so i need to find the reverse of this DFA as a DFA

So I get my reversed NFA here

And my tables

but im told by the question hint that there should be 6 states including the dead state

but im only getting 5

and i can't figure out where i've gone wrong

[coral parcel]

Looks right to me. There might be an error in the hint?

[proven ibex]

😭

[harsh oracle]

Hello

[wispy summit]

Any hints on this? I know that $|A| + |B| = \max(|A|,|B|)$ etc. but this exercise just wants you to do it using elementary means, and I'm weirdly stuck on it

[vital dew]

Yuese

[stray reef]

are we allowed to declare that A has a countable subset A'

[fossil mural]

given that that's basically just what proposition 1.2.2 says, yes

[stray reef]

yeah but maybe there's some red-tape reason that i am failing to see here which would prevent us from equating "exists injection N -> A" and "exists countable subset of A"

[coral parcel]

Yes. In particular, you can say that A is the disjoint union A1 cup A2 where A1 is countably infinite.

[weary tiger]

Are there any tutors or someone willing to teach me discreet for my next semester

[twilit sundial]

this is not the place to ask

[coral parcel]

That is a rather big ask for a chat server. If you're either self-learning or someone elsewhere is teaching you, you can often get good advice here on particular points that confuse you. But actually teaching (as in take charge of topic selection, pacing, and initial presentation), that is a lot of real work which I don't think anyone competent to do it would commit to unpaid.
(And the server deliberately does not facilitate contact about paid tutoring).

[weary tiger]

Mk thanks

[vivid osprey]

In probability, when we want to obtain the marginal distribution of the joint distribution, there is this identity (in the discrete case) $$\left{X=x\right}=\bigcup _y\left{X=x{,}Y=y\right}.$$Suppose the union consists only of two sets, with points $y_1$ and $y_2$. Then, if we write ${X=x}$ as statement $p$ and ${Y=y_1}$ as $q$, we can write the RHS of the above equation as $$(p\land q)\lor (p\land \neg q),$$and this is equivalent with $p$, so it proves the set identity. How does one extend this to more points than two?

[vital dew]

Philip

[wispy summit]

Yes!

[stray reef]

in that case:

• assume wlog that A and B are disjoint
• pick a countable subset A' of A
• biject A' cup B with A'

[vivid osprey]

what I'm after is creating an exclusive (I don't know if this the right word) set of statements {a,b,c,...}, where if a is true, all the other statements are false. Or if b is true, then all the other statements are false.

[wispy summit]

Oh, shoot. Of course. Thanks!

[proven ibex]

i think you just have to nest them

let Y be able to attain y₁, y₂, y₃, then the statement q is {Y = y₁ or y₂}, and the statement r is {Y = y₁}, etc

Y = y₁ would be q ∧ r
Y = y₂ would be q ∧ ¬r
Y = y₃ would be ¬q

[vivid osprey]

I see, thanks 👍

[wide sentinel]

How does one get the intuition of induction man 😩

the part right after you replace the n with k

[stray reef]

"replace the n with k" does not hold as much significance as you think it does

and the only real way to develop intuition for induction proofs is to just... do induction proofs, i guess

[proven ibex]

the whole idea is like dominos

you show that the first one can be knocked down

then if any arbitrary one gets knocked down, it knocks the next one

then this pretty much means knocking the first knocks the 2nd then the 3rd then...

[wide sentinel]

Actually now that i think about it, i mean the part right after you replace k with k + 1

[wide sentinel]

i get that part, if you can step once you can step to the next one

its the part right after you replace your k with k + 1

[proven ibex]

that step there is trying to show that if the statement holds for n = k, then it holds for n = k+1

[wide sentinel]

yeah, but its when you have to add the other random stuff

for example

Prove that n! > 2^n for each integer n greater than or equal to 4

the part after replacing n, with k, then k with k+1 is weird because then you have to do stuff like (k + 1) * k! >(k+1) * 2^k > 2x2^k = 2^(k+1)

[stray reef]

right so first off dont use the letter x as a multiplication

second,

IN GENERAL for an induction proof, you need to find a link between the stmt for k+1 and the one for k

[proven ibex]

try to prove by induction that n < 5 for all n >= 0

you will quickly see that it doesn't work

[stray reef]

and your scratch work could look like

for example starting from k! > 2^k

multiplying both sides by 2 to get 2 * k! > 2 * 2^k = 2^(k+1)

and then looking at what happens between 2 * k! and (k+1)! a.k.a. k!

and then you see that you can attach that to the inequality chain

like yeah sometimes the final proof obscures the details of how it could be arrived at

[wide sentinel]

Yeah I think that's what I meant to say, that's the hard part, I can spot the k statement in the k + 1 statement sometimes though, as in when you pull k out of k + 1

[stray reef]

but it just be like that

[wide sentinel]

Oh so you equal the k statement and the k + 1 statement

[stray reef]

no

youre kinda not seeing the forest for the trees rn

what you are complaining about is that you dont know of any panacea with which the statements for k and k+1 could always be tied together

[wide sentinel]

yeah..

[stray reef]

such a panacea does not exist

and cannot ever exist

[proven ibex]

well sometimes induction is hard

[wide sentinel]

i kind of udnerstand this one

he's adding 2k+3 to (k+1)^2 because we know thats what the sum up to k equals to

I guess I just struggle to think in a general sort of, designing a key that fits every lock sort of way.

[stray reef]

there is no such key

there isnt and there never was and there never will be such a key

you are once again looking for a panacea

such a panacea does not exist

[odd heart]

Bleak but true

[wide sentinel]

No like, finding the general answer to a question u know ? Kind of like, whats the formula for a growing truth table

2^n

if thats also what ur referring to then i guess it doesnt exist...

[tame bronze]

Let $T$ be a subset of the integers from $1$ to $209$, where $|T| = 11$. Is it possible for all non-empty subsets of $T$ to have distinct sums of their elements?

[vital dew]

exams (back may 30)

[tame bronze]

This is pigeonhole right? Not sure how to go about solving this one

[mental mirage]

,w 2^(11)

[vital dew]

Results provided by WolframAlpha

Click here to refine your query online
Upgrade to WolframAlpha Pro!

Requested by theguy4410

[mental mirage]

,w 209*105

[vital dew]

Results provided by WolframAlpha

Click here to refine your query online
Upgrade to WolframAlpha Pro!

Requested by theguy4410

[mental mirage]

ah wait this dosent work lemme think

[quiet eagle]

In linear programming why are basic solutions, that are not only non-zero called "degenerate"? What's so wrong with them, or why do you even differentiate between degenerate and non-degenerate?

[silver ermine]

can a word/string includes whitespace by the definition in DS?

[stray reef]

what's DS?

[silver ermine]

channel name

sorry

in discrete math*

[stray reef]

did you see a problem in which this matters?

like, a problem which would be meaningfully changed by "strings are allowed to contain whitespace" vs. "strings are not allowed to contain whitespace"

[silver ermine]

honestly prob no

[brave rock]

If you are referring to the definition of word that I am used to, you will have been given an alphabet that defines the set of words you are looking at. Whitespace is allowed if and only if whitespace is in the alphabet.

[stray reef]

^

[silver ermine]

thats the one I get as well

[brave rock]

Without more context I cannot be certain if you really are referring to the same thing.

[silver ermine]

solved

I kinda skip discrete math last semester now facing a bunch of algorithm shxt using those terms

[stray reef]

you can curse here

[silver ermine]

I should have read more

[brave rock]

Oooh definitions are important as fuck 👻

[silver ermine]

I thought algorithm would be like, write a function that solves a problem on your computer then you get full points

its not

its not leetcode damit

[agile magnet]

But understanding how to analysis those algos + techniques to come up with better ones is the fun stuff!

Programming is boring

[silver ermine]

ye but the tough point is to understand the language

the concept is not necessarily tough and mostly fun

[agile magnet]

language as in programming language?

[silver ermine]

language in discrete math

[agile magnet]

Programming language is the easy part, assuming you already know the basics of programming

Oh yea

[silver ermine]

sometimes a jump up notation kills me

[agile magnet]

Yea that can be a lot of notation at first but once you learn it, the notation is useful

[silver ermine]

if its some kinda python or cpp syntax i can look up easily

but in discrete its kidna hardcore and rely on the prof

and i dont dare to ask him

since i failed last semester 🤣

[agile magnet]

ask bruh (unless he's an asshole or something)

That's what office hours are there for

[silver ermine]

ill try

is the 1^K here also any generally used notation?

I can infer it means a series of continuous 1s tho

[brave rock]

Yes

[silver ermine]

k

[agile magnet]

in fact it means exactly k 1's in a row

so 1^2 = 11

[prisma jolt]

is \ still used to denote a complement of a set and another?

[twilit sundial]

?

$\setminus$ denotes set difference

[vital dew]

elrichardo1337

[brave rock]

$A \setminus B = {a \in A\mid a \notin B}.$

[vital dew]

Boytjie

[tribal rune]

guys can someone prove that at least 1000000 africans share a birthday (there are 1.216B)

[halcyon dock]

Hmm I’ll think about it

Would anyone like to do a study group for graph theory or combinatorics?

[agile magnet]

hint: pigeonhole principle

[halcyon dock]

I dare you to do it

[halcyon dock]

Is it that simple?

[agile magnet]

yes

[halcyon dock]

Do it then

If you want to lol

It reminds me of the birthday problem

[agile magnet]

there are 365 days in a year
so if each of the 365 days had < 1 million people with a birthday on that day, there would be < 365 million African people

hence there must be at least one day with >= 1 million african people having that birthday

the math behind the birthday problem would get you the same answer with more work

[halcyon dock]

Lol

Nicee

[tribal rune]

yup

got it from a book

and modified it a bit

[tribal rune]

tho it used 366 cuz theres a small possibility

[tribal rune]

i can read the proofs and understand the theorems but i cant solve a problem for the life of me unless its easy so sure

[halcyon dock]

Alright bet

[mental mirage]

[wide sentinel]

Would, "pink icing with green sprinkles" suffice as an answer ?

[coral parcel]

If all the cupcakes have both icing and sprinkles, then the last formula would also be true, so that's not an example.

[odd heart]

Indeed, it describes pink icing with green sprinkles.

Now I'm hungry

[shell yew]

wait why are these equivalent?

(I'm asking about the b not relatively prime to n)

[brave rock]

The proof that is cited is a bit complicated.

It works by going through the criterion by Korselt listed in the article.

[coral parcel]

You've cropped off the qualification that says they're only equivalent when b is coprime to n.

[brave rock]

I found the pdf online so you can just look up the proof

[coral parcel]

However, when they are coprime, b will have an inverse modulo n, so just multiply both sides of b^n == b by that.

Hmm, the other direction actually seems trickier, though.

[shell yew]

(sorry)

[tribal rune]

divide by b

[shell yew]

I'm sorry, I forgot to include the segment saying that the gcd of b and n is 1 in the picture (I'm asking about the converse for b that are not coprime to n)

[quiet eagle]

still wondering

[coral parcel]

You may have better chances of finding someone who can answer in #optimization.

[prime flicker]

hello, quick question, does my answer for 1 and 3 seem correct?

[quiet eagle]

thank you

[shell yew]

are preorders equivalent to partial orders under xRy and yRx equivalence classes?

and total preorders equivalent to total orders und xRy and yRx equivalence classes?

[brave rock]

Yes, a preorder is just a partial order on a partition

[patent solstice]

Hi all, just a question, does a planar graph need to be connected?

I'm looking at the proof for Euler's formula for planar graphs, and we ended up with a spanning tree which confirms the theory |V|-|E|+|F|=2

[tight hound]

No, for a simple example consider a graph with 2 vertices and no edge between them

It is clearly planar and non-connected

[patent solstice]

Ahh makes sense, so the only condition is for it to have no edges overlapping?

[coral parcel]

Yes, that's the only condition for a planar drawing of a graph.

[patent solstice]

Ahh, makes sense

[coral parcel]

(The graph itself as a mathematical object does not know how you draw it. The relative positions of points and edges is something you decide while drawing, but is not part of the graph).

[patent solstice]

Is there a way to determine the amount of faces a graph have?

[coral parcel]

You can use |V|-|E|+|F|=2 to calculate the number of faces a drawing of the graph will have if such a drawing exists.

Beware that this counts the area outside your drawing as a "face" too.

(And this only works for connected graphs).

[patent solstice]

Wait, I'm confused, does Euler's formula only work when a graph is connected?

The intuitive proof they gave us was that if you narrow a graph down into a spanning tree, then that |V| - |E| + |F| = 2

[coral parcel]

Well, consider the graph with four vertices and two edges not sharing an endpoint. By rights it would have a single "face", but then |V|-|E|+|F| would be 4-2+1 = 3.

[patent solstice]

Hmm, yeah, that makes sense

[north raptor]

How exactly is this deduced?

It's part of a solution, theres no other explanation

[agile magnet]

what is the recurrence

that's an important part of this

[north raptor]

Oh sorry, so its the first equality and every even index a_2k is 0, while we know that a_1 = 1, a_3 = 1/6

This is apart of a solution we get from a differential eq. and this is the only work shown

[agile magnet]

this seems like a step of a proof by induction

but yea proof by induction as far as I can tell

[north raptor]

Hmm, i see. Why would they just do like this in one line? We've never seen this before

[agile magnet]

¯_(ツ)_/¯

depending on how advanced the class is maybe they just expect you to recognize that

like recognize the fact that the term got replaced by a closed form of sorts

which probably happened with a proof by induction

fill in the details yourself

[north raptor]

While we have worked with recurrences, we havent solved them explcility ever, or rather dont know methods for it.

I see

So the problem im facing then is that, i cant just make a conjecture like this in an exam and sure if I knew the closed form i'd show it with induction; but in this case its just a side calculation for the coeff. of a power seriers, which wont look like this all the time.

So is the reasonable conclusion that they spent alot of time just playing around until they saw a pattern?

[coral parcel]

It's not really a big thing to "show with induction".
The recurrence relation in the first line clearly says that when you move to a_{2k+1} you append a factor of 4k²-6k+3 in the numerator and factors of 2k and 2k+1 in the denominator. So the total result is a faction with the product of all the factors in the numerators, and the product of all the factors of the denominators.
In the numerator there's nothing better to do (at this step, at least) than to write down the whole lot as an indexed product, but in the denominator it's easy to see that all the factors you've picked up has one of each number from 1 up to 2k+1 -- and that product has a notation already, namely (2k+1)!

[jade aspen]

Hello, maybe somebody could help me out with relations??

Find it hard to understand them...

[north raptor]

Thank you!

[coral parcel]

(Assuming we have a boundary condition saying a_1 = 1, or we'd need to multiply everything by whatever a_1 was).

[coral parcel]

It will be a lot easier for someone to help you if you actually ask a question about something that confuses you.

[jade aspen]

So, I can't find out when relation is transitive or not

for example here.

[agile magnet]

What's the definition of a transitive relation?

How is the relation defined by the picture?

Can you answer both of those for me?

[silver ermine]

how do we read this sign

[coral parcel]

In this context I think it must stand for "is defined to mean", but that is not really a standard usage of it.

[silver ermine]

does it means some equivalent relation but as a set construction?

I saw usually := means "defined as"

am i get it wrong

[coral parcel]

Yes, that is more common.

There's a whole smorgasbord of symbols that different authors use to mean "is defined as".

[silver ermine]

okay, i find this makes sense as defined as as well

[jade aspen]

(a,b) (b,a) > (a,c)

and from that picture I think you should see

[agile magnet]

What is (a, b)(b, a) and what does > mean?

[jade aspen]

simple pointer

[agile magnet]

I want you to write it out for me

[jade aspen]

ok

[jade aspen]

that one below

[coral parcel]

Note that you can't make that read (a,b) (b,a) > (a,c) even if you delete a lot of symbols.

If you had written (a,b) (b,c) > (a,c) that could be explained as just sloppy writing.

But since you wrote "(a,b) (b,a)" that looks a lot like you need to read the definition closely a few times.

[jade aspen]

How can I explain it...

that is transitive

[coral parcel]

Try writing it out in words -- just showing a picture obscures almost everything about which arrows in it already exist, which ones you want to exist, and so forth.

[agile magnet]

We know what transitive means but what you wrote didn't make it clear that you knew, and knowing the definitions is the first step to writing a proof

[coral parcel]

Which means we cannot be sure you've actually understood those details.

[jade aspen]

About definitions, I want to understand it practically

[agile magnet]

And then this pic, I don't see any arrows for direction so I assume that if two circles are connected then they're related?

[agile magnet]

The definition is quite practical

The definition is all you need, nothing more nothing less

Idk what would be practical if not that

[jade aspen]

How can that be 😄

I understand definitions but I can't explain it in my words.

I want to understand from graphs.

or from sets...

[agile magnet]

This is from sets...

[silver ermine]

also<,= in the most popurlar sense

[coral parcel]

At this level I think we owe the learner to be very clear about the quantification, which is one of the possible stumbling blocks. So I would say:

For all a, b, and c that have a ≤ b and b ≤ c, it also holds that a ≤ c.

Or equivalently:

It is impossible to find any a, b, c such that a ≤ b and b ≤ c but still not a ≤ c.

[jade aspen]

Ok so, I want to show you and example

is this transitive

dont mind the composition

[coral parcel]

Try all combinations of a,b,c and check whether, whenever (a,b) and (b,c) are in your set, you always also have (a,c).

[silver ermine]

i think you need to read about proposition logic so that you have intuition of implies symbol?

[coral parcel]

(Hot take: the usual way texts about propositional logic explain the implication connective is horrible for developing intuition).

[jade aspen]

I get that that relations is transitive

because, it wont create any other elements

[coral parcel]

Good.

[jade aspen]

so is it mean that if relation creates new elements its not transitive

and the one who dont is transitive

[silver ermine]

I think your example might be a bit special?

[silver ermine]

create one

ill exam it

to break it

[jade aspen]

ok, ill try to find something else

[silver ermine]

i can give you one (2,3) to add to S

if so, S is no more transitive

[silver ermine]

false reality and stuff i remembered, but if you forget commen sense for a bit it works ig

[jade aspen]

for example this one

[silver ermine]

is it transitive or not

tell me

[jade aspen]

wait

not transitive

because it creates element (2,1)??

[silver ermine]

how to make it transtitive

ur right its not

[jade aspen]

idk

[silver ermine]

i mean

[jade aspen]

oh

😄

wait

[silver ermine]

if you wanna talk in graph representation

just all graph

otherwise just all set and language

it would be better for others to understand

[jade aspen]

idk how to make is transitive

maybe adding

(2,2)

[silver ermine]

can you try add a element to make S no longer transitive?

forget the graph

[jade aspen]

adding (1,2)

maybe?

[silver ermine]

its already in it?

no?

[jade aspen]

im talking about this one

thats different one

[silver ermine]

can we use a pure language representated example

like dont use graph for this time?

if you have that in your material or textbook or somewhere that a set is said to be transitive

[jade aspen]

I can't do it 😄

with "graphs" that shows relations

its way more easier for me

[silver ermine]

but i dont get this phrase

[jade aspen]

ok, sorry not elements

but

[silver ermine]

can you draw it

[jade aspen]

connection between 2 and 1

[silver ermine]

what is 2

[silver ermine]

yes this is right

[silver ermine]

its transitive now

[jade aspen]

yes

[silver ermine]

i'm not an expert on graph representation tho, need someone else to approve

[jade aspen]

I mean it wasnt before

[silver ermine]

exactly(me think)

[jade aspen]

This one is not transitive

[jade aspen]

but if you add arrow from top vertex to the left one below

[silver ermine]

ye

[jade aspen]

it comes out transitive

[silver ermine]

keep this intuition

it is so simple

as you think now

[jade aspen]

thats what I was asking for

Thank you.

[novel ore]

isn't this only the case if N = b^k - 1? or is it just that it's an upper bound for the growth rate of some algorithm (they haven't mentioned which yet) for a number N written in base b

[fossil mural]

well that's what the ceiling is for

like if we take base 10 for simplicity

log_10(200 + 1) is about 2.303

if you round it up, you get 3, and that is in fact the right answer

in general, for b^n - 1 you get the exact correct answer (n) from the logarithm, and then anything in between takes the same number of digits as the next b^n - 1 (200 and 999 are the same number of digits), so for numbers in between you round up

(then "about log_b N digits" is just an approximation, it's deliberately throwing out a difference of up to 1 because for growth rates of algorithms we don't need that much precision)

[candid lintel]

does anyone know any online course i can take for discrete math

looks fun dont know where to take it though

[silver ermine]

does it mean take the element,which i think is a equivalent class, of quotient set as an unit?

[coral parcel]

I wonder why C++ even cares about that? Something funky about magically autogenerating comparison operators from a single operator< definition?

[coral parcel]

The quotient A/I_< is a set whose elements are the equivalence classes of A, yes. It's saying that the strict weak ordering "becomes" (the dignified term would be "induces") an actual strict total order that can be used to compare two equivalence classes.

[silver ermine]

i dont remember the full context in my lecture, the sign is not even in C++ syntax i guess?

might be talking about integer < but it's already total order idk

[coral parcel]

Those are not quotes from the same source, are they? The typeface is different?

[silver ermine]

they're not, just my random research from stack overflow

[silver ermine]

what does this notation mean?

I know what Z means

[cerulean radish]

Z_l seems to mean integers modulo l

Z in general denotes the set of integers

[silver ermine]

how is it look like as a set representation?

can you write me a few elements of set Z_2

@cerulean radish

[cerulean radish]

Z_2 = {0, 1}

Z_l = {i in Z | 0 <= i <= l-1}

It's just the indices of the elements in an array in this case

[silver ermine]

seems it should be i belongs to Z_l

if so

why it's not written as 0<=i<l if it means the index 🥲

[cerulean radish]

0 <= i < l and 0 <= i <= l-1 are equivalent for integers

I think you asked why they chose to use Z_l; I don't know as well then

[hard spindle]

Heya! Are we able to ask for help in this chat or is it another one?

[limpid coyote]

Yeah, sure. Whats the question?

[hard spindle]

It's to do with Posets, I've been working on some questions for the past few hours and I've kinda hit a wall with some.
I've done a and b just a little stuck with c and d

[silver ermine]

may i ask how is moebius function defined? just curious

google version takes only one parameter

[hard spindle]

It's to do with the chains of length i from a to b within the poset

[silver ermine]

can it be negative

[hard spindle]

Yeah, even length chains are 1, odd are -1

[silver ermine]

ok

[hard spindle]

Can also be zero if number of odd chains = number of even

[silver ermine]

im still a bit confused, can you give me a example such that μ(x,y)!=μ(y,x)? I think it must be some case this holds so that the Q(a) make sense but i cant imagine how is it defined

I was thinking defined as first take the difference of the ranks then apply google moebius function but it feels wrong

[hard spindle]

I did a by proof by contradiction, if u(x,y) =/= 0 then there must be some set of chains that lead from x to y - this means there there will be some integer value of -1 or 1.
Then, if there is a set of chains that lead from x to y, there cannot be any path from y to x (as posets are directed) and therefore the answer would be a non-zero integer

[silver ermine]

In your case, the μ(y,x) isn't defined?

if path between a and b doesnt exist, what's the value of μ(a,b)?

[hard spindle]

The path from a -> b exists, but it doesnt exist from b -> a

And I'm assuming the value of u(a,b) to be non-zero

[silver ermine]

we always need a value for μ(y,x) i think?

you said one of them is either -1 or 1, but the another i.e. μ(y,x) is not shown

[hard spindle]

I could be reading it wrong but the question asks why is u(x,y) = 0. I take the proof by assuming that u(x,y) =/= 0.
If u(x,y) =/= 0 then it must be either -1 or 1.
If u(x,y) = -1 or 1 | then it follows that u(y,x) = 1 or -1 (to ensure that the equation is still solveable).
This is not possible as if there is a path from x -> y. Then it follows there cannot be a path from y -> x. Therefore u(x,y) cannot be a non-zero integer and it must be zero.

[silver ermine]

So basically we are doubting on the assumption is always defined or not? It's kidna new to me but lets just pass it

[fossil mural]

i think it's always defined

just elias didn't give the full definition

it's the sum, over all the chains, of +1 for even-length chains and -1 for odd-length chains, right?

so in the case where there are no chains, the sum of nothing is zero

[hard spindle]

mhm

You're much more clear than me 😆

I'm pretty ok with a and b.
Looking for a direction to head in for c and d.
It's the strictly greater than symbols that are tripping me up

[silver ermine]

can you show us the definition of moebius function here?

since the well-known form is not totally like what it is in this context

[hard spindle]

I'm not sure exactly what it would be for question c - that's the hard part

It will have to be some combination of even and odd chains

[silver ermine]

well we need some math detective

[fossil mural]

...ah i think i might see what the answers are

ok well firstly

[fossil mural]

this is the definition

[silver ermine]

👀

[hard spindle]

I get that we're taking the sum of the number of odd/even chains. With odd chains being -1 and even being 1.

And we need to calculate the path from x -> y.
So we have beginning point of u(x,x) which is even chain of 1.
Then we move u(x,y) which is odd chain of -1.
Sum that it's 0?

Ah we can't do that I'm wrong. that's the strictly negatives?

[fossil mural]

uh...?

ok i now have no idea what you're talking about

u(x,x) and u(x,y) aren't chains, they're numbers

also we can't actually solve it by just counting up all of the chains because we're not told what the poset is, so we need one argument that works for all of them

[hard spindle]

ahhh ok

[fossil mural]

in the case of the poset with just {x, y} and x < y, u(x, y) is 1, because there's only one chain from x to y, which is {x, y}

[hard spindle]

The poset has elements x, y, z with x < z < y

[fossil mural]

yep

so if it was just those

then the chains would be (x, y), which is even, and (x, z, y), which is odd, so the sum is 0

but there might also be other elements

[fossil mural]

so basically we want to use this

find a bijection between the chains of even length and the chains of odd length

because that means there's the same number of them (even if we don't know what that number is), so the sum is 0

[hard spindle]

Ahhhh ok ok I'll read over my notes again and see if I can find something about a bijection

[fossil mural]

uh

what

...as in you don't know what the word "bijection" means?

[hard spindle]

I wanna see if we have done one already and see if it's applicable to this problem xD

[fossil mural]

it isn't

even if you've done something similar before, searching for the word "bijection" ...doesn't make any sense

it's like saying, oh well this problem involves even numbers, and then searching through your notes for any other occurrence of the letter e

i guess it would be useful in the sense that it would tell you what a bijection is if you don't know that, but the core part of the idea here is a specific insight about this particular situation

[hard spindle]

You've lost me with this last part - sorry

[fossil mural]

the thing you have to realise is about specifically this problem

it's not going to be something that's come up before unless you have previously thought about specifically "the set of chains between x and y in a poset with elements x < z < y where (z,y) is the only arc of P that ends at y in the Hasse diagram for P"

[hard spindle]

Ah ok

[silver ermine]

what is a length of a chain? |Chain|?

[hard spindle]

After you draw a Hasse diagram, the lines that link the diagram are the "chains" from what I understand.
So each line between two points is a chain

[silver ermine]

so a-b-c is a chain and has length 2?

or 3?

[hard spindle]

2

[silver ermine]

k

[hard spindle]

so in that case u(a,c) = 1 (from what I understand)

@fossil mural Any tips for d?

[ashen bane]

can someone give me some guidelines solving combinatorically problems

for example showing those both equal

[brave rock]

There's a straightforward way to do this one in particular: you simply expand the brackets, apply known results on the sum of i^2 and i, and then simplify after using the formula for (n+1 C 3)

[ashen bane]

Oh no no

[brave rock]

In general there is no single method.

[ashen bane]

Not algebric

They call it Combinatoricall way

making up a story that left and right side both solve

thus equal

I cant prove it algebric

[brave rock]

OK well I can't see it, but you have probably been given hints.

[ashen bane]

this is the first exercise in the textbook lol

No prior info to that

[brave rock]

I assure you that the previous content of the textbook provides context.

There is plenty of prior info.

[ashen bane]

idk, they just usually make up story that both sides of equation solve

Like combinatorical question

[silver ermine]

sounds like something inductoin

[ashen bane]

but choosing 3 people from n+1 people doesnt work for me

no lol

[silver ermine]

do you mean modeling by nature language

daily language*

[brave rock]

Here is a hint: choose the 'middle' person. How many ways can we choose the other two people, one of whom occurs 'to the left' and the other 'to the right'?

[ashen bane]

oh that makes sense

[patent solstice]

Hi all, I'm cramming for my final exam tomorrow lol - how does dominance work in big-O?

I'm having trouble understanding their explanation

For example, 2^{n+10} \in O(2^{2})

[hard citrus]

how would you guys simplify this expression in Boolean algebra? online calculator says there's no way and i couldn't figure something out too
$$ad+c'b'+b'd'+a'c'$$

[vital dew]

horizon2.0

[coral parcel]

You can factor either both appearances of ¬c or both appearances of ¬b out as a single term. But whether you'd consider that a simplification is possibly debatable.

[hard citrus]

yeah but there are no further steps to simplify it, doesn't it? seems weird they would give us this question

[coral parcel]

Depends on whether you consider factoring out either ¬c or ¬b to be a simplification.

[weary tiger]

If i have a set {1,2,3,4,5,6,7,8} and I want to make create a 5 digit number where 3 is before 5 and 5 is before 3. How many can i make?

3 5 8

so i should get 5C2 * 6*5

but this is wrong

the answer is 5C2 * 5 * 4

so this is the configuration

but why is it that?

in this configuration i can have for example 12358 or 13582

but, i cant have 35812

in the first configuration i can have 35812 and 12358 as example digits where 358 is at the beginning or the end

[coral parcel]

It looks like there's a lot more than 5 digits in the number you're building there. What do the underscores mean?

[weary tiger]

the available positions

3 5 8 is fixed

so where can i place the remaining 2 numbers basically

[coral parcel]

How can there be that many positions available if the finial number should only have 5 digits?

[weary tiger]

well its possible positions

[coral parcel]

Sorry.
How can that many positions be be possibe if the final number should only have 5 digits?

[weary tiger]

but we need to place 2 numbers in those possible positions

[silver ermine]

Basically same idea as in mathematics analysis. They consider only the case when the function takes a big enough argument. For the term that can not be represent as k*dominance where k belongs to R, its said to be too small to consider and effectively equivalent as 0 considering the size so ignore them.

[weary tiger]

because 3 needs to be somehwere before 5 and 5 somewhere before 8

[coral parcel]

Once you've selected where 3, 5, and 8 go, there should only be 2 positions left to fill in.

[weary tiger]

so i fixed 3 5 8 in empty space

yes

but the number can go in between the 3 and the 5

or in between the 5 and the 8

[coral parcel]

But why are there so many positions free next to your 3, 5, and 8? That would make a number much longer than 5 digits.

There might not be any room between 3 and 5 after you've decided where they go.

Or there might be two spaces.

But you cannot possibly put down 3, 5, and 8 in a five-place sequence and still have either 5 or 6 positions open to fill.

[weary tiger]

ah i see

i thought it would still work

like for example

i took that from filling out this

[weary tiger]

this string would be 13528 ignoring the empty positions

[weary tiger]

true but i've encountered some problems like this

part (iii)

look

i should have 12 positions right?

[coral parcel]

Why would you make a lot of empty positions just to ignore them afterwards? Even if you can make it work without over or undercounting, it feels like a huge detour.

[weary tiger]

idk its just how i think of it

thats for the other problem

see, we place the 7 boys in a row

[coral parcel]

Okay, let me ask another question. What does "5C2" in your solution symbolize?

[weary tiger]

5 choose 2

[coral parcel]

fghjk

Why is there a 5 choose 2 in your solution?

[weary tiger]

because there are 5 numbers left to choose from

and we need 2

since 3,5,8 have been used

[coral parcel]

Hmm, I thought you were choosing which two of the five positions in the final number would not be filled with 3, 5, 8

[weary tiger]

ah no

i chose 2 numbers from the 5 remaining

the 6 * 5 is where i place them

but just to clarify my process

i brought up another similar problem

where we have 7 boys and 5 girls and we want to seat them such that no two girls are adjacent

in this case we arrange the boys in a row 7! ways

then we have this

now we have 8 places to place the 5 girls

so thats 8 permutate 5

so how can't i translate this to this problem?

notice that there should be 12 seats, yet there are 15 in this drawing

so i should be able to translate this to the 3 5 8 problem?

yes, of course, you can draw 5 positions and find all the cases and sub cases, but i think this is a faster way

[ashen bane]

oh this broke my head when i first learnt it

[weary tiger]

ye exactly

how does this work and for the number problem it does not?

it makes no sense

combinatorics = ☠️

[coral parcel]

I see what your approach is now. But your problem here is that there's only 4 different positions you can put the first of your chosen digits in. After you've put it somewhere there will be 5 different places to put the second of them relative to the the four digits now on the paper.
But with the diagram here you end up counting both of 1_3_5_82 and _13_5_82 as distinct solutions, which leads to overcounting.
On the other hand you have no way to produce 31258.

[weary tiger]

so which solution are we referring to?

because i presented two solutions one is right the other is wrong

[coral parcel]

Then one I responded to where you wrote _ _ 3 _ 5 _ 8 _.

[weary tiger]

ah thats the correct one

(5 choose 2) * 5 * 4 = 200

[coral parcel]

It may give the correct result, but for wrong reasons.

[weary tiger]

ah i see

so this approach is not good

but how come it works for the seats in a row?

[weary tiger]

for this one

i presented two problems where i employed similar solutions

how many ways can you seat 7 boys and 5 girls such that no two girls are adjacent?

[coral parcel]

In that case you cannot have two girls next to each other. But for the number problem you are allowed to put two of the non-{3,5,8} digits next to each other.I

[weary tiger]

ah true

but it did work for other problems

let me see

yeah nvm

there is no other way

thats the only case where you would use it

so how do you solve this problem?

is there only one way?

_ _ _ _ _

you draw this

then you see how many cases you can have

you fix the 3 in either position 1 2 or 3

if you put 3 in the first position you get 3 + 2 + 1 (since 5 can go on the 2nd, 3rd or 4th position

[coral parcel]

My way would have been: Start by picking three of the positions to fill in with {3,5,8}. This can be done in (5 choose 3) ways. Then pick one of the 5 remaining digits to go in the leftmost of the unclaimed positions. Then pick one of the 4 remaining digits to go in the final unclaimed position.

[weary tiger]

yes and you get 200

thats a good way

since you choose 3 positions and you dont order them meaning that the order 3 5 8 will remain intact

[coral parcel]

But we can fix your approach too. Start by writing down:
| 3 5 8 |
Then pick two more digits, in one of 5 choose 2 ways.
Write the smaller of your two digits in one of the four gaps on the paper.
Now there are five gaps, so pick one of those to write the larger of your chosen digits.

[weary tiger]

and why is that way better or more refined than mine?

it looks like the same thing?

[hard citrus]

is this right to open parentheses this way in boolean alegbra? or is there some different way?

[coral parcel]

The difference is that my version doesn't start by committing to how many blank spaces there are where. I start with just a single gap (of yet-unknown length!) between digits on the paper and at each end, and then each time I place a digit the gap I place it in splits into two instead of being consumed.

[weary tiger]

ah i see

[coral parcel]

That is a valid way, at least, but you could also have chosen just to distribute one of the sums first and see if that leads you anyway.
What you have there looks like good progress, though: Most of your terms disappear because they have both a variable and its negation in them.

[hard citrus]

yeah im only left with the last term, though i dont really had a method in mind just opened them with what felt normal operation (im aware of $x+yz=(x+y)(x+z)$)

[vital dew]

horizon2.0

[coral parcel]

Which is perfectly appropriate since a Boolean algebra does satisfy the same distributive laws that let you do it with numbers.

The fact that it satissfies more than that shouldn't stop you.

[silver ermine]

I'm thinking about the wording and the accurate definition of "partition".

according to wikipedia, partition is "wrapped" as in this picture

additionally this is the definition of Chains in this material's context

[silver ermine]

So the union here would be the partitioned set itself but not a partition of it.

By the definition in wikipedia, a set itself can not be a partition of it.

I don't know if it's a wording convention or something but if no it's a bit not so accurate?

source:https://ti.inf.ethz.ch/ew/lehre/extremal04/heer.pdf

[silver ermine]

Another question: Is the notation"nlogn" here overloaded by any convention?

How is this computed to be a set?

[last flicker]

wym,like are you asking whqat it means that the sum is in nlogn-O(n)

[coral parcel]

The most common way to formalize what big-O notation means is that an expression that involves big-O really describes a set of functions:

"nlogh - O(n)" stands for the set of all functions of the form f(n) = nlogn - g(n) where g ranges over all functions that grow no master than n.

Traditionally, being a member of this set is usually written with a "=" sign (as a conventional "abuse of notation"), but in your quote the author must have felt it would be clearer to use an ordinary membership symbol instead.

[coral parcel]

Writing C1 cup ... cup Cn instead of { C1, ..., Cn } for speaking about the partition is just a presentation choice. It's the sets C_i that are important, not the wrapping they come in.

[silver ermine]

According to the definition I've seen, either in the material of my course or wikipedia(they are almost the same), I can tell O(n) is a set or at least can be taken as a set very often because that's what I've seen in the first place. The problem is that, they didn't define subtraction between mathematical funcitons and sets such as f(n)-S. I do see f(n) represent the value of a function in the codomain or the function's set representation/itself very often, but in this case I was wondering if it's overloaded to represent something other because either a value (could be in R) or such a kind of set (the very first definition of functions) don't looked making many sense to me here.

[silver ermine]

It's like saying x={x}, I can take this convention anyway.

[silver ermine]

I mean if it's written as "...belongs to O(nlogn-n)" or "...belongs to O(nlogn)" I would know what it means.

[silver ermine]

Okay now I get it

just go wild

(100+ pages later)

[vital dew]

The following error occured while calculating:
Error: Unexpected operator { (char 5)

Result:

1

[crystal rune]

Oops wrong channel

[orchid jasper]

Is this a valid proof?

[prime steeple]

It might check out, even if carrying then ?> around is not necessary. That said, I' certain there's a shorter proof without roots and fractions.

[obtuse lance]

$2^{n+1} =2 * 2^n > 2*n^2 = n^2 + n^2 > n^2+2n+1 = (n+1)^2$ the last inequality is a slight case of expanding the inequality $(n-1)^2 > 2$ to see that $n^2 > 2n+1$. (I worked backwards from what I needed to make that.)

[vital dew]

Merosity

[twilit sundial]

$2^n>2n+1$ for $n\ge 5$ so you can add that to both sides

[vital dew]

elrichardo1337