discrete-math

[past gate]

And do the same with the edges.

[gritty crescent]

Yep!

[past gate]

I think the same applies for the degree of the vertices.

If the degree of all the vertices are the same.

Is that it?

[gritty crescent]

Yep!

[gritty crescent]

You would want both graphs to have same number of vertices for each degree

So like, if graph (a) has two vertices of degree 2, a graph isomorphic to it should also have exactly two vertices of degree 2, and this should hold for all possible vertices

[past gate]

Ah right,fairly easy I guess.

[gritty crescent]

[past gate]

I just need to counter the number of vertices and the degree of each vertice.

[gritty crescent]

Yep, that should suffice

Although

Dismissing a graph as non-isomorphic should be quicker

For example, (b) is not isomorphic to (a) since the former has a vertex adjacent to every other vertex, but the latter does not.

[past gate]

Ah,something like contraposition?

if not non isomorphic (a) then not non isomorphic (b). Conclude (a) isomorphic (b).

[gritty crescent]

No haha

Not isomorphic just means not isomorphic, it saves you the time and trouble of counting vertices, edges, etc. for (a) and (b)

[past gate]

I will go with the traditional method lol,seems like a complicated problem to me lol

[gritty crescent]

Since (b) has that central vertex adjacent to all the remaining 5 vertices, you can see that right?

[past gate]

Yeah.

[gritty crescent]

But (a) has no such vertex

[past gate]

It automatically fails to be isomorphic with all the other graphs just because of that 5 degree central vertex.

Am I correct?

[gritty crescent]

Superficially checking, that sounds about right

(d) is already ruled out with 7 vertices in all

So you get the idea here

[past gate]

Yeah

Looks like a) and d) are isomorphic to me

[gritty crescent]

Count the vertices

[past gate]

a) and c) pardon

The cyrillic notation just confused me lol

🙂

[gritty crescent]

Hmmm, that would need to be checked.

[past gate]

These two.

[gritty crescent]

Okay, looks good!

[past gate]

These two are also isomorphic

Same number of vertices,same number od degrees of all the vertices.

[gritty crescent]

I'll take your word for it. Aren't you supposed to check if both graphs have same number of vertices for each degree?

Knowing that they're all odd degree is fine

But having 2 vertices of degree 3 in one, and 3 vertices of degree 3 in another would still spoil the day

[past gate]

I am not really sure what you are trying to point out but I counted the number of vertices in each graph(7=7) and then counted the degree of each vertice in each graph and compared if I have the same in the other one(for ex 2 vertices with deg 3 etc..) wich I find correct.

[gritty crescent]

Oh, alright then.

[past gate]

Ok now another thing concerns me.

How do I prove isomorphism by using paths/cycles?

It says that these two graphs are not isomorphic

While counting the vertices and the degrees of each vertice is the same,meaning same results for both,it still says that they are not isomorphic.

[pale epoch]

the left one has two degree 2 vertices that are adjacent, the right one does not

[past gate]

Oh,so adjacency takes part here,right?

[pale epoch]

i'm sure there are other arguments

[past gate]

wait,wdym two degree 2 vertices? there are two degree 2 vertices in the both of the graphs. If you are talking about the middle square.It's the same,the connection is just moved.

[pale epoch]

u_4 and u_3 are adjacent in the left one

an isomorphism would have to map them to degree 2 vertices that are adjacent

such a pair does not exist

[oblique cove]

hello
anyone has a book which contain the solution of Rosen, Kenneth H - Discrete mathematics and its applications-McGraw-Hill (2019)
or i have to pay to slader

[past gate]

I think this is what you are looking for

Oh wait,you are looking for the solutions..

Check it out it may have the solutions.

[pale epoch]

i wouldn't recommend linking illegal stuff

discord does not like it

[oblique cove]

thanks for reply but it's not contain solutions

[pale epoch]

try searching github

[oblique cove]

i don't think this a problem because there're many can't afford to pay or don't have way to pay online

[pale epoch]

something like https://github.com/HenrikSamuelsson/Discrete-Mathematics-Rosen

[oblique cove]

thanks alot bro ^^

[pale epoch]

this is not a moral issue, its a legal one

discord does not want you to post links to such stuff and this server has to enforce this

i suggest sharing such links only via dms

[oblique cove]

u have a point

[pale epoch]

there is also https://github.com/jigjnasu/discrete_mathematics_and_its_applications

seems to have more content

anyways, if you search github you will often find people uploading their own solutions

this is ofc not an official solution manual and might contain errors and be incomplete

[oblique cove]

ok thank you i think i will pay for slader xD

[pale epoch]

same thing applies, except those people get paid

[hybrid crown]

I'm stuck with part c

I simply brute forced the series in part b, which wasn't really working out in c

[iron marsh]

While you wait for someone else to answer, I encourage you to use induction on (b). That looks potentially useful here.

[hybrid crown]

oh wait

I didn't do series on b

I used a combinatorial argument on b

I meant I used series on the first part of c

[dawn robin]

When looking at a boolean problem, do i consider x` to be a different variable from x?

[urban saddle]

well x` has a different value than x so i guess so?

[oblique cove]

how it has inverse however it's not onto function ?!

[obtuse lance]

it is an onto function

give an example of an element in the codomain that's not hit @oblique cove

[oblique cove]

what if Z+ => Z+ still onto ?! @obtuse lance

there first element you start the domain with because it's x+1

if domain ]-inf, inf[ you will not hit -inf - 1

or infinite numbers have another way to deal with ?! i dunno i'm newbie in math

if you got what i mean you can explain me ?

[quaint star]

-inf is not a real number, and neither is -inf-1

It is just notation we use

]-inf, a] you take all the real numbers <= a but with no lower bound.

