discrete-math

[vernal cypress]

@dire obsidian can you help?

[dire obsidian]

I haven't learned that

[balmy jay]

Do you not know what the notation means or are you just stuck on how to prove this

[vernal cypress]

I don't know what it means and I have an exam in 3 hours

[balmy jay]

Oh ok so that bracket looking thing is the floor function

Basically floor(x) always rounds x down

So floor(5) = 5 and floor(2.3) = 2

That make sense?

[vernal cypress]

yup

so roof 2.5 is 3

[balmy jay]

Yeh

But just fyi roof doesn't appear in the question so

[vernal cypress]

yea ik

[balmy jay]

Ok great

Do you have any idea of where to start with the proof

[vernal cypress]

by Let?

I have the answer to that equation btw, I just don't know how to get the answer

[balmy jay]

What's let

[vernal cypress]

.

[balmy jay]

That looks really confusing lol

[vernal cypress]

that calmed me down, thanks

[balmy jay]

Lol np

What I'm thinking rn is to split it into cases: one where x is an integer and one where x is between 2 integers and then go from there

[vernal cypress]

how do we do that?

[balmy jay]

So the first case is when x is an integer right

In that case what is floor(x)

[vernal cypress]

" Prove that if m and n are positive integers and x is a real number"

[dire obsidian]

x integer and x between integers covers all real number
He's splitting it into 2 cases

[balmy jay]

Yeh sorry I forgot to say that

Basically we know x is in the reals so we can divide it into 2 cases, either it's an integer or it's between 2 integers

[dire obsidian]

I think if x is integer you can just say floor or roof doesn't affect it at all?

[vernal cypress]

we know it's in the reals cause it's devided by smt or wut?

[balmy jay]

Yeah that's right

[vernal cypress]

arent real numbers numbers with decimal expansion only?

[balmy jay]

It's just given in the problem, not sure what you're trying to get at

[balmy jay]

5 is also a real number

[vernal cypress]

5.0 u mean?

[balmy jay]

Technically you can write it with a decimal expansion but you don't have to

Yeh

[dire obsidian]

look in a number line.

essentially he split it into 2 sections

1. The points (x integer)
2. The areas between the points (x between integers)

[vernal cypress]

Oh I get it

[silver panther]

$N\subset Z \subset Q \subset R \subset C$

[vital dew]

Max..

[balmy jay]

Yep

[silver panther]

Nope

[balmy jay]

Yeah that's a really concise way of saying what I was trying to get at

[silver panther]

R includes pi

[dire obsidian]

oh sh

[balmy jay]

Also include irrationals

[silver panther]

Z u Q doesn't

[silver panther]

Ye

[balmy jay]

🙂

[dire obsidian]

so you also have a case for irrationals, but in this case you can treat them as decimals since floor/roof?

[silver panther]

Real numbers = any number that doesn't have an imaginary part

[balmy jay]

You could but it doesn't matter either way since we only care if our number is between 2 integers

[dire obsidian]

yeah

hard part is proving between integers didn't learn that at all

[balmy jay]

Yeh but it's not too tricky

Just gotta think a little

[vernal cypress]

m & n has no meaning right?

they're just like x y correct?

[dire obsidian]

m & n are just positive integers

[stray reef]

the letters m and n do not have any meaning outside of context

[balmy jay]

Yep

They're variables

[stray reef]

they are sometimes chosen to stand in for integer-valued things, but that's by no means an absolute requirement

[vernal cypress]

(just so it's easier to see)

[dire obsidian]

$m,n \in Z^+$

[vital dew]

Salt

[stray reef]

well then you're told they are positive integers

also, \mathbb{} for number sets

[vernal cypress]

but m cannot be 0, correct?

[stray reef]

$\mathbb{N}, \mathbb{Z}, \mathbb{Q}, \mathbb{R}, \mathbb{C}$

[vital dew]

Ann

[balmy jay]

Correct

[stray reef]

m is stated to be a positive integer, so yes it can't be 0

[vernal cypress]

so how do I prove this?

[stray reef]

i would write $x = mq + r + z$, where $q$ and $r$ are the quotient and remainder on division of $\floor{x}$ by $m$, and $z \in [0,1)$ is the fractional part of $x$.

[vital dew]

Ann

[stray reef]

i think your two cases would be on whether r+n ≥ m or not

[balmy jay]

Yeah I was thinking of something similar, basically if x is an integer the claim is going to be true since floor(x) = x. If x is between 2 integers, the part after its decimal point will be bounded by 0 and 1 so we can do something like x = y + k, where y = floor(x) and then you just manipulate the equations to get the claim

[vernal cypress]

idk if this will help but here

[vernal cypress]

so what Ann said is the answer?

[balmy jay]

It should get you started on the path to the answer yea

[stray reef]

i didn't give the answer

what i wrote is just a starting point

[balmy jay]

Are you stuck at a specific point, we can try to help

[vernal cypress]

yes, I don't know how to solve the rest

since my teacher showed smt and I got smt else in here so I am confused now

[balmy jay]

I'd suggest to try to develop your own answer, you'll learn more that way

So we had 2 cases right for x

If x is an integer, what would floor(x) be

[vernal cypress]

itself

[balmy jay]

Right so floor(x) = x

[vernal cypress]

yes

[balmy jay]

So for the left side what would that be

[vernal cypress]

this ?

[balmy jay]

Yeah

So we just established floor(x) = x so what does that simplify to

[vernal cypress]

x + n over m

[balmy jay]

Right

And what about the right side

[vernal cypress]

x + n over m
too

[balmy jay]

Yeh

Actually to be more precise for both of these it'd be floor(what you said)

But they both end up being the same so 🤷‍♂️

So do you see why when x is an integer the claim holds

[vernal cypress]

yup

[vernal cypress]

but I should remove the floor for x in the left side right?

and keep the outside one

[balmy jay]

Yes

[weary tiger]

hello

quick question

if im proving that a set is countably infinite

it means i have to prove that the set has the same cardinality as the set of positive integers

correct?

When it comes to proving the cardinality between the two sets, there must be a one to one correspondance?

[vernal cypress]

so I get this

[balmy jay]

Yeh or I think the natural numbers would work too, not sure if there's a difference

[balmy jay]

Yes in order to have a bijection and show they're the same "size"

[balmy jay]

Yeh

That's right

[weary tiger]

so i need surjection too?\

between the set and z+?

[balmy jay]

Yeh

[weary tiger]

thank u good sir

[balmy jay]

So every output has some input

Np

[vernal cypress]

well if they are the same, why do I need to prove it?

[balmy jay]

We showed they are the same

We didn't initially know they were the same

And btw we've just proven the claim holds when x is any integer, still have to do the other case

[dire obsidian]

hard part

[balmy jay]

Yup

Not that hard in my head (~~might be doing something wrong tho ~~)

@vernal cypress Do you have any idea of what to do for the 2nd case

[vernal cypress]

so I should say since x E R then ?

[vernal cypress]

to solve for what exactly ?

[balmy jay]

You mean $x \in \mathbb{R}$?

[vital dew]

math man

[balmy jay]

If so you don't need to, problem already gives you that

[vernal cypress]

yes

[balmy jay]

To prove the claim holds true when x is between 2 integers

[dire obsidian]

I think you could try thinking for 2nd case something like

$\floor{\frac{\floor{x}+n}{m}}$ vs $\floor{\frac{x+n}{m}}$

as
this
$\floor{\floor{x}}$ vs $\floor{x}$

[balmy jay]

Double floor function?

[dire obsidian]

yeah since we know that m and n are positive integers

they won't really affect the balance

idk my wording kinda bad

[balmy jay]

Lol it's fine

Why would you double floor the x tho

[dire obsidian]

but it's essentially double floor on x

[balmy jay]

Doesn't really do anything

[dire obsidian]

because you have floor for x then floor for the entire thing

[balmy jay]

Oh ok I thought of it a different way

[dire obsidian]

yeah just my way of thinking idk how to prove that rigorously tho

but essentially you ignore the m and n since they don't affect anything because they are positive integers

if you think of double floor x it is obvious why it works for x all real numbers

wait I might be high

no I'm right??

yeah

[vital dew]

Salt

[balmy jay]

So I was thinking since x is between 2 integers, we can say y = x - r, for some r between 0 and 1. This means x = y + r so the left side becomes floor((y + n)/m) and the right side becomes floor((y + r + n)/m) = floor((y + n)/m + r/m). r/m has to be between 0 and 1 so the floor function will ignore that and just return floor((y + n)/m)

Lmk if that doesn't make sense

[dire obsidian]

This statement is problematic because I didn't take into account m divide resulting in decimal

[vernal cypress]

I wish I can add some value to this conversation

sorry

[dire obsidian]

I feel like I am adding nothing of value to the conversation as well ;-;

[balmy jay]

Rip 😭

[vernal cypress]

amma fail this exam

I am going to memorize what the teacher wrote and try to make sense of it in the exam ig

I still need help with 1 question which I think is way easier but I am not 100% of my answer

[balmy jay]

You can send it

[dire obsidian]

how do you mitigate the risk of getting a higher integer after adding r/m?

[unreal stump]

The term vanishes because
(\floor{x}+n)%m is an integer in {0,m-1}

And frac{x} can't make it add upto m

[balmy jay]

I think so m is a positive integer and we know 0 < r < 1 so m must be greater than r so r/m must be less than 1. So we're adding something less than 1 to (y + n)/m

[dire obsidian]

yeah but what if after adding to (y+n)/m it increases the whole integer?

Eg.
r/m = 0.4
y+n/m = 0.7
0.4 + 0.7 = 1.1

[balmy jay]

Yeah that's kinda the flaw in my logic that I just realized lmao

[dire obsidian]

yeah I kinda noticed that b/c of ann's claim here

[unreal stump]

Pointed to the wrong thing but this should be the proof

[dire obsidian]

dam that's kinda wacko

[balmy jay]

This makes me see how bad I am at math 😭

[dire obsidian]

😔

[vernal cypress]

can yall help with this?

[dire obsidian]

Didn't you already ask about 3 a)

[vernal cypress]

yes but it seems that no one knows the exact answer and I only have 1 hour before my exam, so it's better to move on to another question

[dire obsidian]

Dude tropo and I literally had a dialogue about it

we got the right answer alr

[vernal cypress]

wait wut? didn't you disagree ?

[dire obsidian]

we didn't

both were right answers just different representations

[vernal cypress]

I see

[vernal cypress]

so this is correct

[dire obsidian]

.

[dire obsidian]

no I made the same mistake as math man for here I failed to take into account decimal result after dividing by m

@unreal stump is discrete math pro his proof should be the most correct

[vernal cypress]

alr

[dire obsidian]

@vernal cypress take a look at this for 3 a)

