#discrete-math

1 messages · Page 136 of 1

maiden fractal
#

When L = 3.

Bucket 1: 000

Bucket 2: 001

Bucket 3: 011

If we want to match bucket 1, we can use the selection tag of 000.

If we want to match buckets 1 and 2, we can use the selection tag of 00%

If we want to match buckets 1, 2 and 3, we can use the selection tag of 0%%

This is the best I can think of so far.

Is there a way I can prove that we can do no better than L = B? Or is there actually a way to achieve a better B, given length L? I should add that the alphabet can be arbitrarily large, however I've found this makes no difference to the cumulative matched buckets B, however I could be wrong on this point.

I'm at a loss on how I can improve this solution. Any help would be appreciated.

last timber
#

is task to find the biggest set such that each element in set is labeled identically up to L's letter or at least one * before L's letter?

maiden fractal
#

Its to create a way to tag buckets, such that you can have unique selection tags to match the maximum amount of buckets from 1..B (cumulatively)

#

E.g. a B of 3, would mean you can match (1), or (1 and 2), or (1,2 and 3)

#

So I believe the answer is the former.

#

The existence of "*" is something that I havent incorporated into any solutions yet, but it's part of the problem. Not sure if it's actually useful. Since this is a real-life problem, that I'm trying to solve with maths.

last timber
#

wait unique selection tags

maiden fractal
#

The selection tags will naturally be unique, since no same selection tag can select different combinations of buckets.

last timber
#

then largest set will be tagging by diagonal each letter by *

maiden fractal
#

Can you explain?

last timber
#

like *abc
a*bc
ab*c
abc*

maiden fractal
#

We need to also be able to select the buckets before the maximum. So like, let's say I have buckets tagged as following.

#

Bucket 1: 000

Bucket 2: 001

Bucket 3: 011

#

If I use selection tag: 000, I only select bucket 1

#

If I use selection tag: 00%, I select buckets 1 and 2

#

and tag: 0%%, I select all 3 buckets.

last timber
#

wait, i am lost
are buckets pretagged or what?

maiden fractal
#

The goal is to create the scheme.

#

E.g. you can choose how to tag the buckets.

#

But the goal is to choose a way to tag the buckets that means you maximize B.

last timber
#

so let me restate the problem
we are given N objects.
We can label them by strings from some alphabet
two objects can be matched if they have identitcal letter up to some letter a_L
if some letter is *, then all letters after it are identitcal to any other string

The task is to label them the way that any search tag gives maximal possible set?

maiden fractal
#

If some letter is *, then all letters after it are matched.

#

If the letter is %, then any single letter is matched.

#

Hmmm, I'm not sure what's the best way to explain the value that we want to maximize B.

#

E.g. if B = 3

last timber
#

wdym by any single letter

maiden fractal
#

That means we can match objects 1, (1 and 2), and (1, 2 and 3) with three different selection tags.

#

E.g. 2 objects with tags "abcz" and "abxz"

#

the selection tag "ab%z" will match both

last timber
#

like 12*712313 = 12*7313313
12%712313 = 12%612313
but 12%712313 != 12%6242313

#

?

maiden fractal
#

"*" and "%" aren't part of the tags of the objects.

#

But just part of the selection tag, that you can use to match them.

last timber
#

oh i now like got it

maiden fractal
#

Sorry about that.

#

Not a great initial explanation...

last timber
#

if i use tag a% search ignores symbol after a but not ignores other symbols

maiden fractal
#

correct

#

there's also a search tag symbol * that will just match basically everything e.g. "ab*" will match anything that starts with "ab"

last timber
#

The task is to label them the way that any search tag gives maximal possible set?

mhm

#

i think in such a statement it is not polynomial

maiden fractal
#

yeah im not convinced that its possible to do better than the length of the alphabet.

#

but, i'd like to prove that if possible.

rich depot
#

I find it confusing 🥶

#

It's a theorem formed from the mating ritual problem

maiden fractal
#

is that similar to the stable matching problem?

rich depot
#

Yes

last timber
#

yeah im not convinced that its possible to do better than the length of the alphabet.
@maiden fractal prolly labeling each object identically up to later string is the way

#

later symbol*

#

like abc
abd
abe

maiden fractal
#

you'd need tags to select 1 object, 2 objects and 3 objects.

#

if you could find a tagging scheme, where the length of the tag is 3.

#

and you could select 1 object, 2 objects, 3 objects and 4 objects.

#

that would be better than anything i've come up with

last timber
#

wait

#

what do u want

#

u want maximal possible set

#

?

maiden fractal
#

lets say we have a tagging scheme for 3 objects

#

object 1
object 2
object 3

#

each with some tags

last timber
#

or u want maximal possible set of strings matched up to L where L is known before?

#

or u want maxible possible set of strings matched up to L where L is unknown?

maiden fractal
#

L is semi-arbitrary, since we want the maximal relative to L, but in reality L is 6

#

but its a bit easier to reason with 3

last timber
#

if L is known before - label all strings identically up to element L-1

maiden fractal
#

we need to also be able to select each set of objects from 1 to B

#

e.g. for B = 3

#

it means that we have selection tags for selecting just (object 1), just objects (1 and 2), just objects (1, 2 and 3)

#

an example of such a scheme:

#

Object 1: 000
Object 2: 001
Object 3: 011
If I use selection tag: 000, I only select bucket 1
If I use selection tag: 00%, I select buckets 1 and 2
and tag: 0%%, I select all 3 buckets.

last timber
#

mhm

#

reee

maiden fractal
#

yeah, its not a homework problem..., optimal answer might be pretty shit

#

like for context, the tag is meant to be a regex, but the other party fucked up the implementation of the "*" character, so im stuck trying to solve this.

obtuse minnow
#

I think the assumption that the "optimal" choice is a "positive" choice for either the world or the couple is ... flawed ...

#

In parallel there is currently SO MUCH PRESSURE to go to college and not everyone benefits from the results: sometimes there's a lot of student debt or mishaps because during college years the student didn't have health insurance, etc. I dunno. I love smart people and college and I would like to believe it is for everyone ... but ...

astral ruin
weary tiger
#

If A = (0,2) and B = [0,2] How can I determine which number is in the cartesian product?

A x B = (0,0), (0,2), (2,0) and (2,2)

However, not all numbers can possible be inside of it. Because B = [0,2]

stray reef
#

A × B contains way more than just four points

weary tiger
#

oh yeah xD

weary tiger
#

but could you at least tell me how I should handle open and closed intervals in cartesian products?

rain stone
#

@weary tiger review the definition of cartesian product, and remember that (0, 2) contains neither 0 nor 2

plucky gulch
#