And [a, inf[ means you take all the real numners >= a with no upper bound.

And ]-inf, inf[ mean you take all the real numbers with no upper or lower bound.

[weary tiger]

Show that (x2 + 1)/(x + 1) is O(x).

[obtuse lance]

do you know polynomial division @weary tiger ?

[weary tiger]

Unfortunately, not 😦

[obtuse lance]

well, I guess we can get around it, here's a straightforward enough trick I think

first step: $$\frac{x^2+1}{x+1} = \frac{x^2 + x - x +1}{x+1} = \frac{x(x+1) - x+1}{x+1}$$

[vital dew]

Meρρa

[obtuse lance]

actually you know what, this is going to be more confusing than polynomial division I think

it's probably best you go learn how to do that first

[oblique cove]

@quaint star i didn't get how it's onto function yet

[obtuse lance]

since +infinity and -infinity aren't integers, they're not relevant to being onto

any integer you take has a specific preimage

Z is just the set of integers, there's no +infinity or -infinity in there

kind of like the set (0,1) contains all the real numbers between 0 and 1, but not 0 or 1

[oblique cove]

good if your domain start from 0 to 10 and your codomain also should be from 0 to 10

so your range will be from 1 to 10

so 0 from codomain has no image

[obtuse lance]

yeah on those sets f(x)=x+1 has no inverse

it's not really well defined either, since x=10 has no image in the set

[oblique cove]

so why in the book they said it's invertable

[obtuse lance]

the example you just gave is different than the one in the book

f from Z to Z is not the same as from {0,1,...,10} to {0,1,...,10}

[oblique cove]

wow

but what if Z+ to Z+ also invertable ?

[obtuse lance]

it isn't

[oblique cove]

so from Z to Z it's invertable but from Z+ to Z+ it is not

[obtuse lance]

yup

[grim kraken]

@weary tiger you want to pull a 3 and a 2 out of the exponents in the 3^(n+1) and 2^(n+1) terms

that way you can combine like terms

[stray reef]

if you want

[unreal stump]

Yes

[past gate]

Guys do you maybe know any online dijkstra calculators that give explanation about the solution?

If yes,can you share it,please?

[past gate]

Thanks @weary tiger !

Guys,sorry if I spam this room but I need help with this combinatorics problem.

How many bitstrings with length 10 exist,that start with 101 and end with 010?

I started this problem by first finding the bitstrings that start with 101

And thats 2^7,right?

[stray reef]

yes but you're overcomplicating it already

your bitstrings have the format 101xxxx010

so you will only need to find the number of bitstrings of length 4

since they're in one-to-one correspondence with the bitstrings your problem wants

[past gate]

That's it? the answer is 2^7?

[stray reef]

no, the answer is not 2^7.

[past gate]

2^4

Pardon

[stray reef]

2^4 yes

[past gate]

Wow

How did you figure it out so fast lol

I am just stuck with this for like almost 20mins

[stray reef]

idk

years of practice ig

[past gate]

This is what I did,but I knew I was counting some cases 2 times.

And I couldn't figure out what to do to exclude them

[stray reef]

this would be more appropriate for counting the bitstrings that start with 101 or end with 010

for which you would need the intersection anyway

[past gate]

yeah

Now that is the second variation

[stray reef]

but the intersection is what they ask you for here

[past gate]

So I need to calculate
(2^7+2^7)-2^4?

Am i right?

[stray reef]

no, the answer to your original problem (strings that begin with 101 and end with 010) is just 2^4

but if you wanted to do the same problem but with or, then you would need to calculate 2^7 + 2^7 - 2^4.

[past gate]

Yeah I am talking about the OR variation

The one you sent

Because in my .pdf assignment the OR variation is just under the one I sent 🙂

[past gate]

In a class of 12 students for a project,it is required to form groups of 3,4 and 5 students,so that each student will be a member of ONLY ONE group.How many different way are there to create the groups?

@stray reef thoughts on this?

I started doing something like this,but I know this is all wrong

[stray reef]

i can't comprehend your logic here

[past gate]

I know,my approach is wrong.

I assume I can't solve this problem with the "product" rule.

Since the order of the students is not irrelevant,I suppose I need to use the combinations formula.

Am I correct @stray reef .I still cannot conclude how to use it the "right way",tho.

[stray reef]

i mean first off i'd answer the following question:

what are all the ways to partition our 12 students into groups of 3, 4 or 5?

or... wait

we have to split our students as 3+4+5

got confused by the wording a little

isn't this just $\frac{12!}{3! \cdot 4! \cdot 5!}$ ?

[vital dew]

Ann

[stray reef]

the order of the students within each group is irrelevant

[past gate]

How did you get 3! 4! and 5! at the bottom of the fraction

[past gate]

Yeah i figured it out! Thanks guys! Appreciate it! 🙂

[stray reef]

no

[past gate]

-either all are men or all are women.```

Now this one freezed my brain to be honest.

[haughty garden]

take two cases

all are women is probably the easier case to deal with

then for all men, you choose 6 people from the pool of 10 men

[past gate]

Idk how is this achieved but a colleague sent me this solution
C(16,6)-C(10,6)-(C(6,1)*C(10,5))

This would apply if the task was:
at least two are women

We take out the case where there are 0 women or 1 women.

But it won't work for:
either all are men or all are women

[haughty garden]

either all are men or all are women is considerably easier because there are no overlapping cases to consider

so you just need to consider all are men and all are women separately and add these combinations up

for all are women, there's only 1 way in forming the leadership (which is to choose everyone)

for all are men, take any 6 of the 10 men to form the leadership which can be done in C(10, 6) ways

so the total number is C(10, 6) + 1

[past gate]

yeah,I guess the solution my friend provided me has blocked my mind.

And can you explain how'd we calculate in this case: at least two are women?

Cuz my colleague just overcomplicated it.

[haughty garden]

your colleague has the correct idea

you just want to remove the cases where you have 0 women or 1 woman

to find the number of ways to have 0 women, this is the same as all men which we found to be C(10, 6)

to find the number of ways to have 1 woman, we first choose one of the women which is done in C(6, 1). We have 5 spots remaining to be filled up by men. We have 10 men to choose 5 so we can do it in C(10, 5) ways

so for the case where you have 1 woman, we can do this in C(6, 1) * C(10, 5) ways

then at least two women is: total - #0 women - #1 woman = C(16, 6) - C(10, 6) - C(6, 1) * C(10, 5)

[past gate]

Ah I get it now,thanks for the detailed explanation @haughty garden !

[haughty garden]

no worries! 😄

[obtuse lance]

do you know the binomial expansion?

[thorn flicker]

hey guys, in general if a relation is anti symmetric can it still be symmetric

?

[obtuse lance]

sure but it forces a very harsh restriction on your set

so harsh that the answer is practically no

[halcyon kraken]

yeah if order mattered it would be 12! but it doesnt matter so you divide by 3!, 4!, and 5! to compensate for overcounting cuz theres 3, 4, and 5 ppl in the groups

[halcyon kraken]

case 1: all women: 1 possible way
case 2: all men: 10C6

[vital dew]

laze/pingme

[slow jewel]

Anyone know the answer to this?

[past gate]

C(7,2)⋅5^2⋅21^6 ?

Since we are allowed to use "repeated letters",we can use combinations.Order doesn't matter.

We have 5^2 choices.

And picking the remaining six consonants is (26-5)^6,in the 5 spots that are left.

So I think the final answer would be

C(7,2)⋅5^2⋅21^5

Don't take me for granted tho,I am new to combinatorics,I just want to help 🙂

[slow jewel]

This was in my exam yesterday.

I got it wrong

i just did 5^2(21*5)

[south badger]

Let $a \in (0 , 1) $ be solution for $2x^4+x-1=0$ Prove $a \not \in \mathbb{Q}$

[vital dew]

Happiness

[slow jewel]

RRT

possible cases {-1,1,1/2,-1/2}

[south badger]

Hmm? @slow jewel What is these cases?

[slow jewel]

possible solutions

[south badger]

How did u get them?

[slow jewel]

The above theorem

[south badger]

Ye i see

[slow jewel]

Ignore what ive done , its not part of discrete maths

But it works

[south badger]

is there any other method?

[errant bear]

assume its rational

and contradict

[civic horizon]

yeah you can probably just substitute p/q for x and then just do divisibility stuff

but that is basically just doing the rational root theorem

[vital dew]

Happiness

Happiness

Happiness

[south badger]

any hints to deduce it?

thanks

[errant bear]

you're welcome

[south badger]

@errant bear please could you see the question right above?

@slow jewel Hints please

[slow jewel]

no idea sorry

[south badger]

Let $m,n \in \mathbb{N*} : \gcd(m,n)=1$ Prove $2m^2+n^2 \neq 0 [5]$

[vital dew]

Happiness

[dawn robin]

Thread open?

How do you prove a certain equation is an answer to a recurrence relation by mathmatical induction.
For instance if the question was
Prove by mathematical induction that 3^n(3+n) is a solution to
Sn = 3S(n-1)+3^n for n>=1 , and S0= 1
^random problem off the web, so i dont know if it works out

[slow jewel]

Assume it hold for (n-1)

then s(n-1) = 3^(n-1)(2+n)

plug into recurrence, this gives s(n) = 3^n(3+n)

How i would do it, got similar question in exam for Differential equations

[dawn robin]

@slow jewel so you basically just substitute out the original equation and check if this one holds at n-1?

[slow jewel]

substitute s(n-1) and check if you get s(n) = 3^n(3+n)

assuming it holds for s(n-1) comes with induction

[dawn robin]

I guess what im saying is where exactly am i checking if that comes from?
Am i just checking
Sn = 3^n(3+n)
Or am i checking the original equation, and seeing if it gives me the new equation?

Srry im just really bad with induction. And barely understand it :/

[slow jewel]

you are checking if the recurrence holds for s(n). We use induction to assume the solution holds for (n-1). This way when we substitute s(n-1) into the recurrence, we get the required solution for s(n)

where s(n-1)= 3^(n-1)(2+n)

[dawn robin]

So if i follow correctly. For it to be true that 3^n(3+n) is an answer. Then when we do
S(n-1) = 3S((n-1)-1)+3^(n-1) <- original recurrence with n-1

It should end up as
Sn = 3^n(3+n)
?

[slow jewel]

s(n-1)= 3^(n-1)(2+n) Do you understand why this is the case?

[dawn robin]

Not really if im honest, and i definitely have no idea where you got the 2 from

[slow jewel]

s(n)=3*n(3+n)

This is the solution right

[dawn robin]

Yes that is the solution, which we are trying to prove is in fact a solution

[slow jewel]

right

replace n with n-1 in the solution

tell me what you get

[dawn robin]

Srry having issues with a customer will be a moment

@slow jewel srry about that

Ok so, i feel extra stupid right now.
But I now realize i am not actually sure what im supposed to even do with
S(n-1) = 3^(n-1) * ( 3+(n-1))
Like. Theres no way im going to get an equivalence out of it without knowing n is there?

[finite flare]

are you doing induction?

[dawn robin]

Attempting, and failing to understand

[finite flare]

do you understand the principle of induction?

like how it works?

[dawn robin]

@finite flare i didnt know that was a thing. So im gunna say no

But where did the 2 come from 0.0

[slow jewel]

look what i made you calculate

s(n-1)

above text

[dawn robin]

Nah you can keep it caps, i realize my denseness is irritating

[slow jewel]

(3+(n-1))=(n+2)

[finite flare]

@slow jewel should you not tell him what the principle of induction is first ?

[dawn robin]

Oooh i see, your just dropping the parenths

[slow jewel]

Im not irritated, im in your position when i do Real analysis

For induction, we assume the solution holds for some n-1 and try to show it also holds for n

the solution to s(n-1) we calculated. Then we sub it into the recurrence as i did in my picture.

[dawn robin]

Oh oooooooh

[slow jewel]

Then we get the solution for n

[dawn robin]

I think i just understood

[finite flare]

you also need to prove statement is true for 1 or wherever your interval starts

[dawn robin]

Ima try to put what i realized into words

[slow jewel]

yeah, but this is the harder part

[dawn robin]

So, we know the original version of the equation is true, and it contains an S(n-1)

That means that if we consider the possible solution to be true when n = n-1, we can replace all n with n-1 thus making S(n-1) = possible solution with n replaces by n-1

That means if you substitute the S(n-1) from the given definitely true equation with the new possible solution, it has to still be true. If it is, then it is a solution

Did i follow that correctly

[slow jewel]

we dont need to change the recurrence

since it already contains s(n-1)

[dawn robin]

Right your just changing the possible solution to match the n-x in order to allow substitution

[slow jewel]

for a substitution to be made

yes

[dawn robin]

Ok, that leaves me with 2 final questions

1: you used brackets. Was that an aesthetic choice? Or do tbey mean something special?

[slow jewel]

you mean when i write s(n-1)

if so, then yes

aesthetic choice

[dawn robin]

Oh thank god

[slow jewel]

sorry if it confused you

[dawn robin]

Question 2
Would you be willing to help me out with a few other odd bits that I missed out when i was taking the class :D

Cause you have been, super helpful

[slow jewel]

sorry bro

Im new to this helper thing

[dawn robin]

Trust me, ur great XD

[slow jewel]

thanks but maybe tomorrow

its 3am here

[dawn robin]

Fair enough :D

Welp in case anyone happens to know.
When proving if boolean equations are equivalent
Something like
Does [X and (x' and y) ] equal [x and y]

I know x and x' are different variables. But are X and x different variables?
Also, can 2 equations with different amount of inputs even be equal?

[last timber]

@dawn robin yes they can

for example (x or not x) and (y or not y) has the same truth values as x or not x

and yes
X and x' are different variables

[past gate]

Find two different sequences of numbers that start with 2,4 and 6.Find the *nth* term formula and write down some of the starting members.

Can anyone help me with this one?

[weary tiger]

2,4,6,8,10,... - a_n = 2n, 2,4,6,0,0,0,0... - a_1=2, a_2 =4, a_3 =6, a_n =0 for n>3

[past gate]

Thanks @weary tiger ! 🙂 my brain just freezed for a second.

Relations and recurrence relations are so hard for me though. :/

[weary tiger]

is there an explanation, why n choose 2 is equal to summing up from n-1 to 0?

for example:
3C2 =3= 2+1+0
5C2=10=4+3+2+1
.
.
nC2= n-1+n-2...+0

I proved it using induction but was looking for combinotorial argument

[civic horizon]

https://math.stackexchange.com/questions/2260/proof-1234-cdotsn-fracn-timesn12

the second proof is probably what you are looking for and it is super slick

the one using lhopital is my fav though

[weary tiger]

I did not understand that and also this proof works for just triangular number? like say I cant make triangle out of n=4.

and if I have n=3. I can make just two connections like that (assuming there is no horizontal connection between a_2 and a_3)

[past gate]

Given the set A={a,b}.How many different relations can be defined on the set A(AxA)?

Does anyone know how to calculate this?

These little questions bother me so much.

[next mauve]

its 8 right

bcoz AxA will hv 2x2 = 4 elements

and A(AxA) is 2x4 = 8 elements

[glass gulch]

I'm pretty sure the parens there are meant to clarify what a relation on A is

[last timber]

what is A(AxA)

[glass gulch]

.

"relations [...] on A (A × A)"

and anyway it's not 4 or 8; a relation is a subset of A × A, which means there are 2^n(A × A) possible relations

@past gate

[past gate]

So that would mean there are 16,right?

2^4

@glass gulch

[glass gulch]

mhm

[past gate]

As @next mauve said,AxA=2x2=4.

Damn,these are hard.

[past gate]

Guys,does anyone maybe know if my solutions works for this recurrence relation?

I get (-1)^(n+1) * 2^(n-1) * n

And my colleague says he gets:
-1/2 * n(-2)^n.

[unreal stump]

What's the reccurence

[past gate]

I get error for some reason

I am waiting for the picture to be sent

Ok,is it visible now?

[unreal stump]

Yes

Your friend's answer should be correct

Wait,looks like the same thing

[past gate]

Yeah

[unreal stump]

So, it's fine

[past gate]

Visually I was noticing that somehow they are the same.

@unreal stump so both of them are correct,right?

[unreal stump]

Yes

[past gate]

Usually my teaching assistants gives answers to the problems to compare later but they didn't give us any on the last 2 assignments wich is weird.

[unreal stump]

How did you solve this?

Using char polynomials,right?

[past gate]

I don't know if you are familiar with the terminology from my uni,but we use the so called "r" roots.

This is my friends solution.

[unreal stump]

Yea,that's the char polynomial approach

[past gate]

@unreal stump is there another way,possibly easier?

This one looks tough to me,I still make mistakes with these types of problems.

[unreal stump]

This is the easiest method I can think of

[past gate]

There's no explanation at all

Idk how to find the characteristic root r1 and r2.

[weary tiger]

Hello

I am not able to understand o(nlogn) & o(logn).

[hardy viper]

@weary tiger not sure what sort of answer you're looking for

[weary tiger]

@hardy viper Do you know about arrays ?

[hardy viper]

yea

log(n) usually shows up when you do a binary search

like you are asking about a multiple choice question, so are you unsure about the array time or about what O(logn) means

[stray reef]

what do those percentages represent??

also, it's big O, be careful. little o means something different.

[weary tiger]

@stray reef Little o means what ?

@stray reef They are just percent of votes.

[stray reef]

there was no need to ping me twice

anyway, f(n) = o(g(n)) means f(n) grows strictly slower than g(n), to put it loosely.

and... you're saying this is the result of some kind of survey?

[weary tiger]

@hardy viper I understood O(1), O(n) & O(n²) but never saw log under a function.

[stray reef]

you've never seen algorithms with logarithmic runtime?

[weary tiger]

@stray reef No it's from CS50

@stray reef No

[stray reef]

binary search?

merge sort?

also, again, why do you keep pinging me...

[errant bear]

@weary tiger ok

@weary tiger hi

[weary tiger]

Hi

[timid spear]

hi guys any ideas ?

[errant bear]

no

[past gate]

isn't it 6?

192 / 78 = 2 remainder 36
78 / 36 = 2 remainder 6 
36 / 6 = 6 remainder 0```

This is what we did in high school,though.As much as I can remember.

[timid spear]

yes its 6

i did too after searching some and your solution true so you remember true , thanks anyway

[visual tiger]

true or false:

if a prime number p is greater than 3

then

p = 1 mod 6 or p = 5 mod 6

oh nvm that's actually pretty trivial

[lament zenith]

would this be just a powerset of every item in A union to 1

so for example if i give the subset {1} and union with {1} will it become

[unreal stump]

*Every item in power set union {1}

[lament zenith]

{1,{1},.....

[unreal stump]

So, for example {1} is in P(A)

[lament zenith]

So that would mean alsO*, well for this case, if im using the known knowledge that {1,2} is a subset of A

[unreal stump]

so,f({1}) will be {1}

[lament zenith]

Yes not {1{1}}

Since 1 exists

So wait if I have f({1, 2})

How would that then be shown

Just (1,2){1}?

[unreal stump]

f({1,2}) will be {1,2} U {1}={1,2}

[lament zenith]

Ahh ok

So like if I just had f({2}) it will be {2} U {1} = {1, 2}

[unreal stump]

Yes

[lament zenith]

Hmm bec at first i interepreted that as a intersection at first

And I was like ah this is wrong, but since its union with any set that is created via A

The resultant of any of the cases will be one by itself, 1 with 2 or 3 and 123

ty

Also is this channel chat capable of discussing algorithm analysis? or do I need to direct myself to another textchat

[unreal stump]

Should be fine

[lament zenith]

Because just recently I've been doing content regarding algorithm analysis. The material covers it somewhat well and I've had past experiences with it. Only concern is how to formulate an argument or accurately represent in english that this worst-time complexitiy of this algorithmn is O(n)

From inspection, I can say that if I have a target value that is big and none of the values are equal to it. So it will iterate until n times and find that all values in the sequence did not achieve the target value. Hence we can claim that this will run O(n)

The way they've explained it has broken each line down really, which makes somewhat sense. Saying that it will run at a constant d for all actions before and after the loop and d as the constant that will determine the number of operations per loop/iteration

Is there any manner i could approach this for further algorithms?

[lament zenith]

<@&286206848099549185>

[timid spear]

what u guys think

[stray reef]

you have ____ losing tickets distributed across ____ streaks

fill in the blanks

@timid spear

[timid spear]

hmm only 5 wins 125 losing tickets

m streaks ?

[stray reef]

no, there are not m streaks

the line of 130 guests is structured as follows:

some losers
winner #1
some losers
winner #2
some losers
winner #3
some losers
winner #4
some losers
winner #5
some losers

[timid spear]

oh I see

k i can do from here

thank you very much

[lament zenith]

im guessing no one is able to help me out for this

[stray reef]

how's this not just Theta(n)

you scan the entire array once

that's it

[lament zenith]

Whats the difrerence between thetaa(n), bigo(n) and omega(n)?

I thought bigo represents the worst case time complexity, and omega is the best case time complexity?

[stray reef]

Omega means "at least this much", big O means "at most this much" and Theta means "exactly this much"

Theta is the intersection of big O and Omega

[lament zenith]

Yeah so like the inbetween or average

between those boundaries right?

[stray reef]

no, Theta is not average

saying an algo is Theta(n) means it always runs in linear time, even in the best and worst cases

you can weaken it to O(n) if you want

[lament zenith]

But isn't there a case for example that an algorithm can run linear for Omega(1) to O(n)?

[stray reef]

sure, there exist such algorithms

yours is not one of them

[lament zenith]

Hmm bec this is what is explained in the material I've been using

[stray reef]

your algorithm always goes through the whole length of the array

always

[lament zenith]

yeah

I've also written this down from previous notes i made from past education

Everything that is Ө(f(n)) is also O(f(n)), but not the other way around.
T(n) is said to be in Ө(f(n)) if it is both in O(f(n)) and in Omega(f(n)).
In sets terminology, Ө(f(n)) is the intersection of O(f(n)) and Omega(f(n))

So maybe what I'm trying to say, is that for this algorithm we can identify its Theta(n) for the best and worst cases

But there might be example where we examin the worst and best case, might result into a different Theta(TIME)

[stray reef]

...

[lament zenith]

Right?

I might've went off topic but for the algorithm, if we were asked to find its best-case time complexity. We can conclude its Omega(n)?

Or does that require some other necessary examination?

[past gate]

Can anyone help me find the n-th term formula for this sequence?

[unreal stump]

Use telescoping

You should get a_n=n(n+1)(2n+1)/6

[past gate]

what is telescoping? never heard of that method before.

[unreal stump]

https://en.m.wikipedia.org/wiki/Telescoping_series

[past gate]

Is there another way of finding the solution?

[unreal stump]

Induction

Assuming you know the formula for sum of squares

[past gate]

Looks like I am gonna be stuck on this one for a while huh

[lament zenith]

This says find the range using roster notation

My guess was its: Range of f(x) = {0, 1, 2, 3}

Since the sets can be placed into the function

as {1}, {1,2}, {2, 3} etc or even {}

Would this be correct

[stray reef]

why do you call it a "guess"

[lament zenith]

Well it wasn't a guess, i just used that word randomly

But my understanding is that for any set given in A, since X is represented a subset of A. {1} is a subset of {1, 2, 3} and can be used in this function to obtain its value

I just wanted to double check if my line of logic is correct

[stray reef]

don't

[lament zenith]

ok... but could i get a response without you* making remarks on what i'm trying to ask

i'm trying my best to explain

[stray reef]

your answer is correct

im just unhappy with you calling it a 'guess'

[lament zenith]

yeah i get it, but i find it hard to think of words to say. so i might throw in a random word at times - which i can understand

ty

[past gate]

Guys,can anyone confirm if my solution is correct for this problem?

I get:

3-3^(1-n)

[unreal stump]

Yes,it is correct

[past gate]

It just concerns me that some of my colleagues have this as a solution.

[unreal stump]

Same thing

[past gate]

I assume they just rewrited it with the a^-1 rule.

Because a^-1 = 1/a^1

[unreal stump]

Yes

[zenith sorrel]

Hello just wanted to ask if my intepretations are right, so the elements within b are 1,2,3,4 right?

[coral raven]

yes

[zenith sorrel]

Thanks! Also, do I have to enclose the elements within the brackets {} or it is not necessary? If so, what do the brackets mean?

[coral raven]

{} means set

elements are elements of a set

[zenith sorrel]

Owww I see! So for the problem, is the {} applicable?

[coral raven]

B = {1, 2, 3, 4}

the elements in B are 1, 2, 3, 4

[zenith sorrel]

Owww I get the gist of it. Thank you for the insight @coral raven ! Truly appreciate your help

[coral raven]

lol laying it on a bit thick

[stray reef]

uppercase B, not lowercase b. but yes

[odd epoch]

Any advice on learning discrete mathematics? Does it have some calculus? Is it difficult? And are there any websites or channels that I should search up to learn?

[weary tiger]

it's pretty easy, no calculus needed

[unreal stump]

cries in exponential generating functions

[weary tiger]

there are different discrete math courses so hard to say where you can learn from if you dont state the syllabus

oh yeah I guess knowing how series work might be needed, so a bit of calculus

[civic horizon]

pls

[stray reef]

@prisma root wrong channel, potentially wrong server, and also what the fuck is that greeting

[coral raven]

i want to know what they sent

[stray reef]

attention attention ladies and gentlemen men and women boys and girls today is my birthday who'd like to join vc to celebrate?

really drilling in the binary >.>

[coral raven]

interesting

[glass gulch]

amazing

[gentle token]

'Ello

[jagged junco]

any idea? Find how many isomorphic graphs there are to this graph? V={1, 2, 3, 4, 5, 6}

[stray reef]

eh?

wym how many isomorphic graphs

you can spend all day coming up with different ways to relabel this graph to obtain technically different but isomorphic variants

do you have the exact wording of the problem?

[obtuse lance]

I assume they mean up to labeling, like there are 6! ways to place the points but since it has two lines of symmetry you could reflect it through so there are 6!/4 distinct ones

[jagged junco]

we are supposed to use V(G)!/|Aut(G)|
so I know it is 6! / |Aut(G)|
but I don't know how to find it |Aut(G)|

[stray reef]

oh

[jagged junco]

why is it 4?

[stray reef]

so what you are REALLY looking for is the number of automorphisms of this graph.

[jagged junco]

yes

exactly

[stray reef]

there seem to be only four, yeah

[jagged junco]

it's four because there are 4 vertices that you can like spin 4 times?

or?

[stray reef]

vertices 5 and 6 can only be fixed or swapped since they are the only ones with degree 2

1 and 4 can also only be fixed or swapped

the placement of 2 and 3 will be uniquely determined afterward

[jagged junco]

so its like you split it in half about 2 and 3?

one case, vertices 5 6 replaced = 2 in total

second case, vertices 1 4 replaced = 2

and then 2 3 is just set automatically

hm

[obtuse lance]

just think of the graph unlabeled and imagine rotating it or reflecting it so that it looks the same

[shadow pier]

nvm I got the answer

[obtuse lance]

you can reflect it through a horizontal line or through a vertical line, and that generates the full group of symmetries

for instance rotation by 180 degrees is really just both reflections combined

[jagged junco]

I think I see it now

[obtuse lance]

this is the klein 4 group, has 4 elements yeah

[jagged junco]

yea it helps

[jagged junco]

so if I want the number of automorphisms to this? it's just 2?

[obtuse lance]

the last one had the symmetries of a rectangle

this has the symmetry of a square which is even more symmetrical

so it should be an even larger group

[jagged junco]

oh

so 4?

[obtuse lance]

no, the last group had 4

larger

have you learned about dihedral groups?

[unreal stump]

Is there any deep connection between group theory and graph theory?

[jagged junco]

nope, we just started learning about isomorphosims (had only one lesson)

so it's what we learned so far basically automorphisms and this formula I said earlier

[jagged junco]

but I tried to reflect it through a horizontal line like you said.
So in case it's a square you don't do it because it's already symmmetric?

[obtuse lance]

eh?

well ok do you know what a group is

[jagged junco]

yes

[obtuse lance]

what groups did you learn about so far

just trying to understand what you're expected to do to solve this problem

seems like dihedral groups would be pretty important to learn about at this stage

in particular what kind of symmetry operations we can do and how they're related is important so you don't over or under count

[jagged junco]

we didn't learn about special groups sorry as far as I know, just V(G, E) it's all about graphs theory

they're expecting us to use combinatorics to solve it, they gave us an example of this something similar to this exercise

for example in the example they gave us here: to find how many isomorphoic to this graph

[obtuse lance]

I can just tell you but that's just me hand holding you through a problem that's almost identical to the last one

and I don't want to do that

[jagged junco]

This is what they did to solve it:

and they showed another way to solve it

so this is what they expect from us

[obtuse lance]

I see

[jagged junco]

in this way it's like what you said when you divide with the reflection of vertical/horiziontal line

[obtuse lance]

well ok then I would just think of overcounting by just saying there is 4! ways of labeling it for starters

but then divide out the ways I'm over counting

like every time I rotate the square or reflect it

I am getting the same graph with different labels I had counted

so just focus on rotations alone how many times am I over counting?

[jagged junco]

so I need to "get rid" divide 4! by the number of times I rotate the square or reflect it

[obtuse lance]

yeah exactly

[jagged junco]

you can rotate the square 4 times

[obtuse lance]

good

[jagged junco]

and to reflect it is 2 for each time?

[obtuse lance]

yeah

[jagged junco]

so it would be 8?

[obtuse lance]

so 4!/8 is the answer

yep

[jagged junco]

oh wow

[obtuse lance]

the way you're thinking is exactly how you determine the generators for the symmetry group

rotation by 90 degrees and a reflection

the size of that group is exactly 8 elements

so your intuition is just what that thing is, put into a math object is all

[jagged junco]

yes I think I see it, now it's more clear for me thank you

🙂

[obtuse lance]

yeah you're welcome, the more you think about it the easier it becomes

[jagged junco]

practice makes perfect 😄

[obtuse lance]

no clue tbh, I can say some random stuff I don't really know anything about like there being a galois theory type thing with covering spaces and fundamental groups, I'm not the person to ask lol

[rigid kite]

I'm confused about the Wikipedia article regarding sums of three cubes. https://en.wikipedia.org/wiki/Sums_of_three_cubes
It says there
[...] 1 and 2 are the only numbers with representations that can be parameterized by quartic polynomials [...]
[...] These can be scaled to obtain representations for any cube or any number that is twice a cube. [...]
To me this means all known families are either representations of 1 and 2 or scaled variants of these. But that can't be true. I know several quartic polynomials for other numbers (all of which are sadly cubes) that are not multiples of the solutions for 1 or 2.
Am I missing something?

I assuming I have no typos, these are some of them:
They aren't pretty, but they surely aren't trivial multiples of the 1 and 2 solutions I've seen

[obtuse lance]

they would be a subset of the multiple of 1

once you have x^3+y^3+z^3=1 then you can multiply by w^3 to get (wx)^3+(wy)^3+(wz)^3 = w^3

here you've restricted further to w=16n^4 in the first case

[rigid kite]

but the coefficients don't suggest a multiple of the 1 case

[obtuse lance]

but since 1 has a parametrization, w^3 has a parametrization too already

[rigid kite]

so it looks like a different parametrization to me

[obtuse lance]

yours isn't different, it's a strict subset probably

[rigid kite]

that's why I'm asking. I totally get, that you can just scale the solutions for 1 and 2 to get any cube. but I found some that don't look like scaled 1 or 2s

hm. can you think of any way to prove that, aside from just plugging in numbers and seeing if they appear in both sets?

[obtuse lance]

yours doesn't look too different, probably you can just multiply by 16n^4 and translate the parameter a little to get it to match up

so doing it the way I describe the x coordinate would be 16n^4*9b^4 and yours is

-9x^4+24n^3x

maybe just set them equal and solve for b in terms of x or vice versa

I know you said you didn't want to do this but

it's not really difficult to merit avoiding imo

[rigid kite]

I did some more digging now. my third solution looks like 2.10 in this paper:
https://arxiv.org/pdf/1802.06776.pdf

I guess the other ones also fit somewhere along the lines of that paper then

but getting back to the original question: that claim on wikipedia seems to be based on some misunderstanding then. those families given in the paper are surely not simple multiples of Mahler's old formula

[weary tiger]

hey, we're covering power series, I was wondering if you just have to go with reasonable guesses to find the series or if there's a more concrete way of finding it?

We have these as exercises

[past gate]

In one social network there are exactly 300003 users.Is it possible for each user to be friend with *exactly* 303 users from that network? Explain why?

Any ideas anyone? :/

[teal flare]

you should think of this formulation as a graph with N=300003 nodes

and every user(node) has degree 303

it happens that the sum of all degrees in a graph is always an even number

you might want to look up for "handshaking lemma"

but with this you can get the answer

[past gate]

Oh,so I think I can use the 2e=sum of all node degrees

So it would be 2e=300003 * 303

2e=90900909

And e=90900909 / 2

And we get

45450454.5

And we conclude that this is not possible because we can't construct a graph with a decimal number of edges.

Am I right? @teal flare

[teal flare]

exactly

[weary tiger]

Maybe use pigeonhole principle?

I was wondering if that could work

[past gate]

Never heard of it.

Can you maybe try and show us how would that work? @weary tiger

[teal flare]

I don't think so

[weary tiger]

Yh I figured

It asks whether it is possible for a user to have exactly 303 friends

Nice trick tho using graph theory

[deep tapir]

Is this familiar to anyone? It shows up when calculating $(x \frac{d}{dx})^n \frac{1}{1-x}$

[vital dew]

deadpan2297

[civic horizon]

These are apparently called eulerian numbers

[feral osprey]

if A,B ≤ G
Does A∪B ≤ G?

[stray reef]

does ≤ mean subgroup?

if so, then no. A ∪ B may not be a group at all!

@feral osprey

[feral osprey]

@stray reef How so?

[stray reef]

A ∪ B may fail to be closed under composition

(or multiplication, or whatever else you're calling the group law of G)

if you want, i can give you an example

[feral osprey]

I'd like that

[stray reef]

take G = (Z,+), A = {10n | n ∈ Z}, B = {3n | n ∈ Z}

then 3 ∈ A ∪ B and 10 ∈ A ∪ B but 13 ∉ A ∪ B

[feral osprey]

But all a ∈ A ∪ B and so a ∈ G

[stray reef]

so what?

[feral osprey]

What makes it that b that isn't in A ∪ B but in B.
Means that A∪B ≤ G is false?

[stray reef]

what?

what's this a and b business?

i gave you a proof by counterexample that A ∪ B isn't closed under addition, and therefore cannot be a subgroup of G

you understand that in order for A ∪ B to be a subgroup of G you need A ∪ B to be closed under addition (among other things), right?

[feral osprey]

oh. I see thanks

[feral osprey]

Can someone give an example of a cyclic subgroup?

[stray reef]

cyclic subgroup of what?

[feral osprey]

any kind? I don't unerstand it, at all

[stray reef]

...

do you mean that you want an example of a cyclic group?

[feral osprey]

yes

[stray reef]

okay sure

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, with addition modulo 10

[feral osprey]

@stray reef Are they're a subgroup of Z?

[stray reef]

no, this group is not a subgroup of Z

[feral osprey]

I was looking for a cyclic subgroup

[stray reef]

a cyclic subgroup of Z?

[feral osprey]

A cyclic subgroup in general

[stray reef]

there's no such thing as a "subgroup in general"

it's always "subgroup of <group>"

just like there's no such thing as a "subset in general"

[feral osprey]

alright, a subgroup of Z

a cyclic subgroup of Z

[gritty crescent]

2Z

Even numbers under usual addition

[feral osprey]

@gritty crescent How is it a cyclic subgroup?

[gritty crescent]

Might be off here

Okay yeah

This group is isomorphic to Z itself if I'm not wrong

(And 2/-2 are generators)

[feral osprey]

pretty much my issue

[naive mural]

The cyclic subgroups of Z are just nZ since nZ=<n>

Cyclic just means generated by a single element

It doesn’t have to cycle back around

[feral osprey]

huh

[naive mural]

Yep

[feral osprey]

Alright the question i have is I've got a group G
wth objects a,b∈G with an ending limit
that gcd(o(a),o(b))=1
show that : ⟨a⟩∩⟨b⟩={e}

[naive mural]

You’re a bad cheater

[feral osprey]

It's a practice test question

[naive mural]

Right

[feral osprey]

Can you help me? You don't have to give the solution just explain the concepts given

[naive mural]

No

Ask me tomorrow when the test is finished

[feral osprey]

It's not a test, and fine

Assuming I won't find someone to help me than

[naive mural]

It’ll be faster to just think for yourself

[feral osprey]

I can't if I don't understand the question

[naive mural]

Goodluck

[gritty crescent]

Do you understand what the question is asking of you?

And the hypothesis given to you?

[feral osprey]

I don't. That's why I'm here

[gritty crescent]

Do you know what the order of an element is?

[past gate]

On 3 shelves there vertically,one under another you need to put n compact disks.In each of the shelves the compact disks are put vertically one after another.Each of the shelves can have n disks.how many different ways are there for the disks to be put?

[feral osprey]

@gritty crescent I don't

[past gate]

Does anyone maybe know this one?

[gritty crescent]

Then I'm afraid you'll have to go back and see some of group theory first. I would have to write out the entire answer otherwise, and I'm not willing to give it away.

[feral osprey]

@gritty crescent fully aware of that, can you link me anywhere?

[gritty crescent]

Sure. If you're looking for a book, Dummit and Foote's Abstract Algebra is great, you could look into the group theory part.

For video lectures, there's a playlist by ICTP on Abstract Algebra, another one by Richard Borcherds, and yet another one by Daniil Rudenko. They would be insufficient by themselves, but supplemented by the above book, they might help.

[feral osprey]

Hmm. Well assuming for now just to understand the question, what would be the laconic material I need to go over?

[gritty crescent]

The definition of a group, some examples of groups, order of element/group and some other elementary results.

[feral osprey]

definition of a group is that is a set based on a function that is enclosed within that set. (there's also that the function needs to be associative)

(Z,+) is an example of a group

[gritty crescent]

You also want inverses to exist

[feral osprey]

inverse : a+b=b+a?

[gritty crescent]

This is commutativity

[feral osprey]

Forgive my ignorance

[gritty crescent]

And it need not be present in every group(groups which obey commutativity are called Abelian or commutative groups)

[feral osprey]

(a+b)+c=a+(b+c)

Right, so the main issue, I was sitting with a classmate trying to explain order of element

Didn't understand

[gritty crescent]

A set G together with a binary operation • is a group if:

1. It is closed under •, that is, for every a and b in G, a•b is in G. This is called closure.
2. • must be associative. For any elements a, b, c in G, a•(b•c)=(a•b)•c. This is called associativity. Addition of real numbers is associative, while division of real numbers is not.
3. There exists an element e in G such that a•e=e•a=a. Element e is called the identity element. (Exercise: prove that the identity element in a group is unique)
4. For every element a in G, there exists an element b such that a•b=e. Element b is called inverse of a, and is often denoted as a^(-1) or -a depending on context. (Exercise: prove that inverse of a given element in a group is unique.)

So putting this in the context of (Z,+), you can see that

1. Adding two integers gives an integer, so we have closure.
2. Addition of integers is commutative.
3. We have 0 as an additive identity within the integers. Adding 0 to anything makes no effective change.
4. Corresponding to every integer c, you can find -c such that c+(-c)=0.

[past gate]

Guys can anyone help me with my combinatorics problem?

[gritty crescent]

The channel is currently occupied, you can ask in one of the general question channels or wait.

[feral osprey]

@weary tiger oh nice

@gritty crescent Great info. So how do I know the order of any of the elements?

[gritty crescent]

Are you sure you understood everything above?

It'll be built on top of each other, you can't hop on to order without understanding what a group itself is

[feral osprey]

Yes, it's just practice from here

[gritty crescent]

Try proving the two claims I marked as exercise

[feral osprey]

unique means there's only such element or that there's one for each element?

@gritty crescent What's the definition of unique? so far in the course we used those claims as a given fact

[gritty crescent]

There's only one such element in the entire group, in case of identity, and corresponding to each element there is only one inverse.

[feral osprey]

alright, on it

[gritty crescent]

So like, 0 is the unique integer such that 0+b is b, you have to prove that identity in a group is similarly unique

[feral osprey]

Exercise: prove that the identity element in a group is unique
assume there's two identity elements e and a
what will e*a=?

[gritty crescent]

Sure. e•a will be a since e is identity. Similarly, e•a will be e since a is identity. Hence, e=a.

[feral osprey]

lol. forgot to mention false assumption a!=e .

[gritty crescent]

You don't need it

Uniqueness proofs generally don't need this hypothesis

If you take two things that satisfy a common set of properties and show that they're one and the same, you've established uniqueness.

[feral osprey]

Oh... I see

[gritty crescent]

Over here we applied the definition of identity twice-once on a, once on e. We got the desired uniqueness from that.

[feral osprey]

(Exercise: prove that inverse of a given element in a group is unique.)

let's use a and b elements in G
and their inverse (-a) and (-b) accordingly.

so a * (-a) = b * (-b) = e
we'll put (-a) = (-b)

a* (-a) = b * (-a) =e
a * (-a) = b *(-a)
a = b

So inverse of a given element in a group is unique or else the elements are the same

[gritty crescent]

You have to take a single element

And suppose it has two inverses

[feral osprey]

oh

a * (-a) = a * (-b) = e
a * (-a) = a * (-b)
(-a) = (-b)

So yeah, group seems to be nailed from your text

So how do I find the order of an eleement?

[gritty crescent]

This argument won't work

This assumes cancellation

We don't have cancellation at our disposal yet

[feral osprey]

right

[gritty crescent]

Hint: try exploiting associativity.

[feral osprey]

a * (-a) * c = a * (-b) * c = e * c
a * ((-a) * c) = (a * (-b)) * c = e * c

e = a = a * (-b) ; c = (-a) * c = c
e = a ; c = (-a) * c

e = a

e * (-a) = e * (-b) = e

(-a) = (-b) = e

I have no idea what I'm doing at this point

The only way it seems in which a will have to difrent inverses will be if a=e

or a is the identity

[pale epoch]

🤔

what are your variables even

[gritty crescent]

Yeah, at this point your variables are not super clear.

[pale epoch]

and like

why do you glue minus signs in front of them

at this point its not clear what -a means

[feral osprey]

right

let me write it

again

[pale epoch]

(if you dont know that a has a unique inverse, and -a is the inverse of a)

so you should start with b, c both being inverses of a and derive b = c

[feral osprey]

a and c are elements in G
(-a) and (-b) are both inverses of a and inverse of an element isn't unique
e is the identity element of G on function *

as such
a * (-a) = a * (-b) = e

we'll try using c to check via associativity to simplify by functiong *c at the end

a * (-a) * c = a * (-b) * c = e * c
We'll put bracets for associativity
a * ((-a) * c) = (a * (-b)) * c = e * c

a = a * (-b) = e ; c = (-a) * c = c
e = a ; c = (-a) * c

therefore e=a and (-a) = e

e = a

e * (-a) = e * (-b) = e

(-a) = (-b) = e

[coral raven]

no, stop that

you don't need two separate elements that aren't inverses of each other or whatever

[feral osprey]

I need c as a placeholder

[coral raven]

just focus on a

and use b and c as the two inverses

[pale epoch]

also dont glue minus signs on your variables for no reason

[feral osprey]

(-a) just means inverse of a

[pale epoch]

what does that mean

[coral raven]

use b and c please

[pale epoch]

that requires unique inverses

if you have two different inverses, which of them is -a

[coral raven]

easiest just not to use minus signs

just talk about a, b and c

that's all you need

[feral osprey]

it's to prove that inverses are unique

[coral raven]

yeah

[pale epoch]

yes, then you cant talk about the inverse of an element

[feral osprey]

I falsely assumed they aren't

[coral raven]

please

use a, b and c

[pale epoch]

honestly this is a one line proof (if you know that inverses are two sided)

consider ||b*a*c||

[feral osprey]

But we don't know if * is two sided

@pale epoch How'll you prove it in one line?

[coral raven]

what do you mean by * being two-sided

how can an operation be 'two-sided'

[feral osprey]

sum and multiplication

[coral raven]

sorry what

no, define two-sided for me real quick

[gritty crescent]

If b is an inverse for a, a•b=b•a=e

[pale epoch]

if b*a*c is not enough, you need to take a step back, take a break and start again tomorrow

[feral osprey]

mistaken Commutative with two sided

[gritty crescent]

See Nightchanger, it will take some time to build up the background for your problem.

[coral raven]

ohhhhhh

[gritty crescent]

Especially if you still have difficulty with proving these results

So try to pick up a standard text

And do some problems

And try your problem afterwards

[pale epoch]

but well, as i said you should prove that right-sided inverses are left-sided as well and vice versa

and tbh this isn't that important

it's just some standard manipulations that you can just look up

(although not being able to do them probably means you can't manipulate group elements abstractly properly yet)

[weary tiger]

Each output of a computer program is a randomly selected integer. How many integers must be output to guarantee that either ten integers are multiples of 6, nine integers have a remainder of 1 when divided by 6, eight have a remainder of 2, seven have a remainder of 3, six have a remainder of 4 or five have a remainder of 5?

I know I have to use the pigeonhole principle to solve this problem, but I don't know how.

[obtuse lance]

try to maximize getting the worst case scenario

[weary tiger]

We have none of the above?

There are infinitely many multiples of not 6

[obtuse lance]

sure but any number will satisfy at least one of those conditions

[weary tiger]

Is the "or" at the end supposed to be "six have a remainder of 4" OR "five have a remainder of 5"?

[obtuse lance]

yeah, that's how I'm reading it

it is kind of ambiguous in that sense, kind of annoying lol

[weary tiger]

I don't know how to maximize the worst case scenario...

[obtuse lance]

well a number must be 0, 1, 2, 3, 4, or 5 mod 6

[weary tiger]

It's possible that 9 don't have a remainder of 1 nor 2 nor 3

[obtuse lance]

and so when it is it fills up one of those buckets

you want to fill up all the conditions until they're one away from being filled

then you know the final one will top off the last bucket no matter what

[weary tiger]

So we want at most 9 integers???

I am so confused

[obtuse lance]

maybe work a simpler problem to practice pigeon hole principle

or maybe you don't understand what the question is asking, I'm not sure

[weary tiger]

Yeah I don't

I mean

I don't know how to apply your advice to it

Are you talking about only the remainder conditions being 1 away?

[obtuse lance]

imagine each remainder condition as being a bucket

if I give you the number 11 then you put it in the bucket that's labeled "has remainder 5 when divided by 6"

how many more numbers with remainder of 5 do you need to fill this bucket?

[weary tiger]

I mean you'd need something that has remainders 0,1,2,3,4 as well

So 5

But some integers can clash with each other

[obtuse lance]

no

just that bucket alone

[weary tiger]

For example, 2 has remainder 2 when divided by 6

3 has remainder 3

[obtuse lance]

you have 6 distinct buckets

each with different levels that it takes to fill up

there are no integers that can class with each other

2 only goes in the remainder 2 bucket

3 only goes in the remainder 3 bucket

no number goes in multiple buckets

[weary tiger]

Why not?

[obtuse lance]

a number only has one remainder when divided by 6

[weary tiger]

lol

[past gate]

I have a bothering combinatorics question as well

how many ways can you arrange n nondistinct objects into 3 distinct containers?

[obtuse lance]

channel's occupied, try a question channel

[weary tiger]

But I'm confused still

[past gate]

Wait,lets try and help n/c first.

[weary tiger]

You could have something like

Basically you could have infinitely many that don't have remainder 1

So I don't have know what the worst case scenario would be

[obtuse lance]

doesn't matter, it has to have some remainder

no matter what number you get, it's gonna have a remainder of 0, 1, 2, 3, 4, or 5

[weary tiger]

Yeah

[obtuse lance]

so it goes in one of the buckets

[stray reef]

what's our condition again

10 in residue class 0, OR 9 in residue class 1, OR 8 in residue class 2, OR 7 in residue class 3, OR 6 in residue class 4, OR 5 in residue class 5

did i get that right?

[weary tiger]

I don't konw

It's not written in logical symbols

[stray reef]

you're the one with the problem, how can you not know

[weary tiger]

Because it's given in text

[stray reef]

does the word "or" somehow become an arcane incomprehensible symbol when capitalized?

[weary tiger]

They use comas

[stray reef]

they use a comma-separated list with the word or before the last item

you may find reading comprehension is a useful skill

[weary tiger]

Wouldn't the way you've written it mean that if we just get 10 multiples of 6, we're done?

Or 5 integers with remainder 5?

[stray reef]

presumably, yes.

[weary tiger]

Since the whole chain would be true

[stray reef]

yes.

it's impossible to guarantee that all six of these conditions will be true

even with <ungodly large number> integers you could be astronomically unlucky and end up with them all in one class, leaving the other classes empty

[weary tiger]

We could pick 10 in residue class 1

9 in residue class 2

8 in residue class 3

7 in residue class 4

6 in residue class 5

5 in residue class 0

[stray reef]

and?

who cares

[weary tiger]

And I don't know

[stray reef]

your condition is a bunch of statements connected with OR

[weary tiger]

Never mind I think I got it now

[stray reef]

in order for the condition to NOT be true, all these statements must be false

by de morgan's law

[weary tiger]

We can pick 9 integers with residue 0

[past gate]

In order OR to be false,all need to be false.

[weary tiger]

8 with residue 1

[past gate]

Yeah exactly Ann

[weary tiger]

7 with residue 2

[stray reef]

you can pick one less in each residue class than the requirement calls for.

[weary tiger]

... and so on until 4 with a residue of 5

It's so simple lol

[stray reef]

yes, it is.

[weary tiger]

So the answer is just 9 + 8 + 7 + ... + 4

[stray reef]

all it takes is reading comprehension.

that plus 1.

9+8+7+6+5+4 is the max you can have without the condition being true.

[weary tiger]

I see, so we pick any other integer that hasn't been picked which will make it true

[stray reef]

that's not quite what i had in mind wording-wise

[obtuse lance]

sounds like a fundamental misunderstanding of the problem still tbh

randomly selected integers from the computer program are not necessarily distinct

not that it matters really, but maybe that's what you're thinking

[weary tiger]

They don't have to be, but we're looking at each of the conditions in the problem

And we determined what was has to happen for each condition to be false

But very close to true for a lack of better wording

[weary tiger]

@obtuse lance

[weary tiger]

Let S = {1,2,...,n} and let m and r be integers such that 1 ≤ r < m < n. For an r-element subset A of S, determine the number of m-permutations of S in which all elements of A appear.

This question has multiple answers?

For example, look at S = {1,2,3,4,5} and A = {1,2}

Then 123, 132,... has 6 permutations (m = 3)

And 1234,1243,... has 4! = 24 permutations (m = 4)

But both of these satisfy the problem, with the same sets A and S

[pulsar thunder]

can anyone help me with this one? this is about triangular numbers

[errant bear]

draw a picture, er more like a grid/array

both should follow from it

[pulsar thunder]

is this correct?

[young wasp]

start small

[pulsar thunder]

so the formula for Tn in terms of n would be : Tn = 1 + 2 + ... + n ??

[young wasp]

you're trying to find a recurrence relation

start with the base cases

then gradually increase it

then you can relate with n and Tn

here the relation you need to find is T(n) = T(n-1) + n.

[weary tiger]

Can anyone help me with the question I posted?

I don't understand what the problem is asking