Since you have exam in 1 hour I'll just tell you the solution to 3 a)

C(21,1) * C(20,1) * C(19,3)

C = choose

do you understand the question now?

[vernal cypress]

how did you find that? did you just remove 1 3 times?

since there is 3 medals

[dire obsidian]

Reasoning:

Have 21 players, choose 1 to give gold medal
Have remaining 20 players, choose 1 to give silver medal
Have remaining 19 players, choose 3 to give bronze medal

[vernal cypress]

C = choose, wdym by that

so 21 ways to give gold medal and 20 to give silver and 19 to give bronze

I am guessing C stands for ways

[dire obsidian]

note that the order which you give the medal type in doesn't matter as well
so another possible distribution is

C(21,3) * C(18,1) * C(17,1)

Have 21 players, choose 3 to give bronze medal
Have remaining 18 players, choose 1 to give silver medal
Have remaining 17 players, choose 1 to give gold medal

[dire obsidian]

choose is

[vernal cypress]

Alright thanks a lot, I will try to solve B on my own. Have a great day

[vernal cypress]

Alright, back. the exam was hard af, I might jump off my balcony

[silver panther]

😂

@vernal cypress pls don't

It's a sign to start preparation sooner and grind harder 🔥

[wild cloak]

Q. In how many ways can 6 cards be taken from
one deck, in such a way that cards of all colors are
chosen?

The way I thought of it is:
I by default assign a red and a black to the first 2 out of 6 places.
R B _ _ _ _

To select a red in that first place there are 26 ways, to select a black in the second is 26 ways and for the remaining I have 50C4 possibilities?

So, 26 x 26 x 50C4?

[coral parcel]

No, that counts most hands many times, depending which two of the cards you consider "the red" and "the black" card.

Instead, count all six-card hands, and then subtract the all-black and the all-red ones.

(But the way, is the problem translated from a non-English language? "All colors" sounds strange when there are only two of them, and some languages use their word for "color" to denote what is called "suit" in English -- if you want each suit to be represented, you get into a more complicated inclusion-exclusion computation).

[dense glade]

for b

what is the answer for b?

[dire obsidian]

sounds like pigeonhole

[dense glade]

I don't think any number in the domain can give -1 for f(x)=x^2 right?

[dire obsidian]

omygosh is that composite functions

[dense glade]

yes

[dire obsidian]

yeah I can't contribute to that then I haven't learned composite functions nor inverse functions

[dense glade]

no worries I figured it out

[severe swan]

How would I calculate this?