Hi, I have a question (don't know if it's supposed to go here, given that it's from my algebra course, but it is far too elementary for posting it to algebra I'd say): Given two natural numbers a, b, I understand that <a, b> = <(a, b)> (i. e. the subgroup of (Z, +) generated by a and b is the same subgroup as the one generated by their gcd. Now, the question is, how do we find a generator for the subgroup of (Z_n, +) generated by [a]_n, [b]_n? The solutions manual just states that we “use Bèzout's identity, the generator is given by (a, b, n)”, but I can't really see how this works - mainly, I don't quite see how that n appears in the identity.

weary tiger
#

Ok, Dre

#

Are you in a class?

velvet junco
#

Yes

weary tiger
#

What is the material you are on?

velvet junco
#

We're currently studying strong induction

weary tiger
#

How many sections are there in this class?

#

Probably logic, proof, number theory

#

right?

#

Did you do anything on congruence?

#

Or

#

Least Common Multiple?

velvet junco
#

oh wow smh okay i see where this is going

#

but to answer your question yes

serene garnet
#

In the non-zero integers mod 7 over multiplcation, why is 3 a generator if it isn't coprime with the order (which is 6)?

obtuse lance
#

what's the name of the theorem that says they must be coprime

#

3 and 7 have to be coprime, maybe you're thinking of this?

serene garnet
#

there's nothing that explicitly states they must be coprime, it seemed like it was a byproduct of Lagrange's Theorem but apparently it's not and only works when the binary operator is addition

stray reef
#

you don't care about the coprimality of 3 and the order of the MULTIPLICATIVE group of the nonzero integers mod 7

obtuse minnow
#

@serene garnet the powers of 3 (mod 7) are 3, 2, 6, 4, 5, 1

#

Because I almost made a mistake, I'm wondering this also:
( a, a^2, a^4, a^8, ... ) <-- can this pattern generate mod p for p > 5

vital dewBOT
weary tiger
#

@stray reef can you help me

stray reef
#

maybe

weary tiger
#

if we have 4 X's, 4 Y's, 4 Z's

#

and we need to make a 12 letter word out of those letters

#

then how many words can we make where we don't have any X's in the first 4 letters

stray reef
#

hm

#

give me some time to think about this

#

ah yes of course.

#

C(8,4)^2

weary tiger
#

don't say of course

stray reef
#

pick 4 places for the X's out of the 8 they can occupy, then 4 out of the remaining 8 for the Y's

#

the Z's will fill the remaining 4 places.

weary tiger
#

i need to die

#

im just so stupid when i didn't think of that

#

what is the point of life

stray reef
#

bruh

#

if you're feeling suicidal go get a therapist seriously

weary tiger
#

no money

#

also

#

this only happens when i work on a math problem for a while

#

and can't figure it out

#

and then someone can figure it out in 1 min

stray reef
#

i'm not qualified to provide mental help.

weary tiger
#

or less

stray reef
#

all i can say is that you should not compare yourself to others

#

bc this thought pattern of "someone else is better than me => life is pointless and i should die" is toxic

#

you should definitely not compare yourself to me

#

like so what if i solved a problem in 2 minutes that you attacked for hours and still couldn't solve

#

that's like saying "this high-level monster nearly killed me but this guy who's 30 levels above me killed it in a few hits! life is pointless"

weary tiger
#

well i don't need to compare myself to you, but look at for example gauss. he derived the sum of an arithmetic progression formula when he was 8 years old

stray reef
#

gauss?

#

of all people, gauss is not someone you should compare yourself to.

#

gauss is an outlier

#

he would dwarf a lot of people in terms of mathematical power

obtuse minnow
#

He's the best player of his century ... more Michael Jordan-like.

rain stone
#

Literally everyone who has completed a Math PHD has solved a problem/answered a question nobody else ever has. They aren’t all Gauss

vestal moth
#

i am gauss

last timber
#

i am euler

sleek swallow
#

I am wheeler

last timber
#

say it to ur mom

sleek swallow
#

destroyed

rain stone
#

@weary tiger I talked with one of my profs recently about research and he said the primary quality it took was a work ethic. Even the most brilliant students need to grind to get research done.

Math isn’t just a test of “sit down and solve a problem”. Yes, you need to have good logical and creative skills, but you also need to be able to ask for help, you need to be able to learn from what doesn’t work, you need to be able to grind through 6 months of failing, etc. These are skills you learn over a long period, they don’t appear in a day, and they’re what allow you to do research

#

You aren’t going to be locked in a glass box and asked to solve a problem

#

It’s a dynamic process that involves other people, a ton of resources, and getting it wrong over the long term

#

Competition questions are fun, but they aren’t a good simulation of that

last timber
#

math is about making errors and pretending that it is planned so

weary tiger
tardy pike
#

I got an = 5^n + 4n^2

#

Not sure if that's right

delicate ridge
#

@tardy pike you can substitute in

#

to check a proposed solution

#

$a_{n-1} = 5^{n-1} + 4(n-1)^2$

vital dewBOT
delicate ridge
#

(if we assume that your answer is correct)

#

subbing that into the recurrence relation

#

we get $a_n = 5(5^{n-1} + 4(n-1)^2) + 4n^2$

vital dewBOT
delicate ridge
#

so $a_n = 5^n + 24n^2 - 40n +20$

vital dewBOT
delicate ridge
#

which doesn't fit your proposed solution

tardy pike
#

In order to get the homogeneous solution we ignore the function term right? So 4n^2 is ignored.

delicate ridge
#

idk what the homogeneous solution means, but the "complementary function" is the one obtained by considering $a_n = 5a_{n-1}$

vital dewBOT
tardy pike
#

Alright, I appreciate it!

delicate ridge
#

and then the particular solution will be something of the form pn^2 + qn + r

#

where you'll need to determine those constants

#

(p, q and r)

weary tiger
#

@weary tiger you figure it out?

weary tiger
#

@weary tiger no

compact shell
#

ϕ⊂{ϕ}, True or False?

stray reef
#

is ϕ meant to denote the empty set?

compact shell
#

Yes

stray reef
#

the empty set is a subset of anything.

compact shell
#

So it will be true?

#

Isnt it an element of the other set?

stray reef
#

it is possible for $x \in A$ and $x \subseteq A$ to be true at the same time.

vital dewBOT
compact shell
#

Nope

#

Okay so empty set is a subset of all the sets.

stray reef
#

Nope
what

delicate ridge
#

hmmmmmm

sleek swallow
#

Nope
@compact shell Let $A = {\varnothing}$. Then, obviously, $\varnothing \in A$. Since the empty set is a subset of all sets, it follows that $\varnothing \subset A$.

vital dewBOT
sleek swallow
#

You can prove quite easily that the empty set is a subset of all sets so that’s just something you should be aware of. Try proving it on your own.

last timber
#

well i am unsure if it correct

#

but informally since intersection of sets A and B is set of elements both in A and B

#

and intersection of disjoint sets is empty set so like here we go

#

but more formal proof is based on another construction

rain stone
#

I mean you can also have like

#

$A = {1, {1}}$
Then ${1} \in A$ and ${1} \subset A$

vital dewBOT
shut fjord
#

Suppose there are 9 cups of bubble tea. I can choose from milk tea, green tea, or thai tea. How many ways to buy these 9 cups if I will still have 3 green tea after dropping 2 of the 9 cups on the way home?

#

So far I got that this is a combinations problem and we are guaranteed to have 3 of the 9 items as green tea.

#

which leaves 6 of the remaining items to be any of the above 3 options

#

but then I get tripped up after 2 items are dropped.

#

Would this mean I should only count the leftover items that can be any of the 3 options (3 are guranteed green tea, 4 can be any). Or do I consider ALL combinations (the 3 guranteed green tea, 6 can be any of the 3 options) then subtract out the 2 that are dropped?

#

i got 11

errant bear
#

Suppose there are 9 cups of bubble tea. I can choose from milk tea, green tea, or thai tea. How many ways to buy these 9 cups if I will still have 3 green tea after dropping 2 of the 9 cups on the way home?
is this the exact question

shut fjord
#

yes

lyric pumice
#

Verbatim?

#

@shut fjord

sleek swallow
#

but more formal proof is based on another construction
@last timber ?

shut fjord
#

yeah* @lyric pumice

stoic hearth
#

does "the subset of all its sets" and "the set of its subsets" mean the same?

stray reef
#

no

stoic hearth
#

the former is subset that is shared between sets? fishthonk

#

Wherein it seems appropiate to state that if $X=\mathcal{P} (M)$ is the set of the subsets of M, then $M={X}$ is also the same as $M={\mathcal{P}(M)}$

vital dewBOT
stoic hearth
#

or am I wrong because of thinking that $X$ and $\mathcal{P}(M)$ are two ways of expressing the same set

vital dewBOT
sleek swallow
#

Let $M$ be a set. Let $X = P(M)$. The only reason why he has called it $X$ is because he's lazy to write out $P(M)$ whenever he's talking about the powerset of $M$.

vital dewBOT
stoic hearth
#

then my first assumption applies

sleek swallow
#

Also, not really sure what you mean when you say that:

$$M = {X} = {P(M)}$$

Not very sure what you're going for over here.

vital dewBOT
stoic hearth
#

if $M$ is the set and $X$ is the set of it's subsets, if $X=\mathcal{P}(M)$ then another way of saying the same is that $\mathcal{P}(M)$ is the set of the subsets of $M$

vital dewBOT
stoic hearth
#

or should it be $M={{X}}$

vital dewBOT
sleek swallow
#

Yea, that's correct. Usually, though, $\mathcal{P}(M)$ is the standard notation for the powerset of $M$. So, we usually start by saying "Consider the powerset of $M$, denoted by $\mathcal{P}(M)$. If $X$ is the set of all subsets of $M$, then $X = \mathcal{P}(M)$."

vital dewBOT
sleek swallow
#

But that's super convoluted and unnecessary lol.

stoic hearth
#

and what Zorich did seems like

#

or should it be $M={{X}}$
nvm that's incorrect

sleek swallow
#

I don't really think that's what Zorich has done haha, just have a read through

stoic hearth
#

dunno it looks like that's exactly what the first sentence is trying to say

sleek swallow
#

Yeap, it is.

stoic hearth
#

okay

#

also does any of this go in #discrete-math ? Having a look at earlier messages it seemed similar to me

sleek swallow
#

Well, I don't know lol. Set theory isn't really covered in my discrete math course but i suppose it can come in here

#

we've answered questions of that kind in here haha

#

Basically, someone will tell you if your question is out of place

stoic hearth
#

alright thank you

open rampart
#

can anyone help me w this question

sleek swallow
serene basalt
#

for (a) use fermats little theorem

#

(b) seems false?

open rampart
#

Using Fermat's would u get q(x) = 0? How would I express it as a bunch of degree one polynomials

fluid verge
#

For all elements $\a\in\text{GF}(p)$ in that finite field, you have $q(x)=0$, therefore

$x^p-x=\prod_{\a\in\text{GF}(p)}(x-\a)$

vital dewBOT
loud copper
#

dude wtf

fluid verge
#

For two, just use lagrange's theorem

loud copper
#

WHAT THE FUCK IS THAT FONT

fluid verge
#

shh

#

shhhh

loud copper
#

i gotta leave before i get violent

fluid verge
#

punish me daddio!

stray reef
#

okay

fluid verge
#

not you

last timber
#

okay

open rampart
#

tyyy @fluid verge

foggy hatch
#

That font is like "script but the ts aren't crossed", which is freaking me out

weary tiger
#

where can i find examples on making a proper proof sequence

rain stone
#

wdym by "proof sequence"

serene garnet
#

@stray reef Sorry to reference the old question but this is about the question of coprimality of 3 and the order of Z7. I found a theorem which states: "For each divisor d of n the number of elements x in G which have order d is phi(d)." If this is applied to the multiplicative group of a finite field like Z7, the number of elements which have order 7-1 must be the number of elements that are coprime with 6. So why is [3] a generator of Z7?

stray reef
#

uh

#

Z7* is cyclic and it has phi(6) = 2 generators, namely [3] and [5]

#

phi(d) just COUNTS the elements

#

[3] is a generator of Z7* for the very simple reason that its successive powers in Z7* are [1], [3], [2], [6], [4] and [5]

serene garnet
#

oh and because 1 is obviously coprime with d then there needs to exist some generator that is not coprime with d

#

that makes much more sense ty

vapid light
#

@open rampart are you in cs70?

open rampart
#

@vapid light lol yupp

vapid light
#

damn

#

good luck dude

#

hated that class lmao

open rampart
#

yee i hate it too ;-; but thanks dude

vapid light
#

at least you dont have stable matching

#

thats a win in my book

bright ether
#

Can anyone give a hint about Question 15 and 20

finite rose
#

@bright ether for question 15, notice that H={a| a^12 = e}

bright ether
#

Yes then ?

finite rose
#

you need to show H is a subgroup of G

#

how do you show something is a subgroup

bright ether
#

Like first take a and b

#

And but what is order of (a.b)

finite rose
#

use my hint

#

you don't need to know the order of ab

#

all you have to do is show that ab is in H

#

i.e. (ab)^12 = e

bright ether
#

Ok done

#

For any positive integer another than 12 , also proof is valid

#

?

finite rose
#

is it?

#

what do you think?

bright ether
#

Yes I think

finite rose
#

by the way, you also need to show that H is closed under inverses

#

to show H is a subgroup

bright ether
#

Yes I showed it

finite rose
#

good

#

yes, the proof works for any integer

bright ether
#

Ohk for Question 20?

finite rose
#

what have you tried for this question?

bright ether
#

I am not getting how to start

#

Like it has 35 elements

vital dewBOT
finite rose
#

are you familiar with Lagrange's theorem?

#

one consequence of it is that every element of a finite group has order dividing the order of the group

#

35 = 5*7

bright ether
#

Language theorem I didn't read it till now.

#

I am doing from Joseph a gallian book

finite rose
#

Lagrange, not language

bright ether
#

Oh okk

#

Typing mistake

#

Thanks to both of yoy

#

Any other option for Question 20 other than lagrange ?

finite rose
#

if a has order 5, b has order 7, then ab has order 35

last timber
#

My suggestiong you have to check

#

I have just given example of some chain of subgroups

bright ether
#

Ohk I will check

#

Then reply

last timber
#

For 17 it is pretty easy

bright ether
#

Icosahedron...ok that is from Lagrange theorem right ?

finite rose
#

no

#

it's more elementary

last timber
#

18 is also trivial

bright ether
#

17 I am not getting also

#

18 is done

finite rose
#

we're talking about question 20 now

#

@last timber

#

every element of G has order 1, 5, 7, or 35

bright ether
#

This point I don't get , how?

#

How can we find elements order from order of group

#

It is divisor of 35?

finite rose
#

every element x satisfies x^35 = e, this is given

#

so the order must divide 35

#

because if it didn't we could write 35 = a *|x| + b, with 1<=|b|< |x|

#

and then x^35 = x^(a*|x| + b) = (x^|x|)^a + x^b = x^b = e

bright ether
#

Ohk got it ,

finite rose
#

so the order is actually smaller than |x|

bright ether
#

So we know order of elements.

#

So how g is cyclic by it

finite rose
#

there are probably more ways to do it (there are more advanced theorems that pretty much give this directly)

#

but at an elementary level, here's how I would do it

#

if G has an element of order 35, we're done

#

otherwise, every element that's not e has order 5 or 7

#

if we had distinct elements a,b with different orders, then ab would have order 35, so we're done

#

otherwise assume every element has order 5

#

then every element generates a subgroup of order 5 and these subgroups without the identity partition G\{e}

#

so we would need 4| 35-1

#

but this is false

#

so we can't have that every element has order 5

bright ether
#

Ok

finite rose
#

similar argument shows that it's impossible for every element to have order 7, since 6 does not divide 34

#

is the argument clear?

bright ether
#

Yes got it completely. But this argument you made at last for 5 and 7 element , it is in which chapter ?

finite rose
#

no idea, I haven't read the book

#

are you referring to the fact that if a has order 5, b 7, then ab has order 35?

#

we know that (ab)^35 = e, so the order of ab divides 35

#

so it's either 5 or 7 or 35

#

it can't be 5 or 7

#

hence it's 35

bright ether
#

Yes that I got it

finite rose
#

does this argument work for 33?

#

what do you think?

bright ether
#

Yes ,but elements can have order 11 and 3

#

So that 11.3 = 33

last timber
#

btw what is the book

#

is it gallian

bright ether
#

Joseph a gallian

#

Yes

finite rose
#

@bright ether the proof as I gave it doesn't work for 33

#

perhaps you misunderstood the proof

bright ether
#

Why but if a has order 11 and b has order 3 then ab has order 33.

sour arrow
#

Try a simple group. Z/2Z.
1 + 1 = 0
1 has order 2, 0 has order 1.

#

It is true that the order of ab will divide |a||b|

finite rose
#

@bright ether that's correct but this is not the problem

#

the problem is showing the impossibility of all elements having order 3 or order 11

#

there are ways to modify the proof to make it work though. For example, you can show that if three different elements have order three, then G contains a subgroup of order 9, contradicting Lagrange's theorem

bright ether
#

Ohkkk

weary tiger
#

Im unsure if This is correct as the slader guide did it another way by reducing the mods first. If possible can someone give this a look? Answer from slader is 23mod30. Cant check book either bc evens 😐

📎 image0.jpg
#

Mod is definitely correct as 61015=900

#

I follow step by step for chinese thrm not sure how to check

errant bear
#

you need to break up each of the three original equations into modulo p

#

@weary tiger

weary tiger
#

Wait what do you mean

#

Sorry not familiar with terminology yet

errant bear
#

is 10 a prime number

weary tiger
#

I think (6^-1)8 is 8 because 63= remainder 8

#

No

#

OH wait

errant bear
#

so there isnt just 1 inverse

#

infact that means there isnt an inverse

weary tiger
#

So I would have to find congruent prime modulo equation equivalent

#

Then preform chinese thm

errant bear
#

uh

#

you need to break the equation y=3mod 10 into 2 equations

#

where the mod is prime

#

same w 15

weary tiger
#

I see 1mod2 2mod3 3mod5

#

Slader man no give description of this but this is what he do

#

I see him break down into smaller and calc the 3 distinct congruences and get to his answer

errant bear
#

mmhm

weary tiger
#

catthumbsup catLove thank you friend

errant bear
#

like, 6x=8 mod 10 doesnt mean x=3mod 10

#

as x=8 gives 48, which satisfies

#

so you pretty much always have to make sure that when combining equations, that the moduli are coprime

weary tiger
#

How would you mult 6^-1 to other side? When 6* 6^-1 cancel on x side

errant bear
#

you cant

#

you can only multiply 6^-1 on both sides when working mod p

#

for p prime

weary tiger
#

Ok given a prime how would you mult the side for example 6x=1mod7

#

6^-1 * 1 mod7 gives 6 mod7not sure how

errant bear
#

yes

#

6 is 6's own inverse modulo 7

#

to find the inverse of n mod p you find the x such xn=1mod p

#

it can take a while, fo larger values of p

#

5^-1 mod 7 is = 3, as 5x3=15=1 mod 7

weary tiger
#

I see now thank you 🙏🏼

errant bear
weary tiger
#

Prof no explain how he do this sadcat

errant bear
#

also theres an easier way to solve these systems of diophantine equations, my phones about to die, but ill send the formula in a bit

weary tiger
#

Sounds good! Look forward to it

marble pivot
#

Is finding primitive roots mod p (for p prime) trivial for a computer

sour arrow
#

Yes

marble pivot
#

Well, is there a fast algorithm I guess

#

Like is it worth it to try to improve the current algorithm @worthy palm

flat oracle
#

Can i ask a practice homework question here?

stray reef
#

yes but we won't just do them for you

flat oracle
#

sweet thx and that makes complete sense

#

so very basic question just a week into my discrete math course

#

But is that right ? Or is there another way to do this?

stray reef
#

i...

#

this is like 3 times longer than it needs to be

#

even if we word the negation as they did and not as "for any integers x, y > 2, if x and y are prime then x^2+y^2 isn't"

#

you could just say

#

"if at least one of x and y isn't prime, we're done. if they're both prime, then they're both odd, and thus so are x^2 and y^2, and so x^2+y^2 is even as the sum of two odd numbers. and since it's larger than 8 it cannot be prime as it has 2 as a factor."

#

tho i suppose if it's week 1 it might help to be extra thorough about this stuff so idk!

#

@flat oracle basically the logic is airtight and the only issues with this thing are stylistic

flat oracle
#

tho i suppose if it's week 1 it might help to be extra thorough about this stuff so idk!
@stray reef yeah my prof was super thorough during lectures and expects alot of description

#

"if at least one of x and y isn't prime, we're done. if they're both prime, then they're both odd, and thus so are x^2 and y^2, and so x^2+y^2 is even as the sum of two odd numbers. and since it's larger than 8 it cannot be prime as it has 2 as a factor."
@stray reef yeah i was gonna say that till i saw a TA walk thru a practice problem kinda similar and his was as detailed as above and he said thats what the prof expects for this first assignment

#

but that makes alot of sense. thx a million for the feedback!

marble pivot
#

@worthy palm alright. I guess what I'm getting at is, would it make sense for someone to try to improve the current algorithm for finding primitive roots, or is it already fast enough and it wouldn't make a difference if it was faster

bright ether
#

Can we find GCD of any positive integer n and -1.

#

?

obtuse lance
#

yeah 1

bright ether
#

How ?

#

N = -1× -n
And -1 = -1×1 . So ans = -1 , am I right by this method?

#

Ans can be 1 also like,. n = 1×n.
-1= 1 × -1 .

rain stone
#

gcd stands for greatest common divisor

#

last time I checked, -1 < 1 ;P

bright ether
#

Oh ok got it

weary tiger
#

If I solve a modulo x for example 5x=2(mod 3), x=1 satisfies. How would I find ALL the ints that satisfy

errant bear
#

you did

#

the equivalance class formed by x=1mod(3) is every solution

#

[1] or 1 with the overline

#

same thing

weary tiger
#

this would not work for all prime modulo right

errant bear
#

no, in fact it will and must

weary tiger
#

whaaaat thats crazy

#

I like math

errant bear
#

you should try like mod 13, just to "confirm" this

#

but you dont want to go overboard because itl take a while for larger p

#

oh yeah i forgot ab the method gimme a bit

#

from last night

weary tiger
#

yeah I remember

naive saffron
#

If gcd(a,n)=1, then the congruence ax=b (mod n) has a unique solution modulo n

#

If gcd(a,n)=d, then the congruence ax=b (mod n) has a solution iff d | b, in which case there are d solutions modulo n

weary tiger
#

I see now, so much clearer !

#

very interesting

errant bear
#

oh yeah also, you should be able to prove that if the modulus is prime, then there will only be one solution to ax = b mod p

weary tiger
#

if I find the inverse x and mult by b to find a satisfying answer, but p is not prime would it still be unique since gcd(a,n)=1?

#

clearer: if p is not prime, will a satisfying x still be unique

errant bear
#

well last night we saw this wasnt the case with mod 10

weary tiger
#

you are right I will look into this

naive saffron
#

2x=0 (mod 10) has two solutions because gcd(2,10)≠1

#

well two solutions mod 10

weary tiger
#

How would I go about finding all X for a ax=bmod p where p is not prime

#

not sure because I found a satisfying x but since it is not prime I am sure there are other solution

errant bear
#

you need to break p into its prime factors so it varies

#

and you shouldnt use p if it isnt prime btw lol

weary tiger
#

oh sorry! haha

#

I break it into p prime modulos and try some options

#

thank you for help all

errant bear
naive saffron
#

Wow

#

No no no

#

When solving for linear congruence you don’t need to factorize it

#

To solve ax=b (mod n), just find the multiplicative inverse of a mod n

#

The way to do that is using Euclidean algorithm

weary tiger
#

can I prove that the solution for x in ax=b(modn) is unique by proving that with ax=b(modp) ax=b(modp) where p*p=n

#

so an x that solves ax=b(mod 15) is unique if it also solves ax=b(mod5) and ax=b(mod 3) since 5,3 prime

naive saffron
#

No

#

The solution for ax=b (mod 15) is unique means that if x and y are solutions then x=y (mod 15)

weary tiger
#

for the case of ax=b(modn) how would I show all int x that satisfy.

#

if I find a satisfying x how would I prove that there is/isnt any more xs' that satisfy

naive saffron
#

If gcd(a,n)=1 then ax=b (mod n) has a solution and is unique

#

If gcd(a,n)=d, then ax=b (mod n) has a solution if d divides b. If that's the case, then you can solve (a/d)x = b/d (mod n/d), and this equation will have a unique solution x_0 between 0 and n/d-1, then all the solutions for ax=b (mod n) will be give by x_0 + t(n/d) where t=0,1,2,...,d-1

weary tiger
#

I see this is much more clear! Thank you all ! ! ! pandaWow

naive saffron
#

Do you know how to solve ax=b (mod n) when gcd(a,n)=1 tho?

weary tiger
#

yes I use Euclidean algorithm to find x multiple and check

#

I receive correct answer ax=1(modn)

naive saffron
#

Use Euclidean algorithm to find c,d such that ac + nd = 1, then ac = 1 (mod n), so x = (ac)x = c(ax)= cb (mod n)

weary tiger
#

I do, is perfect ! found the x that satisfies all those conditions, therefore it must be solution and unique

naive saffron
#

Well you haven't really proved that these are all the solutions

#

Neither did I

#

I just told you that these are all the solutions xD

weary tiger
#

LMAOO

#

If gcd(a,n)=1 then ax=b (mod n) has a solution and is unique

#

this is theorem I use, will check book to see if correct with my answer

naive saffron
#

Lol

#

It's not a definition

#

It's a theorem

weary tiger
#

haha I change

#

just curious— what is ‘mod’ and how is it used?

#

calculates remainder

#

5 mod 4=1

#

1/4 is remainder

#

O

naive saffron
#

In this case it means something else lol

#

a = b (mod n) means that n divides (a-b)

weary tiger
#

o

naive saffron
#

As an operator, a mod b usually means the remainder of a when divided by b

#

But when we write (mod n) after a triple line equal sign, we mean the definition I gave above

weary tiger
#

Ok

errant bear
#

whoever wdym

#

To solve ax=b (mod n), just find the multiplicative inverse of a mod n

#

you cant just do this thonk

naive saffron
#

Well

#

After finding the multiplicative inverse it’s very easy

#

You just multiply both sides by the multiplicative inverse

errant bear
#

huh

marble pivot
#

Thank you viburnum

errant bear
#

whats the inverse of 2 mod 4

marble pivot
#

uhhhh

#

I don't think it has an inverse ?

#

cause 4k + 1 is always odd, and any multiple of 2 is even

naive saffron
#

Lol

#

My complete sentence was

#

“If gcd(a,n)=1, then ax=b (mod n) has a unique solution. To find this solution, just find the multiplicative inverse of a”

marble pivot
#

oh lol, yeah they have to be coprime

errant bear
#

you never said that

marble pivot
errant bear
#

that was like 2 paragraphs later

naive saffron
#

Bruh

#

Ok yes

marble pivot
#

well yeah, he was clarifying

naive saffron
#

For that specific sentence it wasn’t quite right

errant bear
#

and thats what i saw

#

so

#

whoever=loser confirmed

#

qed

marble pivot
#

nice

naive saffron
#

...

marble pivot
#

@worthy palm ok this might sound really dumb, but I'm trying to a research project in cryptography and I have no idea what topic to do... I was gonna try primitive roots, or discrete log algorithms or something

#

They're all so complex though, they just turn into a bunch of computational complexity theory and elliptic curve crypto and it's so hard

#

That's tough

#

Yeah I was not aware how much math was in cryptography lol

#

Is there any topic that I might be able to do for a research project involving math? It seems like anything involving math is already well studied and all the "new" problems are much higher level

#

Haha well

#

I'm in a summer program for research, and they let you do any topic

#

I'm still trying to find a topic

#

Ok

#

@worthy palm I have a pretty good background in number theory, and a lot of time, but yyou're sure it would not be a good idea to try to do research in cryptocraphy

#

Sorry for the pings lol

marble pivot
#

Sorry this is probably really annoying for you lol

#

Alright

#

Ok lol

green crystal
#

how can i ascertain if a graph is non-planar computationally

pallid lintel
#

what do you mean computationally

#

i guess there could be an algorithm for checking K_5 subdivisions and K3,3

cloud horizon
#

yo

#

so i had thisquestion about creating the sequence formul based on the given numbers

#

<@&286206848099549185>

#

the current numbers are :

#

not sure what the sequence formula is

viral patioBOT
#
From

#❓how-to-get-help

Rule 4

If your question has not been answered for a minimum of 15 minutes, you may use the Helpers tag once. Please do not try to bump your question using this ping unnecessarily. Do not abuse this ping. Do not individually ping users with the Helpers tag without their express permission.

last timber
#

try find relation between numbers

cloud horizon
#

yes i did.

#

they multipy *3 the first 2 times.

#

then multiply *2 the next 2 times

last timber
#

,calc 108/54

vital dewBOT
#

Result:

2
fossil pewter
#

,w 3,9,27,54,108,...

vital dewBOT
cloud horizon
#

interesting.

#

@fossil pewter ty

bright ether
#

Can anyone give hint about Question 59

reef thistle
#

forgot what C and Z are

junior mantle
#

C(a) is centralizer of a

reef thistle
#

Z seems to be centre of group

#

probably all the kI

#

wait why isn't this in abstract alg

stray reef
#

isn't C(A) just the set of everything that commutes with A

reef thistle
#

yeah sounds like it

#

that means you can just equate BA=AB and solve

bright ether
#

Yes right annn

solemn dome
#

How do I do this?
Give a recursive definition of the set of natural numbers n so that 2 = n mod 3.

errant bear
#

what does it mean for 2 = n mod 3

#

@solemn dome

errant bear
#

smh

solemn dome
#

i figured it out, i was in lecture when you responded @errant bear

errant bear
#

aight cool

cold grove
#

"a series is convergent iff the limit as the sequence goes to infinity is 0"
I know this statement is false because it has counter examples (ie harmonic series) but does anyone have an intuitive understanding as to why its false?

near prawn
#

it needs to go 0 and needs to do so fast enough

#

which isnt true for harmonic

cold grove
#

I thought about it like that too @near prawn but I didn't understand what fast enough meant because it just made sense that if it eventually goes to 0 you can add up the other values to get a number. But i guess I have to try to compare it to other series to better understand it

cold grove
#

I asked in another server too just to get a variety of responses and I think the answer they gave helped along with urs. They said relating the harmonic series to the integral test it, integral is the log function which doesn't have a y asymptote, so it continuously increases even if very slowly.

craggy gale
#

Yes

#

and there are indeed four of them

#

the |•| probably isn't meant to be read as absolute value here x')

#

You're welcome

hasty glade
#

When I m talking about digraphs

#

What is o(a)

bright ether
#

Question 61 sat bottom of the pic. Can anyone solve ?

#

Or give a hint please

near prawn
#

does |a| mean the order of a?

bright ether
#

Yesss

vital dewBOT
last timber
#

where (m, n) stands for gcd

bright ether
#

I am getting that , yes. But after that what to do

#

I am getting, at last that |a| divides 280 and 440

last timber
#

hint: lcm

near prawn
#

does it even work tho

#

if the order of a is 20 then order of a^28 isnt 10

last timber
#

what

near prawn
#

(a^28)^5=a^140=(a^20)^7=e if order of a is 20

last timber
#

why 5

near prawn
#

wym

#

im just saying a^28 wouldnt have an order of 10 if a had an order of 20

last timber
#

but why you decided that a should have order 20

near prawn
#

bruh i cant read

#

nvm ignore me just woke up

#

yea just do the gcd thing

last timber
#

@bright ether so look

vital dewBOT
last timber
#

any ideas how u can apply this?

bright ether
#

I have done like this, is this correct ? , My answer is - n can be any divisor of 40.

near prawn
#

,rotate

vital dewBOT
last timber
#

so

#

in ur problem statement it means that m = 280

#