How many (base 10) integers (leading 0's are NOT allowed) between 1 and 9999 are palindromes?
All of the following are examples of such integers: 5, 22, 373, 8448. The following would not count, because they have leading 0's: 0, 00, 0000, 010, 0440.

Answer: 198

[vale cairn]

Think about how much information is required to determine a palindrome between 1 and 9999

that should give you an easy way to count them

[marble pivot]

@severe swan ^

do u get what they're saying

[dire obsidian]

I'll try to have a swing at this

Case 1: Simple ones
1 digit:
8 possibilities {2,3,4,5,...,9}
2 digits:
9 possibilities {11, 22,33,44,...,99}

Case 2: Complex ones
3 digits:
-> miniCase i: all same
9 possibilities {111,222,333,444,...999}
-> miniCase ii: front back same; middle different from front & back [eg. 303]
= (middle) x (frontback) - (middlefrontbacksame)
= (9x10) - 9 = 81

4 digits: 
 -> miniCase i: all same
        8 possibilities {1111,2222,3333,...8888}
 -> miniCase ii: front back same; middle two same but different from frontback [eg. 9009]
       = (middletwo) x (frontback) - (middletwofrontbacksame) - (9999 because not included)
       = (10x9) - 8 - 1  = 81

= 196

Stuck at finding the last 2 possibilities (answer said 198)... 😭

[vale cairn]

Yeah so my thinking was/is that
Given any number 1 <= n <= 99, note we can generate two palindromes by appending a reversed copy and deciding whether to delete a letter in the middle or not. For example 23 would correspond to 2332 and 232. (under this convention, 1 generates 1 and 11, and so forth).
This clearly generates every palindrome and there are no repeats: one or two digit palindromes are determined by their first digit, and three/four digit palindromes are uniquely determined by their first two digits

[dire obsidian]

yeah I'm just stuck at finding the last 2 possibilities

[vale cairn]

my point is that this a bit more uniform because I'm just saying there's a 1-2 correspondence but ye

I mean you seem to have neglected 1

[dire obsidian]

I neglected both 1 and 9999

[vale cairn]

Yes

that'll be it

[dire obsidian]

because it said "between"

[vale cairn]

lol

Ok fair enough

[dire obsidian]

yeah but it's not just 1 and 9999 that got affected by this

[vale cairn]

Oh true

[dire obsidian]

wacko

[snow copper]

Between in discrete questions is usually inclusive of the end points in my experience

[dire obsidian]

can someone explain example 1.3?

[dense glade]

does a relation on anything means anything x anything?

[dire obsidian]

in context of sets pretty much iirc

[dense glade]

hmm

because

a relation is z is aRb if a|b

do you think this relation is reflexive or not

[sleek loom]

a|a is always true so yes

[dire obsidian]

I need help understanding this question.

I recognize that the hardest part is figuring out the conditions and repercussions of setting the first element to something. The rest plays out exactly the same as linear arrangement.

[dire obsidian]

I'm going to sleep now but would like to have this question answered

[austere cedar]

Under all possible placements, two placements which only differ by rotation are considered identical. We can split all placements into groups, where in each group there are only identical placements. So we want to find the number of groups. So when we count the placements, we need to count one placement from every group. In each group is exactly one placement with A at the top, so if we count every placement with A at the top, we also get the total number of groups. Thats why we chose A to be at the top.

[weary tiger]

can u guys come up with a non prime positive integer n such as 4 | n-1 and 3 | n+1

[gritty crescent]

65?

[weary tiger]

funny thing is, I gave up at 63😭😭😭

[gritty crescent]

[weary tiger]

LOL

[gritty crescent]

I thought about 5 first but it was a prime, kept increasing by 10 till I hit 65

There might be a smaller value too, I'm not sure

[weary tiger]

why 10

[gritty crescent]

No particular reason, just felt like it would keep spitting out numbers in a way that n+1 will have 6 in the unit place and n-1 will have 4

[weary tiger]

im mentally insecure rn

that was very efficient

[gritty crescent]

It's okay, it could have taken much longer for me as well. Got lucky maybe. 😛

[weary tiger]

whatever it was , I need it😭

[weary tiger]

it is the smallest

[gritty crescent]

[crystal dove]

If I want to use any 2 generators to produce a hamiltonian path through a symmetric group, does anyone have any ideas where I might begin?

[coral parcel]

The two conditions can be restated as n == 1 (mod 4) and n == -1 (mod 3). By the Chinese remainder theorem these combine to n == 5 (mod 12), or in other words n = 5+12k for some k. An obvious way to force that to be composite is to set k=5, which yields n=65.

[weary tiger]

bro.

🤝

I switched to arithmetic not too long ago , and I'm still trying to let go of that calculus thinking

[coral parcel]

Can you speficy the task more exactly? Do you want to find two generators such the the Cayley graph is Hamiltonian (respecting orientation, I suppose), or prove that every set of 2 generators has this property, or to describe an efficient way to compute a concrete Hamiltonian cycle?

[crystal dove]

I want to find an efficient way to compute a concrete Hamiltonian path using only 2 generators. I'm not actually sure it's even always possible with any 2 generators. The purpose is for visual art.

[coral parcel]

When you say Hamiltonian path, do you specifically mean it doesn't need to be closed?

[crystal dove]

It doesn't need to be closed, I just want to generate the Cayley graph in a beautiful way.

[coral parcel]

Hmm, feels complicated.

[spare forge]

Would someone be able to offer an example of this in practice?

[wicked rain]

could someone explain why my answer is wrong?

[coral parcel]

How did you get your answer?

[wicked rain]

knowing that 0-9 there are 10 numbers

and 0 or 9 can not be used in first slot

so 8 possible digits for the first slot

[coral parcel]

If 799,992 is a correct answer, we must assume that "should not have repeated digits of the same value" really means "must not be the same digit repeated 6 times".

[wicked rain]

8*9*8*7*6*5

[wicked rain]

i had that in assumption, but how to interpret it

[coral parcel]

Okay, that looks like it corresponds to a reasonable interpretation of the text of the problem, but apparently not the intended one.

[wicked rain]

🤔

[coral parcel]

It looks like you interpreted "should not have repeated digits of the same value" as "must not have more than one occurrence of any digit".

[wicked rain]

right

[coral parcel]

For what it's worth, I initially interpreted it as "any two neighboring digits must be different", leading to a third count yet.

[wicked rain]

example is: 123 and not 113

is that what what is meant?

[coral parcel]

Yes, I understand how you interpreted it.

Evidently it is not the interpretation used to declare 799,992 to be a correct answer.

What leads to 799,992 possibilities is that, for example, 222622 is allowed but 222222 or 987654 are not.

[wicked rain]

i seem to get your point

[coral parcel]

It's a stupidly ambiguous question.

[wicked rain]

😥

[spare forge]

❓

[wicked rain]

hold on, i have to break my fasting

i am still confused how it is solved, but i will try to do it with your interpretation

[coral parcel]

I'm confused which kind of answer you expect here?

[spare forge]

An example of what that $X$ would look like

[vital dew]

Qlinltiqor

[coral parcel]

An example of some random well-quasi-order or an example of a quasi-order that fails to be well in one of the two specified ways?

[spare forge]

Either

[coral parcel]

In $\mathbb Z$ define $a\sqsubseteq b$ if $|a|\le|b|$. Then $\sqsubseteq$ is a well-quasi-order.

[vital dew]

Troposphere

[coral parcel]

In $\mathbb Q$, define $a\preceq b$ if $|a|\le |b|$. Then $\preceq$ is a quasi-ordering but not well, because there's an infinite strictly decreasing sequence.

[vital dew]

Troposphere

[spare forge]

Isn't that the symbol for positive semi-definiteness? $\preceq?$

[vital dew]

Qlinltiqor

[coral parcel]

It's also that, but it can be used for random order-like relations to use in examples too. (There are not enough symbols to go around to let every meaning have a monopoly on one symbol).

[spare forge]

So if we remove the infinite requirement and just use some small finite subset of $\mathbb{Z},$ like ${1, 2, 3},$ then are you saying ${{1, 2}, {2, 3}}$ is the $\sqsubseteq$ ordering?

[vital dew]

Qlinltiqor

[coral parcel]

In $Q$, defined $a\trianglelefteq b$ if $|a|\le|b|$ and $a-b\in\mathbb Z$. Then $\trianglelefteq$ is a quasi-ordering, but is not well because $[1,2)$ is an infinite antichain.

[vital dew]

Troposphere

[coral parcel]

As a consequence of the proposition, a quasi-ordering with finitely many elements is always a well-quasi-order.

[spare forge]

Oh, okay. So,with your example and mine, if the counting pattern follows infinitely, does the ordering I wrote fit the ordering pattern also follow similarly or does $\sqsubseteq$ mean something about the size of sets rather than what's inside of them?

[vital dew]

Qlinltiqor

[coral parcel]

My \sqsubset ordering essentially says "compare integers as usual except ignore the minus sign in front of negative numbers".

That's just a device to make sure it's not antisymmetric, which would make it qualify as a not-quasi order, and therefore presumably not as interesting an exmple.

So we have $5 \sqsubseteq -8$, for example, or $42 \sqsubseteq -42 \sqsubseteq 42$.

[vital dew]

Troposphere

[spare forge]

Oh, okay. Thanks for that example

[spare forge]

I guess should we try thinking of something in analog of graphs?

Just as an exercise*

[coral parcel]

A graph picture can be useful for thinking of order-like relations, yes.

[spare forge]

There's probably going to be something on an infinite induced subgraph and edge coloring?

[coral parcel]

Or a more concrete way to think of a quasi-ordering in particular could be as the combination of an equivalence relation and a partial order among the equivalence classes.

Edge coloring doesn't sound immediately relevant. (But if you can make it stick to something and get insight out of it, more power to you ...)

[spare forge]

I'm trying to invoke Ramsey's Theorem of monochromatic subsets in this

[coral parcel]

Hmm, that sounds like heavily overthinking something.

What are you aiming to achieve?

[spare forge]

So, from the proposition: if $x_{0}, x_{1}, \dots$ is any infinite sequence in $X$ and we let $K$ be a complete graph on $\mathbb{N},$ coloring edges $ij (i < j), ij \in E(K)$ with three colors: green $x_{i} \leq x_{j},$ red $x_{i} > x_{j},$ amber $x_{i}, x_{j}$ if incomparable, how can we apply Ramsey's Theorem to speak about the antichains or decreasing sequences in the context of the green subsequences?

[vital dew]

Qlinltiqor

[spare forge]

And then subsequently give it as a proof of the proposition using an analog of graphs.

[coral parcel]

I don't think that will work.

To begin wth, Ramsey's theorem as usually stated is for undirected graphs.

It doesn't give you any good way to speak about the central requirement of a quasi-order being a transitive relation.

In general it sounds like a horribly complicated and indirect way to argue for a quite simple proposition.

But again, I don't know what you're trying to achieve here.

[spare forge]

I'm just trying to show the proposition for graphs.

[cerulean token]

hi

[coral parcel]

I think first you will need to be a lot more explicit about what "the proposition for graphs" is.

[spare forge]

The proposition for a complete graph on $\mathbb{N}$? 😬

[vital dew]

Qlinltiqor

[coral parcel]

I don't know which proposition you're speaking about.

You don't need to tell me, of course, but it will be kinda difficult to have a conversation otherwise.

[spare forge]

Oh, wait, my English is bad. I'm trying to show the proposition in the context of graphs 😅

[coral parcel]

But I'm still not understanding what "the proposition in the context of graphs" is.
It sounds like you have some kind of graph-based generalization or analogue to the characterization of well-quasi-orderings in mind, but it is not as obvious as you think what exactly that analogue would be.
Could you please state it explicitly?

[spare forge]

I die 💀

[spare forge]

some kind of graph-based generalization or analogue to the characterization of well-quasi-orderings in mind
Yes.
but it is not as obvious as you think what exactly that analogue would be.
Could you please state it explicitly?
I do not know what to do now.

[spare forge]

I'll admit, the attempt at the graph example was not mine. I was just trying to understand the part I didn't mention (but asked about) in this proof:

[coral parcel]

Okay, now it makes sense what you're saying.

I thought the original proposition would have a much lighter-weight proof, but I haven't been able to find one for the last hour or so...

[spare forge]

This is (9.1.2) for reference:

[spare forge]

Yhea, this is from a graph theory book (Diestel, 5th edition) that a friend of mine is trying to teach me but I'm trying to learn a bit before our session starts.

[coral parcel]

Interestingly, this proof concludes a stronger property than the definition of "well-quasi-ordering" in https://en.wikipedia.org/wiki/Well-quasi-ordering, which only requires every infinite sequence to have at least one good pair. It could look like your book defines "well-quasi ordering" such that it wants a whole good subsequence. It doesn't seem to be obvious that those definitions are equivalent, other than by going through this proof.

So, now that I understand what you're saying, do you still have a question?

[dire obsidian]

I need help understanding this question.

I recognize that the hardest part is figuring out the conditions and repercussions of setting the first element to something. The rest plays out exactly the same as linear arrangement.

[coral parcel]

Huh, how does that connect to well-quasi-orders?

[dire obsidian]

it doesn't. It's a separate question that I asked yesterday but got buried in messages

[coral parcel]

My annoyance with getting randomly pinged will lead me to ignore that question henceforth.

[dire obsidian]

what counts as 'randomly pinged' ?
I don't think I've ever randomly pinged anybody? (I only ping Helpers or people I am currently in active convo with. I never do random pings...)

Did you mean 'reply pings'?

[young violet]

any help with that

[spare forge]

You should have likely replied to the last comment our helper made to your question and not mine.

[dire obsidian]

there wasn't any

[spare forge]

But the helpers are volunteers. They can only answer at a rate they can. Anyways, my question got buried in an hour but bumping it after a while got a response by our friend here.

[dire obsidian]

yes but replying also counts as ping?

[spare forge]

Anyways, this is digression to the channel. Probably just bump your question again.

[dire obsidian]

Ah right have you learned about circular arrangements before?

you might be able to help me with my issue

[spare forge]

Ehm, possibly. I have yet to understand the page the helper linked me so me helping you might be backlogged by that 😬

But it's an open channel, so I'm sure someone can help in the mean time. Is it the same screenshot from above?

[dire obsidian]

you could try seeing my help thread (same question) to not clog up this channel and re-bump your original question here

[weary tiger]

Is this arithmetic viable?

It’s different from the solutions but it seemed okay to me, I would like confirmation or advice

[vale cairn]

Seems fine, ig you're saying if 2^k < (k+1)! then (k+2)! = (k+2)(k+1)! > (k+2) 2^k >= 2*2^k = 2^(k+1) and I'm not sure how else one could phrase it

In which way was it different?

[weary tiger]

they subbed in for 2^k instead

[vale cairn]

Wdym?

Oh

[vale cairn]

Well it's the same work, just the inequalities being written in a different order

[weary tiger]

yeah i'm just kind of frustrated by discrete because there r so many ways of doing things

and my mind is not creative in any way

but if it works it works i guess

ty

[dire obsidian]

The trick to inequality proofs is taking advantage of inequality on n

[vale cairn]

Np

[weary tiger]

wdym

like i understand i have to use the induction step to literally do anything

it just doesn't click immediately sometimes

but this shit is so hit or miss like ugh

[dire obsidian]

In your case $k \geq 2$

Then you can assume freely in your inductive step after proving base case k=2
$2^k < (k+1)!$ You abuse this and sub it in during your inductive step and try to get it to match the hypothesis you are trying to prove

[vital dew]

Salt

[dire obsidian]

Here I'll give you example

@weary tiger

Another way to abuse inequality is

[jade wing]

If I assume the equality is true, how do i prove the RHS ?

[dire obsidian]

Say you have inequality
$x < y$
for your induction step

you are free to use anything that is greater than y for your right side because overall inequality still stands.
so you are allowed to transform the top to

$x < y^2$

or whatever you want

[weary tiger]

im struggling to follow this proof

[vital dew]

Salt

[dire obsidian]

what part are you not getting?

[weary tiger]

im stuck on 'because'

like how is that a fact

[dire obsidian]

what 'because'?

[weary tiger]

don't you only know that it is true for n = 5

because k^2 < 2^k < 2^k+1

[dire obsidian]

if you prove basecase n = 5 is true
you are free to use k in your induction hypothesis

[weary tiger]

where is the 2k+1 from

on the right side

i was thinking you were turning 2k+1 into 2 * 2k

[dire obsidian]

dude this is like I have a balance
I add 1 to both sides
is the balance still correct?

[weary tiger]

okay it just seems arbitrary to me

i understand that

i just wouldn't think to do that ever

[dire obsidian]

Ok I'll walk through the steps with you

it's actually more obvious than you think

So we initially work with induction hypothesis
$k^2 < 2^k$

we want to show
$(k+1)^2 < 2^{k+1}$

[vital dew]

Salt

[dire obsidian]

are you okay with this so far? @weary tiger

[weary tiger]

yes

[dire obsidian]

so now you take what you are trying to prove and expand it
you usually always do this. Always have your "want to prove" statement expanded
$(k+1)^2 < 2^{k+1} = k^2 + 2k + 1 < 2^{k+1}$

[vital dew]

Salt

[dire obsidian]

@weary tiger is this clear ?

[weary tiger]

yes

well you'd want to try to sub 2^k in for k^2 somehow?

[dire obsidian]

oh wait mb

that was a wrong step

[weary tiger]

or you can change 2^k+1 to 2(2^k) and use it somehow then

[dire obsidian]

what you do next is

Now that you have your expanded " goal"

$k^2 + 2k + 1 < 2^{k+1}$

Leave it for now. This will be the final template you are trying to reach.

Now, we start working with your Induction Hypothesis

$k^2 < 2^k$

[vital dew]

Salt

[weary tiger]

okay

ive never approached a problem like this but im listening

is it a hard and fast rule that you always want to expand something like (k+1) ^2?

[dire obsidian]

A neat thing to point out is that you most of the time want to "reach" the template via the left side first.

So how can $k^2$ become $k^2 + 2k +1$?

[vital dew]

Salt

[weary tiger]

if you somehow turned k into k+1

[dire obsidian]

no don't think about $"(k+1)"$ just purely think about making the left side become exactly the same as the template's left side

[vital dew]

Salt

[weary tiger]

okay you add 2k + 1

[dire obsidian]

Alright, so we add $2k+1$ to the left side, but if we add it to the left side, we need to also add it to the right side to maintain balance of the inequality

[vital dew]

Salt

[weary tiger]

ok

it's making sense

[dire obsidian]

So now induction step becomes

$k^2 + 2k + 1 < 2^{k} + 2k + 1$

[vital dew]

Salt

[weary tiger]

oh cos 2^k is larger than k^2 the proof is done?

[dire obsidian]

no don't rush this

[weary tiger]

okay

[dire obsidian]

Ok, so you now have the left side completely matching the template. The rest goes to trying to get the right side matching the template (Want to turn ${2^k + 2k + 1}$ into ${2^{k+1}}$)

[weary tiger]

ok

[vital dew]

Salt

[weary tiger]

now im lost again

but keep going

[dire obsidian]

where are you lost

[weary tiger]

at the next part

like how are you going to turn it into 2^k+1

[dire obsidian]

k gotcha

Next step is the part you will fiddle the most with.

Think back into your induction hypothesis' right side.

${2^k}$

Even though you have $2^k + 2k +1$ in your induction step right side right now, you want to go back and think in terms of

$(2^k) + (2k + 1)$

Now you think to yourself:

"What would turn $2^k$ into $2^{k+1}$?"

Ah right, $2^k \cdot 2^k$

"So I need to turn the (2k+1) in my induction step right now into $2^k$"

"Wait, I can abuse inequality and turn $2k +1$ into $2^k$ because:

$2k+1 < 2^k$

we know that this is always true because our restrictions for k is $k > 4$

and in terms of the induction step,

$k^2 + 2k + 1 < $2^k + (2k + 1) < 2^k \cdot 2^k$

so we can say

$k^2 + 2k + 1 < 2^k \cdot 2^k$

Proved!

[weary tiger]

Oh i didn't know that 2k+1 < 2^k for k > 3

im seeing that's a theorem now in my textbook

how tf am I supposed to know that

[vital dew]

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

[weary tiger]

wait im kind of lost

What makes something antisymmetric?

[dire obsidian]

not symmetric i think

[dire obsidian]

where are you lost?

[weary tiger]

no lol

oh wait i get it now

[dire obsidian]

The part you have to fiddle with (right side)
is to just look at what will make induction hypothesis right side into template right side
Then literally force them to match via abusing inequality

[weary tiger]

IH?

induction hypo?

[balmy jay]

Yea

[weary tiger]

am i supposed to just know these theorems

[dire obsidian]

that's just how inequality proof works there's no "theorem"

[balmy jay]

Yeh there's some creativity involved as well to figure out how to bound certain quantities

[weary tiger]

isn't 2k+1 < 2^k for k > 2

[dire obsidian]

main part of inequality proof is just recognizing that you can abuse the sht out of inequalities

[weary tiger]

a theorem

there just isn't a formula to follow

which is why this shit is so confusing to me

i also don't know basic exponent rules

[balmy jay]

This is kind of a lot of math

[balmy jay]

Mood lol

[dire obsidian]

what part are you still confused about

you can literally write an algorithm for this

it's so mechanical

[weary tiger]

i think im fine now but idk there's too much creativity

[dire obsidian]

you don't need to be creative

[weary tiger]

like the next thing i struggle with is gonna be so obvious once i get it

[dire obsidian]

there is nothing creative about this

I literally found out 2k+1 < 2^k via forcing right side in induction step

[weary tiger]

it feels like what i lack is creativity when i look at these problems and have no idea what to do

[dire obsidian]

no the only "creative" part is not even creative

you find it when you are trying to force the right side to match

[balmy jay]

I'd argue that while the process of induction itself is very much mechanical the actual details of how you apply it to certain problems can involve creative steps

[dire obsidian]

there's a reason they give you a bound for n

[weary tiger]

The equality of sets

𝐴×(𝐵∖𝐶)=(𝐴×𝐵)∖(𝐴×𝐶)

is true in general.

Write a formal proof of this equality, using the Test for Set Equality.
Does anyone know the proof?

also i have another question

[balmy jay]

Show left set is subset of right set and right set is subset of left set

[dire obsidian]

yeah other cases of induction (not inequality) can be really wacky and creative

[weary tiger]

Ahh I see thanks

[dire obsidian]

But inequality induction proof in a nutshell is abusing the property of inequality itself

[balmy jay]

Yup

[weary tiger]

why are you allowed to substitute a numeric value in for k in this problem

[dire obsidian]

what do you mean substitute?

[weary tiger]

i subbed 2 in for k

second to last line

[dire obsidian]

why woudl you do that

[balmy jay]

$k \geq 2$ maybe?

[vital dew]

math man

[dire obsidian]

ah

wait

[balmy jay]

Yeah in general you don't do that unless you're doing base case

[weary tiger]

okay my prof was doing that sometimes for proofs

and it feels like a slippery slope like it just doesnt make sense to me

why you would be allowed to do that

[dire obsidian]

screw your prof's method

just follow the method I showed you

sometimes the role of the right side and the left side alternates if your prof is really evil

[weary tiger]

my prof is really sweet

[dire obsidian]

but other than that I really don't know how this doesn't work

[weary tiger]

he goes over things quickly sometimes

[dire obsidian]

but do you get inequality proofs now?

[weary tiger]

okay im gonna try an easier problem with this method

we will see

[dire obsidian]

it's not "I think up of how to sub this"

it's "I want this because the template clearly indicates to me that I need this"
"ok can I force this in via abusing inequality"

the first case is creative

the second case is mechanical

the method I showed you is not creative at all

you literally jsut let the template dictate to you what you need then abuse inequality to force that in

[balmy jay]

@dire obsidian Do you do competitive math

[dire obsidian]

no

[balmy jay]

Oh

Lol was just wondering

[weary tiger]

like what follows next here

[dire obsidian]

force in (k+2)?

[weary tiger]

ok i know that but how

[balmy jay]

Yeah

[dire obsidian]

you literally can do
$2 \cdot (k+1)! < 2 \cdot (k+2)!$

[vital dew]

Salt

[dire obsidian]

then your proof is done

[balmy jay]

Yeah this is just kinda pattern matching

[dire obsidian]

note that you need to have restrictions given for the variable if you want to abuse inequality

[balmy jay]

You see (k + 1)! and you want something in terms of (k + 2)!, just multiply by k + 2

[dire obsidian]

you know this is true because you were given restriction k >= 2

[weary tiger]

my book did 2(k+1)! < (k+2)(k+1)! = (k+2)!

is that the same as what you're saying

[dire obsidian]

yeah

[weary tiger]

okay

[dire obsidian]

this message I am replying to is basically what your book said

[weary tiger]

so doing the right side of the induction is about using the k>= from the ih

to sub in and simplify

?

[dire obsidian]

But i am dumb and stupid so I literally just think
if k>=2
then it is always true that (k+1)! < (k+2)!

so I am free to force that sht in

[weary tiger]

hmm ok

im gonna try one more and then get din

would you mind sticking around a couple mins

[dire obsidian]

k

[weary tiger]

im just completely hitting a brick wall

like I want to multiply the right side by 4 and subtract 3 to get it equivalent to the IS

[dire obsidian]

You knwo what in this case I'd use strong induction

but I kind of forgot how to do strong induction

give me a sec

[weary tiger]

strong induction is the next lesson

and this problem is not in the answer key

[balmy jay]

Strong induction is just: base case is the same, inductive hypothesis is just assuming every case from 1 to k works, and inductive step is using any combination of those k cases to prove the k + 1 case

[dire obsidian]

yeah

the problem with forcing things in rn is

the case 4^0

it's not bigger than 3

if you use strong induction iirc you can bypass that

[weary tiger]

I am going to grab dinner but I will read anything you guys discuss

and will be doing the next lesson tomorrow

[dire obsidian]

wait I'm sorry I need to review this stuff ignore what I said earlier for this question

[weary tiger]

it's okie

the more methods I can use the better cos I am not feeling amazing about this stuff and I have an exam on Thursday

[dire obsidian]

discrete math is fun but pain 😭

[weary tiger]

it is fun when it clicks

[dire obsidian]

yeah

[weary tiger]

if you come up with a solution lmk

[dire obsidian]

yeah I might get stuck on this problem as well XD

[balmy jay]

Is the problem to prove that $1 + 3n \leq 4^{n}$?

[vital dew]

math man

[dire obsidian]

yeah I'm kinda stuck as well

[balmy jay]

Ah ok I might try to solve this in a while

[dire obsidian]

OK wait I think if you deal with the special case when k = 0 for the IS claim then check and prove that is still true (it is because 4=4)

you can just assume k > 0 then do your regular thing of subbing 4^k for 3

[balmy jay]

Yeah you don't need strong induction for this one

[dire obsidian]

yeah I think it's solved now

just needed to explicitly prove via calculating induction step claim for k = 0

then do the rest the usual way

[weary tiger]

hm ok

I'll work this out tmr

ty guys

[dire obsidian]

Yeah mb watch this video to see what antisymmetric is
(indian accent kinda thick but this video explains the concept very well)

https://www.youtube.com/watch?v=t39BW_0eEAA&ab_channel=KNOWLEDGEGATE

[weary tiger]

Okay, thank you for the video suggestion.

[dire obsidian]

I literally just watched it

earlier I also didn't know what antisymmetric is lol

it's certainly not saying "not symmetric" I was clowning when I said that

[spring surge]

I don't get this simple proof. If someone has some intuitions about it lemme know.

[weary tiger]

what is that

[spring surge]

Its from the oldschool book about machine learning.

[weary tiger]

this has nothing to do with connectivity from graph theory or order from number theory does it

is this for a course?

[spring surge]

no it don't

[spring surge]

no its for me.

[weary tiger]

looks pretty advanced

what's the book name

[spring surge]

Marvin Minsky - Perceptrons

[weary tiger]

perceptrons is like old school ML

[spring surge]

Yeah

This proof looks simple. The definition is simple

Like I don't need to understand complex stuff to get it

Still I don't connect the logic flow from axiom to conclusion in both of these pages

[weary tiger]

what's your mathematical background if you dont mind me asking

[spring surge]

university math

for IT sciences

[weary tiger]

nice what kind of math courses have you taken so far

or self studied

[spring surge]

abstract algebra

logic

combinatorics

[weary tiger]

samee

although it was 95% graph theory

[spring surge]

differential calculus

but i suck at it and it aint matter here

[weary tiger]

does this book require abstract algebra knowledge

[spring surge]

don't know anything about them, but thinking about it motivated me to self study combinatorics

no

its just simple logic

basically the books says we have a function which checks if poly is convex

we do that by taking any 3 points

and checking if they make line

and if middle one is not in a poly - its convex

i think i understood my answer

[weary tiger]

i mean that's not all that the book says

[spring surge]

no its only related to my problem

and then it talks about how to check if figure is not connected

if there are two figures on paper instead of one

[weary tiger]

that's just like the notion of connectivity from graph theory

[spring surge]

can you expand?

is there the algoritm which verifies if graph is not connected?

[weary tiger]

there must be

since it's well studied

so if you remove the dashed line the graph becomes disconnected

analogous to you saying there are two figures instead of one (in graph theory we would say there are two disconnected components)

a graph is connected if you can travel from one node to another via edges for any two pair of vertices (if you pulled one vertex by applying a force the whole thing moves)

graphs may be connected or disconnected but every graph is made of components that are connected. You would call them figures ig

[spring surge]

so graph is represented as a set of points?

how do represent connections?

[weary tiger]

set of points plus set of edges

exactly

[spring surge]

so its easy to just bruteforce the way out of the problem

?

[weary tiger]

the connections are represented by unordered pairs of points

[spring surge]

i see

[weary tiger]

yeah i suppose you pick a point, travel to all the points you possibly could, and if at least point isn't travelled to, then the graph is disconnected

[weary tiger]

more formally a graph is denoted by (V,E) where V is the set of points and E is the set of connections

[spring surge]

two sets

[weary tiger]

yup

[spring surge]

i guess graph theory helps you better on visualising systems

like complex frameworks and api's

if you do enough problems to burn the brain

[weary tiger]

graph theory goes beyond literally networks although it's pretty good for representing network like objects where you have some idea of a set of elements and a set of connections between them

for example in your figure the squares could represent vertices and edges exist between pairs of vertices if the squares are in contact

then you could apply an algorithm to see if the graph is connected or not

[spring surge]

applications connecting different math areas are motivating

or seeing how theory could be applied on problem solving

like mine

[weary tiger]

im sure i'll see them again when I take an algorithms course

[weary tiger]

anyone here?

i could use someone to check my work on this problem

[spring surge]

which problem?

[wide vine]

Any tips on finding the longest cycle in a graph?

Is it something you have to brute force?

can't be a because you have no means to get back

[spring surge]

How does line with written with blue pen is justified?

[weary tiger]

i was just adding to turn the left side of the IH into the left side of the IS

it's supposed to be 2k, not 2^k

[spring surge]

oh

[weary tiger]

i wrote it incorrectly

ya

[spring surge]

i think its correct. but i would write it more simple way.

(n^2 + 2n + 1 < 2^n + 2^n)

[ (2n + 1 < 2^n ) and (n^2 < 2^n) ] --> (n^2 + 2n + 1 < 2^n + 2^n)

[wide vine]

When you are applying matrices for relations you apply them in the same order as you would the expression you are interessed in?

in this case

I would make a matrix to represent S and R

lets call them S and R

so then it would be S * R

to get the S o R pairs I want

right?

` a b c d
a 0 1 1 0
b 0 0 0 0
c 1 0 0 1
d 0 0 0 0

S`

` a b c d
a 0 0 0 1
b 0 0 1 0
c 0 1 0 0
d 0 1 0 0

R`

S * R is the correct way to compute this.

I computed it online and it seems correct in that order with what I drew but im not sure

nvm

I think it is R * S

okay yeah it looks like it is

matrix R * matrix S

to get S o R

[hard citrus]

This is a mess

[wide vine]

[hard citrus]

The matrix for the composition SoR is denoted by Mr*Ms, where Mr is the matrix for R and Ms is the matrix for S

[wide vine]

I see

yeah we didn't have anything like that

at least the notation

[hard citrus]

Here's the example from my notes

[wide vine]

we only applied the idea with the idea of graph powers

and those were always the same matrix so I didn't get any notation like this but it makes sense

Anyways, thanks

I knew my notation was a mess as soon as I started tying

[dire obsidian]

I'm confused if the existence of b and c basically nullify any chance of the function being symmetric. I already proved that it can't be antisymmetric via existence of b and c

[weary tiger]

can someone help me with this

im getting very lost

[wide vine]

I know what "symmetric" and "antisymmetric" is but Im confused if the term is used to describe only 1 nodes or the whole graph

because I am asked to answer this quetion

Is it possible to have a relation on a set that is symmetric and antisymmetric? If so, give an example. on the problem set

I would think not if you are speaking about an entire relation

but you could have "local" portions between 2 nodes that are symmetric and 2 other nodes that are anti symmetric

I am going to go with it is describe the relation on a whole and in which case I would say NO.

[hard citrus]

So a symmetric relation is defined as:

if aRb then bRa
and antisymmetric as:
if aRb and bRa then a=b

So it is possible to construct a relation that will be both symmetric and antisymmetric at the same time by 1) making it symmetric and 2) making a=b