since 10 is order of x^28

#

and n = 440 by similar reasoning

bright ether
#

My answer is correct or not ?

last timber
#

no need in "any divisor of 40"

#

just 40

bright ether
#

Okkkk

marble pivot
#

@last timber how do u have that font on latex

last timber
#

artemisia

orchid pine
last timber
#

it may be

#

in part of sums

#

but as i see it is not

analog sonnet
#

Maybe Ctrl+F and look for generating function

#

since you seem to have the pdf

#

yeah looks like a more general intro to different mathematical sub-branches and structures

orchid pine
#

it appears to have generating functions
under counting

#

whenever it dips into other fields is it still solely within the context of discrete math?

#

I major in CS

I’m thinking about minoring in math, but if I get interested in something math related, I could get distracted

#

i think im overthinking it

weary tiger
#

can I ask questions on here?

near prawn
#

no

weary tiger
#

ok

near prawn
errant bear
#

lmao

weary tiger
weary tiger
#

@stray reef can you help me pls

stray reef
#

i don't know

#

help you with what

weary tiger
#

oh here comes polynomial

#

yay*

#

if we have a box with 5 blue and 3 red balls, balls are drawn with replacement. we wish to find the probability that after 12 draws, there was a blue ball drawn 5 times.

#

@weary tiger what is wrong with you

#

<3

#

i enjoy your conversations

#

that was a genuine yay

stray reef
#

at least 5 or exactly 5?

weary tiger
#

exactly 5 ann

#

actually

stray reef
#

in either case the number of blue ball draws follows a binomial distribution

weary tiger
#

let me reword the question it is not accurate the way i worded it

stray reef
#

...

#

okay

weary tiger
#

what is the probability that 12 draws are required until a blue ball was drawn 5 times

#

idk if those are two different questions

#

it may be

stray reef
#

ah see yeah that's different

weary tiger
#

@somber hearth I’m not sure I understand

stray reef
weary tiger
#

so it would be

stray reef
#

your problem asks for $P(X = 7)$ where $X \sim NB(5, 3/8)$

vital dewBOT
weary tiger
#

wait but i haven't learned about this

#

is there an intuitive way to look at this

stray reef
#

that's all i have the energy for atm

weary tiger
#

rip

#

ok

#

thanks

stray reef
#

ok @weary tiger now that i'm a little bit less tired i can try to explain it to you in a way that i think is fairly intuitive

#

if you want

weary tiger
#

@stray reef sure

#

sorry i wasn't on

stray reef
#

"12 draws are required until a blue ball was drawn 5 times" means that

  • the first 11 draws saw exactly 4 blue balls
  • the 12th draw was a blue ball