[hard citrus]

When we talk about these properties (reflexive, irreflexive, symmetric, asymmetric, antisymmetric and transitive) we look at the whole relation, not just a part of it

[wide vine]

hmm so you mean 1 node?

[hard citrus]

What do you mean by a node

[wide vine]

vetex

vertex

[hard citrus]

Yes

[wide vine]

so 1 vertex that is reflexive

well symmetric I guess would lead to reflexive (in a 1 vertex case)

[hard citrus]

Reflexive is if for all the nodes you have a loop around them

You can have a symmetric relation without it being reflexive though

[wide vine]

sure but I meant if we have 1 vertex

(a,a)

[hard citrus]

Like just relation R={ (a, a)} on the set {a}

Then yes

[hard citrus]

Actually

Vertices are just the points

You mean loops

Cause
R={(a, a)} would have one loop around the vertex a, and if it is constructed under the set A={a} then it will be both reflexive and symmetric but under the set A={a, b} it is not reflexive

[weary tiger]

if anyone has tips i would much appreciate

on the verge of tears rn

[coral parcel]

Shouldn't the 3^k here be 3^(k-2)?

[dire obsidian]

Oh wait tropo is here just ask him

[coral parcel]

If you fix that, it looks like the terms that bother you at the end will cancel each other out.

[weary tiger]

Omg

im gonna cry

thank u

how would I go about for the IS in this question

my P(n): n is odd

I don't know what else to say

like am I supposed to be using the def. of odd integer here?

[coral parcel]

You're supposed to know that the sum of three odd numbers is odd.

If you want something more symbolic than that, then yes, by all means use your definition of odd integer.

[weary tiger]

how does that get me anywhere

I'm just lost

also my prof did this problem in class

and I kind of don't understand how he did that at all tbh

like how can you just sub bk-1 and bk-2 for 4p and 4q

I simply dk what to do

[coral parcel]

How doesn't it give you everything you need:

[weary tiger]

how do I assume that any arbitrary indices are odd

how is that assumption validated

any three arb. indices*

like obv 0, 1, 2 are odd

[coral parcel]

1. You know by definition that b_i is the sum of three particular numbers.
2. The induction hypothesis tells you each of those three particular numbers is odd.
3. You know that the sum of three odd numbers is an odd number.
4. You're asked to prove that b_i is an odd number.
   I'm unable to fathom how this is now not just a matter of connecting the dots in the obvious manner.

The indices are not odd -- but nobody claimed or asked for them to be.

like obv 0, 1, 2 are odd
Neither 0 nor 2 is an odd number.

[weary tiger]