#

which makes it obvious that the answer is $\binom{11}{4} p^4 (1-p)^7 \cdot p$, where $p$ is the probability of drawing a blue ball in a single draw (which i think was 3/8 in your problem)

vital dewBOT
weary tiger
#

i guess the part that's most confusing is the c(11,4)

#

what is that counting

stray reef
#

the number of ways the four blue ball draws could be positioned among the first eleven draws

weary tiger
#

yeah why not all 12?

#

and choose 5

stray reef
#

the 12th draw was a blue ball

#

we need the 12th draw specifically to be a blue ball

#

since otherwise we would've hit 5 blues before the 12th draw and it wouldn't fit the event description

weary tiger
#

so p = 5/8, since 5 blue balls?

stray reef
#

seems so

weary tiger
errant bear
#

its asking you to find how many combinations of triples whose sum of the points are even

ocean viper
#

halp pls 😦

weary tiger
#

what is the question?

ocean viper
#

its the statements

#

ik that the argument is valid

#

i used truth table to show it but apparently i had to do it via the rules of inferences

#

i found a rule of inferences but idk how to show that it is division into cases

#

p = christmas bonus
q = sell motorcycle
r = buy stereo

how do i show that
p -> r
q -> r
p v q -> r

is a valid argument via proof of inference

weary tiger
#