i feel like im missing a step when i assume that every index is an odd number

b_0, b_1, and b_2*

[coral parcel]

Every index is not an odd number.

The indices are 0, 1, 2, 3, 4, 5, ... and only every other of them is odd.

[weary tiger]

i dont mean the index number, i mean the value corresponding

like b_0 = 1, b_1 = 3, b_2 = 1

ok I get it now

ty

[limpid fossil]

how did they get this as the probability of best case?

the best case there is only 1 comparison

the first element 42 or z is empty

[elder berry]

In what you sent, there isn't a mention of 1/(2n) being the probability of best case (which I believe you mean is finding 42 immediately).

Can you clarify what you meant, or give more context?

[weary tiger]

is this valid?

[weary tiger]

nvm

give me a min

ok

if anyone is here

how about now

[limpid fossil]

that was the solution key

[weary tiger]

im literally gonna cry this is way too complicated

like it's time to be a business major

[elder berry]

The probability that you get a list that contains the number 42 is 1/2.

Given a list that contains the number 42, and since it is equally likely for that 42 to be in any position, that means that getting 42 to be in the first place will have the same probability as getting 42 to be in the second, third, or any other place.

There are n such places, so for a single position you would have 1/n chance to get it.
And since we assumed that the list contains that element, the probability is (1/2) * (1/n)

[wide vine]

Im a bit confused how to start this

like (c)

I think I have an answer

but im not sure about the others

actually idk...

[coral parcel]

Each of them is trivial, but in two different ways.

[wide vine]

oh it is just R_3

[coral parcel]

Yes.

[wide vine]

hmm

R_1 o R_2

😕

hold on

[craggy juniper]

not trying to interrupt since you’re getting help so ignore me until you’re done, but what does \circ mean there?

[wide vine]

same thing as

f o g

but with graphs

it is the composition

okay

I think I got it

R_1 o R_2 = {(x,y): x=y or y=x-1}

@coral parcel sorry to ping but does that sound right?

I realized the R_4 I guess is easily as it is the identity

I think this is right now

[fallow zodiac]

Can I get a little help with this problem? If it's a problem of telling me the exact answer could I possibly get a nudge of how to do it?

[crystal dove]

Does the Cayley graph of any finite symmetric group always have a Eulerian path?

[coral parcel]

Consider that for example 29 >= 1 and 1 < 7 ... so you should have (29,7) in R1 o R2.

[coral parcel]

How many paths pass through (30,32). How many pass through both (20,26) and (30,32)? Inclusion-exclusion principle.

[coral parcel]

Yes, every finite group in fact; it doesn't need to be a symmetric group.

[crystal dove]

@coral parcel remarkable!!

[coral parcel]

https://en.wikipedia.org/wiki/Eulerian_path#Hierholzer's_algorithm works to find one.

[crystal dove]

Thanks! I was in fact looking for a practical algorithm, for art purposes

[coral parcel]

I still have no good attack on the Hamiltonian question.

[crystal dove]

No worries, all the forums I posted it in gets no strong recommendations hehe

[dark oyster]

Could you help?

[stray reef]

have you made any progress on this so far or are you stuck not knowing how to begin?

[dark oyster]

I don't know how to prove this

[stray reef]

so that's a "stuck not knowing how to begin"

do you have the definition of a group written out in front of you?

[dark oyster]

yep

[stray reef]

okay