what is there to do other than say "this has the form of proof by division into cases"

#

@ocean viper

ocean viper
#

how do i show it? .-.

#

sure it looks similar

#

but idk how to show it

weary tiger
#

if p ⋁ q is false, the implication is vacuously true. If p ⋁ q is true, proof by division into cases applies

#

sorry was busy with something else

#

@ocean viper

ocean viper
#

what does vacuously true mean o..O

weary tiger
#

an implication p⇒q is defined to be true if p is false or q is true

#

in cases where p is false, the implication can be called vacuously true

ocean viper
#

ah

#

so if it is vacuously true i can ignore it?

#

im sorta trying to generalize what u just said

weary tiger
#

hm no you can't really ignore it

#

it is kinda ignored in some cases though lol

#

for example, in direct proof method

#

to prove p⇒q you can assume p to be true and show that q follows from it. Because if p is false, then the implication is vacuously true

#

but even though it's still something to consider, no one would ever write that out

ocean viper
#

hm

#

i learned abt but i dont rlly know how to apply it

#

Im not taught to write proofs yet

#

so idrk much of this

weary tiger
#

it's probably easier with a truth table

ocean viper
#

hm

#

yeah

weary tiger
ocean viper
#

yeah ik abt that

#

so for my problem i can assume either p or q is true
and even if they're not, the statement will still be vacously true

weary tiger
#

yes

#

there may be some more detail involving rules of inference your instructor wants but that sounds good enough to me lol

ocean viper
#

aight

#

ye i u nderstand now

#

Thanks alot!!!

weary tiger
#

it is primitive enough that it only uses the definition of the implication and cases inference

ocean viper
#

o.o

marble pivot
#

Intuitively I don't get how if p is false, p implies q is true no matter what @weary tiger

#

I feel like it shouldn't have a true/false value at all if p is false

faint umbra
marble pivot
#

Ah that’s a great explanation, thank you

weary tiger
#

the tagged person doesn't get the ping if you edit it in btw @marble pivot, you have to tag them again in a new message

marble pivot
#

Oh

mortal mortar
#

Let 𝐴 be a finite set with exactly 35 subsets of size 4. Determine |𝐴|.

#

I'm not sure how to do this is it just 35 choose 4?

last timber
#

@mortal mortar no

vital dewBOT
last timber
#

determine n

mortal mortar
#

okay thanks

naive saffron
#

Seems difficult

#

,calc 35*24

vital dewBOT
#

Result:

840
last timber
#

,w 840 = x(x-1)(x-2)(x-3)

vital dewBOT
last timber
#

,w 7 choose 4

vital dewBOT
naive saffron
#

Who in the right mind would go a solve a quartic polynomial

weary tiger
#

guess and check

last timber
#

Who in the right mind would go a solve a quartic polynomial
@naive saffron Fermat

cyan field
#

hey guys

#

is this true?

#

Claim: There exists a simple graph with 5 vertices

with degrees 5, 3, 3, 3, 2.

near prawn
#

what have u tried

#

@cyan field

fading abyss
#

has anyone used

weary tiger
#

Don’t think so

marble pivot
#

𝐴
|𝐴|.

#

Whoa

stray reef
#

?

marble pivot
#

I didn’t know there were characters like that

#

𝗔𝗕𝗖
ABC

#

Sorry I guess this isn’t the right channel

weary tiger
#

Would y=f(x)=x/2 from all reals to integers be onto, if so how would I “formally” prove it is

stray reef
#

$f(x) = x/2$ does not define a valid function from $\bR$ to $\bZ$ at all

vital dewBOT
stray reef
#

unless you believe that π/2 is an integer

#

@weary tiger

weary tiger
#

Would such a function not be possible?

stray reef
#

of course it wouldn't

#

i mean like

#

look

#

f(x) = x/2 would make you have f(1) = 1/2

#

but is 1/2 an integer?

#

no, 1/2 is not an integer

weary tiger
#

How would I go about to prove such a function DNE

#

Not sure where to start

stray reef
#

i literally told you why your function doesn't exist

#

i can give you as many more real numbers as you like which don't give an integer when halved

weary tiger
#

Not for that function but for an onto function from reals-> int

stray reef
#

oh

#

so you're just looking for a surjection from R onto Z?

weary tiger
#

Yeah

stray reef
#

the easiest one to define would be the floor function

weary tiger
#

Hmm I will look into this in specific but in general how would I prove it is onto

stray reef
#

.......

#

using the definition of an onto function

#

if you wanted to prove that the floor function is onto, then you would need to prove that every integer is the floor of some real number

weary tiger
#

I see, thank you

weary tiger
#

would a way to prove R -> Z 1-1 functions do not exist is to show that cardinality of R is much greater than cardinality of Z so there would never be a 1-1 correspondence

honest barn
#

By definition showing there isn’t a 1-1 function from R -> Z shows that R’s cardinality is larger

#

If you have restrictions on your functions, like they’re additive or something you might be able to get an easier solution

weary tiger
#

ok thank you

weary tiger
#

using inclusion exclusion how would I calculate in a 6 decimal digit space(so is able to be 1st digit) where digits can be repeated, except the digit in the last position can not be the same as the second or third position

#

I have |A| as 10^59 and |B| as 10^5 * 9. where |A and B| is 10^58 but this isn't right

dapper mason
#

@fading abyss i used that txtbook for my discrete class