so you know that you need to show + is associative, that it has an identity element, and that every element has an inverse.

do you understand that these are your goals? Y/N

[dark oyster]

Yes

[stray reef]

okay

[dark oyster]

I understood but how can we use in power sets

[stray reef]

would you like to be taken through how to prove (A+B)+C = A+(B+C)?

you can do a proof either by element-chasing or by means of a venn diagram, whichever you prefer (as long as your teacher is okay with the venn diagram)

[dark oyster]

No, he is not okay with Venn diagram unfortunately

[stray reef]

okay then you will have to rely on your knowledge of elementary set theory

and do a somewhat boring and bureaucratic element-chasing proof

[dark oyster]

Yes thank you ı will try

[spring surge]

Can you solve combinatorical problems algebraically or geometrically?

[unreal stump]

I don't see how geometry would be useful at all

[inland rose]

u can

but its stupid and hard to do it geometrically

[unreal stump]

Explain

[broken cradle]

Hi everyone

Is the correct answer 220?
That's how I calculated: (12!) / (9! * 3!) = 220 😄

[austere cedar]

its really depending on the actual combinatorical problem you wan't to solve. Sometimes it helps and sometimes it doesn't work at all. Eg look at the following: show that p choose k is divisible by p for p prime. p choose k is the number of opportunities to color the vertices of a regular p-gon s.t. k are white and p-k are black. You now can use the rotational symmetry of the p-gon to show that always p colorings are the same up to rotation. So the total number of colorings must be divisible by p. Of course this isn't really hard to solve without the geometric approach, but you might get the idea of what you could do

[austere cedar]

what is a skeleton of a graph? I never heard this term before...

[broken cradle]

There must be no cycle in it

So in this case we always take 3 edges out

[austere cedar]

so its the same as a spanning tree?

[broken cradle]

There are a total of 12 edges, there will always be 9 edges (so that there are no cycles in it)

and from that I got this:

(12!) / (9! * 3!)

I don't know, I thought well?

[austere cedar]

12 choose 3 is the number of possibilities to choose any 3 edges, so you also counted the case where the edges ab, bc and cd got removed. I think you don't want to count that

[unreal stump]

Is the answer 36?

[broken cradle]

How did you get it?

[unreal stump]

In the first circled part(abc),you can remove either ac,bc or ab but no two of those at once

That will be 3 possibilities

Similarly 4 for the middle rhombus

And 3 for the last circle(hij part)

[broken cradle]

Yes it can be

[unreal stump]

You can't cut down bridhes

So This has to be the answer

[broken cradle]

Okay thank you very much 😄

[wide vine]

im really not sure how to approach this. is it just R1 o R2 = {(x,y): y<=x}?

i have been drawing it out and not really sure how to work with it just with the inequalities

[coral parcel]

Similarly, since 7 >= 1 and 1 < 29, you should have (7,29) in R1 o R2 too.

[wide vine]

😖 I see it with examples but idk how to do it for an arbitrary number

because at the inbetween stage

you would always have some number (y) < x

(7,y_1) => y_1=x_1 => (x_1, 29)

(7, a) => (a,29)

hmm

a < 7

and

a <= 29

but idk how to relate

the 7 and 29 :/

(x, a) => (a, y)

x > a

a <= y

x > y?

[coral parcel]

Why?

Basically, when you're given an x and y, you need to ask yourself "does there exist a number that is smaller than one of these and also smaller than the other?"

[wide vine]

well isn't that always true

[coral parcel]

Sure looks so to me.

[wide vine]

but how did you get that from it :/

[coral parcel]

How did I get what?

[wide vine]

^

from

[coral parcel]

This

[wide vine]

oh

[coral parcel]

And this

So it seems to me that you have solved the solution when you wrote:

well isn't that always true
and I'm struggling to understand what you think is still missing.

[wide vine]

idk I see what I wrote

but I don't see the relationship with respect between x and y

[coral parcel]

Can you come up with any example of x and y that the relation should not hold between?

Someone gives you and (x,y) and asks you "is this pair an element of R1 o R2?", which we have just agreed is the same as asking "does there exist a number that is smaller than x and also smaller than (or equal to) y?"

I don't understand what you feel is difficult about answering that question.

You already stated the correct answer.

[wide vine]

ohh

a < x and a <= y

I see it now that I wrote it different

okay yeah

[coral parcel]

As you wrote here, yes.

[wide vine]

IK

thanks

[light heath]

guys I have a question. Show that at most a countably infinite number of books can ever be written in English. ( We define a book to be a finite sequence of words, dividied into sentences, paragraphs and chapters) How would one go about solving this problem

[coral parcel]

Do you know that a countable union of finite sets is at most countable?

Or would it help to consider a "book" to be a string over the alphabet {a, b, c, d, ..., x, y, z, space, paragraph break, chapter break}?

(The definition in the problem seems to ask you to disregard punctuation and capitalization.)

[light heath]

wdym so sentences?

[coral parcel]

Oh oops, missed that. Sure, add "period" to the alphabet.

[light heath]

yes but this was my original answer to this question

There is a finite amount of words in the english dictionary. Using these words we can create sentences of a arbitrary size with an infinite amount of word combinations. Books are made out of pages which are numbered. Pages are of an arbitrary size and filled up with sentences which is a infinitely countable set. Then that means we can make an infinite amount of pages which are numbered and have a one to one correspondence to the set of natural numbers meaning that a infinite amount of books can be written in english

my friend said that its infinite but i need to show its countable

by showing a one to one correspondance to the set of natural numbers

but I dont know how too

[coral parcel]

The friend's criticism has merit.

I think the easiest way to argue that the set of all books is countable is to consider each book as a finite string over a common finite alphabet.

Then sort all books according to their length.

Do you agree there are only finitely many books containing, for example, exactly 123,456 symbols?

[light heath]

yea

[coral parcel]

So if you pick some arbitrary order to place all the books of each particular length, there will be some finite number of books (including all possible shorter ones) before any given book in the whole set.

[light heath]

I see but does this show a one to one correspondance to the natural numbers

[dark oyster]

Can you help pls? "A subgroup N of G is called normal if for every n 2 N and g 2 G, gng−1 2 N.
a) Given an arbitrary subgroup H of a group G, is there a largest subgroup of G containing H as a
normal subgroup? Prove your answer.
b) Show that the subgroup K = hfg−1h−1gh j g; h 2 Ggi is a normal subgroup of a group G.

[coral parcel]

Map each book to the number that tells how many books there are in front of it.

[light heath]

ok

[coral parcel]

Why on earth are you typing the set membership symbol as the number 2?

I've seen people type "e" and "E" and "in" and "\in" and "ε" and even one time a Euro symbol, but "2"??

[stray reef]

i think this is bad pasting

[dark oyster]

Ahahahsah I have just copy-paste. I already took a screenshot when I noticed the 2

[dark oyster]

yep

[coral parcel]

Okay.

Seems a bit harsh to make these two properties your first introduction to normal subgroups.

For (a) you might look for a condition on elements of G that means "there is no way this element can be in any H that contains N as a normal subgroup", and then hope that the set of everything that does not have this property turns out to be a subgroup.

For (b) it's more or less a follow-your-nose proof, except the definitions you need to unfold are fairly complex and the same variable letters are used for different thing in each of them - so there's a risk of getting confused by all the details. At least, that is, once you're familiar with the fact that that $gxyg^{-1}=(gxg^{-1})(gyg^{-1})$ and $gx^{-1}g^{-1}=(gxg^{-1})^{-1}$.

[vital dew]

Troposphere

[limpid fossil]

but then doesnt this give the possibly 42 is at the end of the list? and then it wont be best case