#

the author is a prof at my school lmao

fading abyss
#

oh lmao

#

how was it?

dapper mason
#

pretty good explanations

#

pretty solid txtbook tbh

hasty glade
#

What is the name of these graphs ?

#

I mean choosing two nodes A, B. I m able to go from A to B for all A and B

#

I do not know the word in enlgish

stray reef
#

connected

hasty glade
#

That was the word

#

The definition talks about two A and B nodes

#

can A = B ?

stray reef
#

well you can always go from a node to itself

#

by just

#

not going anywhere lol

#

so it doesn't matter

hasty glade
#

...

#

You are damn right..

#

Hahahahahaha

#

I spent 10 minutes with that issue..

#

A is connected B isnt

#

Is that right ?

#

G is a connected graph, if you create a new graph D removing an edge from G so that G is not connected. Can G have loops?$$

#

Oh.. That is not what I expected

vital dewBOT
hasty glade
#

I gave the B graph example

last timber
#

graph is connected if there is path between each pair of vertices

languid flint
#

Graphs are connected if there's a path to access all nodes @hasty glade

last timber
#

it can have loops

#

parallel edges

#

only it needs is to have a path

#

at least one path

languid flint
#

Hey @last timber

last timber
#

Hey

languid flint
last timber
static basalt
gleaming zephyr
#

in sets element repittion doesnt make a difference

#

{x,x,x,x,x,x,...} = {x}

#

or you can just think of normal set equality

#

7 is in here 7 is in there

#

7 is in here 7 is in there

#

this is a subset of that and this is a subset of that hence equal

static basalt
#

Right I understand. Thanks

pallid lintel
#

would anyone know what indices of registers mean's in this context? We have been talking about goto programs and structured programs, and running them on registers over the natural numbers.

📎 4c733c7499b6bcf0b8373cf0eadd3476.png
#

i just want to know what an 'indice of a register' means

lean flume
#

me is confusion

sour arrow
#

Try it in English first. What does it mean if A is a subset of B?

hasty glade
#

Guys.. what is the name of a set of edges like {a,b,c,d}

#

In which you go to a then b then c and finally d

#

What is the name of that in english

sour arrow
#

Path?

hasty glade
#

Exactly

#

And a close path is when {A,(...),A} ?

#

i do not know this vocabulary hahaha

sour arrow
#

Sorry, no, I'm wrong. It's a walk

hasty glade
#

What is the name of a path/walk in which you start on a node and finish on the same node ?

junior mantle
#

Circuit?

sour arrow
#

I never remember these rofl. Wikipedia to the rescue

hasty glade
#

Can i say that {A} being A a node is a circuit ?

sour arrow
#

Yes. The walk where you go nowhere is a circuit

hasty glade
#

So having a walk that is {A} in which u(A) = 0 is a circuit ?

#

u(A) = length of A

lean flume
#

@sour arrow A is subset of B means that every element of a is in b

sour arrow
#

@lean flume
Exactly. Or, if an element is in A, then that element is in B

#

Can you translate that to maffs?

lean flume
#

so if A exist in B then B exists in A?

hasty glade
#

@sour arrow I m having a lot of trouble

sour arrow
#

Nop. That makes no sense haha. Make sure you know how the symbol ∈ is used

hasty glade
#

Because if you consider a tree you would find that it has no cycles

#

But picking any node would be a cycle

sour arrow
#

Oh true haha

#

Hmm. Let me look at these definitions

hasty glade
#

Something has to be incomplete on the defenition that my teacher gave me hahaha

lean flume
#

∈ means it exists

#

so

hasty glade
#

This is the exist symbol $\exists $

vital dewBOT
near prawn
#

definitions can vary from author to author in graph theory so be careful

hasty glade
#

I m really having a mess hahah

#

Wikipedia does not help

sour arrow
#

Oh it does haha

#

"non-empty"

#

So just by definition, the "do nothing" walk doesn't count

#

Which - fair. This allows you to define trees.

hasty glade
#

Well that would be case if you use edges for the trails..

#

And most of the time you will

#

Thanks now everything has sense

#

Well reading wikipedia I realize a lot of things..

hasty glade
#

Dont you believe that graph definitions have a lot of holes ?

#

I mean I saw 3 different definitions for the same thing..

#

One of them was wrong

#

Well, what I believe that definitions are not wrong if you are picking a good source

#

I red an article in spanish that had some mistakes

#

The english information is waaaay better

#

If I say "GRAPH" then it cant have the same edge ?

#

I mean a "MULTIGRAPH" is also a "GRAPH" ?

#

Or they are different things ?

#

I do not know what to think hahaha...

marble pivot
#

Yeah it’s kind of annoying

hasty glade
#

Consider a Polytree

#

Or a Directed Tree (for some authors)

#

The properties that are true for default no directed trees, are also true for Polytrees ?

solemn dome
naive saffron
#

You can try long division

solemn dome
#

one of my friends suggested long division, but i dont understand what that really means

#

after i do the long division what do i do

#

because it leaves me with a polynomial right?

naive saffron
#

What did you get

solemn dome
naive saffron
#

...

#

alright

obtuse lance
#

you don't know how to do long division? @solemn dome

solemn dome
#

long division isnt the problem for me here i can do it, but im just doing this to save time

#

because i dont understand why im doing long division or the answer's application to the problem

errant bear
#

:sully:

naive saffron
#

alright so we know $\frac{x^4+4x}{x+2}=x^{3}-2x^{2}+4x-4+\frac{8}{x+2}$, then notice that when $x$ is large, the fraction $\frac{8}{x+2}$ is small, and eventually approaching 0. This means that it will not influence how the function behaves when $x$ gets large, so when $x$ is large, the function acts like $x^3-2x^2+4x-4$

vital dewBOT
errant bear
#

do you know what big O's definition is? it should help

solemn dome
#

i just know you should avoid having a large big O value

naive saffron
#

???

solemn dome
#

im taking a computer science course

#

and thats all i know about it from my lecture

errant bear
#

do you know the definition of big o

solemn dome
#

no

errant bear
#

uh

solemn dome
#

does this work?

errant bear
#

i mean, no

#

you need the defining inequality here

solemn dome
#

all the problems before this one were like, c1g(x) < f(x) < c2g(x) and i plug in numbers

#

but this one doesnt seem anything like that and its not covered in lecture

errant bear
#

are you positive the definition of O wasnt covered

solemn dome
#

is big O the same thing as order of magnitude?

errant bear
#

no

solemn dome
#

wait nvm

#

i found it

errant bear
#

mmk

#

so just use this definition

solemn dome
#

my friend says the answer is 3, but i want to understand why

#

i dont understand the definition

hasty glade
#

Would someonle talk with me about graphs haha ?

errant bear
#

have you tried using the inequality

solemn dome
#

i just sound stupid at this point, but i dont even know what to plug in where for the inequality

#

when i learn math i usually see an example before doing a problem, and i didnt see an example. I have no guidance on how to do this problem