discrete-math

[quick axle]

24 <= n <= k+5a+7b

where it could be multiples

of a and b or just one

[dire obsidian]

which makes it work

[quick axle]

any

the reason why they went with n = k - 1

was because that's the simplest case

24 + 5 = 29

[dire obsidian]

what do you mean by 'any' we literally just shown that n=k-5 doesn't work

[quick axle]

so k +1 >= 29 where k >= 28

[dire obsidian]

what???? we can't use 'any' we literally just concluded that for IH n=k-5 doesn't work...

I think how it works is that it has to be

IH n=k-(whatever is lowest component)-1

so that you can account for the offset

[cerulean wind]

it’s not that he’s choosing k-4

it’s just what pops out

[quick axle]

I think it should be + 1

n = k - ( lowest component) + 1

[dire obsidian]

but n=k-4 working disproves that

[quick axle]

Isn't that just n = k - 5 + 1 ?

where k >= 29

[cerulean wind]

he could have done
k + 1 = [(k + 1) - 7] + 7 = (k - 6) + 7. if you check the first 7 numbers, through 30, then this works

[quick axle]

24 + 5 = 29

[cerulean wind]

nobody is “picking” anything for n

[dire obsidian]

ah right mb

[dire obsidian]

you have to pick or else it doesn't match in IS I showed this using n=k-5 for IH already

[cerulean wind]

you use n = k for IH assuming that it holds for all m <= k and then show it for n = k+1. there is no picking for the Ih. it’s just using the fact that it works for k - 4 or k - 6 <= k, whatever those numbers may be

[quick axle]

We could try with 7:

n = k - 7 + 1 => n = k - 6
for k >= 31

so
We assumed k - 4 to be our inductive hypothesis:
k - 6 + 2 = [(k-6) + 2] - 2
=> [(k-4)] - 2
=> k-4 can be expressed as a sum of 5's and 7's via inductive hypothesis, so k - 6 can be expressed as a sum of 5's and 7's

[dire obsidian]

I thought the main reason why it works is because of the fundamentals of how you prove this type of problem. You need to offset the (k+1)

[quick axle]

🏳️

good luck

[dire obsidian]

I hate grimaldi

[dire obsidian]

it gets even worse when we get into divisibility proofs

and euclidean algorithm I hate that thing so much

[quick axle]

euclidean algorithm isn't difficult

[dire obsidian]

wait

[quick axle]

I suppose this is for gcd?

[dire obsidian]

can you explain

yeah

[quick axle]

Yea

[dire obsidian]

gcd lcm

cancer for me

please teach me your ways

wise one

For instance, I have absolutely 0 idea what is going on in this proof

[quick axle]

Suppose you have two numbers a and b.

The euclidean algorithm finds the GCD via:

gcd(a,b)
=> a = b(greatest positive integer possible) + positive integer (this is called the remainder)
b = remainder( greatest positive integer) + positive integer and so forth till you get the remainder to be 0

lol your example looks hard

lmao

[dire obsidian]

I hate grimaldi

[quick axle]

this has to do with the transitive property or something

[dire obsidian]

I have 0 idea what is going on

I miss set proofs

those were 'easy'

[quick axle]

We let
gcd(a,b) = g
gcd(na,nb) = h

gcd(a,b) = g is just the same thing as the formulaic representation:
g = as + bt, where s and t are integers

gcd(na,nb) = h can also be represented the same way:
h = (na)s + (nb)t
h = n(as) + n(bt) => ng = n(as)+n(bt)

so we can get ng = (na)s+ (nb)t or h = ng

so that gives us that ng is divisible by h

since ng = h

the second part is just repetition lol

same thing for third part

h1 = h/n

[dire obsidian]

what is the reason you can use the same s and t?

[quick axle]

we're trying to prove they're equal

the formula

[dire obsidian]

I see

[quick axle]

if they're equal, they must use the same s and t

[dire obsidian]

What kind of frame of mind should you have when you are trying to prove stuff with euclidian algorithm?

[quick axle]

depends what you're trying to prove

lol

[dire obsidian]

what are the possible variations?

[quick axle]

let me check my previous lectures

i forgot

[dire obsidian]

thanks a bunch

euclidian algorithm is bane of my existence rn

[quick axle]

i don't think you could do much with Euclidian algorithm actually

it was the divisibility def

my prof used it to prove that all n >= 2 is either a prime or can be factored into primes

he also used it to prove if all integers are either even or odd

division algorithm is the same as euclidean algorithm ngl

[dire obsidian]

yeah euclidean algo is gcd

Something like this is also extremely confusing for me

wack af

[weary tiger]

Could I get help in figuring out how to solve this please?

[cerulean wind]

what happens if x in B? what happens if x not in B?

[weary tiger]

I'm not too sure, idk where to start on this question

I'd appreciate any help in going through it tho

[cerulean wind]

if x is in B, then x is in A and …

[weary tiger]

and if x isn't in B, then it's also not in the power set of A?

[cerulean wind]

um. that’s true, but completely irrelevant

just look at the definition of B. write out what it means for x to be in B (here, we have f(x) = B). if x is in B, then x is in A and x is not in f(x) = B… this is a contradiction.

find a similar contradiction if x is not in B

[weary tiger]

If x∉B:
Then x∉A and x∈f(x)=B. This is another contradiction.

Is this right? @cerulean wind

[cerulean wind]

yes

well

x is still in A

[weary tiger]

oh so we only consider that its saying, f(x) is in B so you cant say x is not in B

[cerulean wind]

i’m not sure how to interpret that

i was emphasizing x in A because i wanted u to finish off my line of reasoning

B is a subset of A. x is an element of A. x is either in B or not in B. in either case we get a contradiction

[weary tiger]

shit i didnt look at that middle line where it states x is in A

So by using these two cases of x in B and not in B

if they're both proven wrong by contradiction, is there anything else I'd need to state to finish off the original proof by contradiction that A implies the power set of A?

[cerulean wind]

*proof that there is no onto function from A to P(A). no. that’s it. you have reached a contradiction in both cases. this is impossible.

[weary tiger]

Cheers, appreciate the help

looking back at it, it shouldn't have been as hard as I thought it was initially

[sullen vessel]

Would anyone be able to have a quick look at this proof and let me know if they think its ok? Im not great at induction so Im just wondering if i have actually proven what ive tried to and if ive been clear about it, Its a proof that every non empty finite set has as many even sized subsets as odd

(If anyone feels sketchy about downloading the PDF i can post screen shots the PDF was just easier)

[proven silo]

what does mentioning amount of subsets do?

the important thing is {a_1,...,a_k} has the property from induction hypothesis and if adding a new element then you make the even odd and the odd even

[sullen vessel]

I thought it was useful just because it shows that we are accounting for every element of the new set, but i suppose youre right its not really relevent, i have satisfied the induction hypothesis though yeah?

[proven silo]

Si

[dire obsidian]

Can someone explain this proof to me?

Also what are the principles and laws I need to know for euclidean algorithm proofs? My textbook sucks (grimmaldi) and my prof's lectures are also confusing af so I just want to ask here

[spring zephyr]

hey i needed help with a problem

i cant figure it out at all like im so lost

how do i find the big o of n+log(1+n^2)

[proven silo]

Could you do it if it was n+log(n^2) for example?

[spring zephyr]

not really i havent done big o of anything that involves log

a workthrough would be very helpful

[proven silo]

Look at lim n->inf of log(n^2)/n

That shows which term is dominating

[spring zephyr]

well i can intuitively say that the big o is n^2

but proving it is the issue

[proven silo]

n^2 is not a term

[proven silo]

And do what I said

[spring zephyr]

well cant i say that log(1+n^2) <n for any n>=1

[proven silo]

If you actually know that

You can

Looking at a graph or whatever is not knowing it

[dire obsidian]

Can someone explain this proof to me?

Also what are the principles and laws I need to know for euclidean algorithm proofs?

[quick axle]

If they're equal, they should share a common divisor

[dire obsidian]

can you elaborate?

[compact hound]

@dire obsidian do you still need help on understanding that proof

[dire obsidian]

definitely

still stuck af

@compact hound

[compact hound]

Sure. Lemme switch to my laptop real quick and walk you through it

Do you understand the basic divisibility properties or no

[dire obsidian]

Kind of

My prof lectures are confusing af and my textbook also sucks at explaining

so I'm really stuck in eudlidean algo proofs

[compact hound]

Alright for sure. I’ll start from scratch then

[dire obsidian]

Thank you so much

I also kind of need a brush up on the principles and laws I need to know

I get the divisibility thing I think

[compact hound]

Yeah for sure. Gimme a bit to walk to a library. I just got out of a class and connection where I’m at rn isn’t good enough for computer

[dire obsidian]

$a \mid b \implies a=bx, x \in Z$

[compact hound]

I’ll @ when I’m all set up

[dire obsidian]

aight

[vital dew]

Salt

[compact hound]

@dire obsidian Alright, so to recap the definition of divisibility. a|b means that a divides b. Aka a is a factor of b

[dire obsidian]

yup

[compact hound]

Intuitively speaking then, we get this

$a|b \implies ak=b$ where $k \in \mathbb{Z}$

[vital dew]

3K

[dire obsidian]

yeah

[compact hound]

Alright cool. So, there's a property of divisibility that I'll prove real quick. If a|b and a|c, then a also divides a sum of multiples of a and c

So the example proof has that proof as the first one. Lemme show a quick proof for it

[dire obsidian]

ok

[compact hound]

Suppose $a|b$ and $a|c$

[vital dew]

3K

[compact hound]

By the definition of divisibility, then $ak=b$ and $aj=c$ for some $k,j \in \mathbb{Z}$

[vital dew]

3K

[dire obsidian]

yup

[compact hound]

We can multiply $ak=b$ by some integer $x \in \mathbb{Z}$ and $aj=c$ by some integer $y \in \mathbb{Z}$. Then we get $a(kx)=bx$ and $a(jy)=cy$

[vital dew]

3K

[compact hound]

We can then add these two equations together to get $a(kx)+a(jy)=bx+cy \implies a(kx+jy)=bx+cy$

[vital dew]

3K

[compact hound]

Note that kx+jy is an integer as it a sum of a product of integers. So it satisfies the definition of divisibility. So, $a|bx+cy$

[vital dew]

3K

[compact hound]

So that's the first part. And it's a similar situation for the whole r|b and r|d part

You would do the exact same thing but subtract equations instead. Teacher seems to be fine with you using the properties without proving them, but that's why that property works if that's all cool so far

So we've gone over this stuff so far

[dire obsidian]

I'm trying to compartmentalize this give me like 3 minutes

[compact hound]

Yeah for sure

I can write it up in latex if you want it all together in one image then separated by text too. Just lemme know

[dire obsidian]

why was it necessary to multiply by x and y?

[compact hound]

The reason for that was to show that if you know that some number, in this case a, divides two things

[dire obsidian]

does
$a(k)+a(j)=b+c \implies a(k+j)=b+c$ work?

[vital dew]

Salt

[compact hound]

Then it also divides the sum of products and yep you got it

You could add the two initial ones to say $a|b+c$

[vital dew]

3K

[dire obsidian]

a|(b+c)

a|b a|c
ak=b
aj=c

so ak+aj = b+c
a(k+j) = b+c

[compact hound]

exactly

[dire obsidian]

so I'm also utilizing the principle where I can randomly assign integer values to the divisibility statement?

that part is also kind of wack to me

I can only assign it to the left side right?

because right side would screw things up

[compact hound]

So you're not randomly assigning integer values, but let's try to think of it intuitively

And I think I get what you're saying, but yes

[dire obsidian]

so if 30 is divisible by 5
30*4 is still divisible by 5

[compact hound]

The left side will always be a| (something)

Exactly

[dire obsidian]

but I can't say the same thing for right side

if I mult the right side it will screw things over

[compact hound]

Nah you are still good

Let's take a look at the whole 5|30

[dire obsidian]

if 30 is divisible by 5
30 is not divisible by 5*10

ok

[compact hound]

Remember that 5|30 is completely different from 30|5

Divisibility doesn't go both ways it is a one way street

5|30 says that there is SOME integer that multiplies against 5 to get 30 (5*6)

30|5 says that there is some integer that multiplies against 30 to get 5, which isn't true

So when you have 5|30

[dire obsidian]

ah

[compact hound]

And then multiply both sides by 4

You still have 5|30*4

If we wanna write it out. From 5*6=30 aka 5|30

[dire obsidian]

wait what

[compact hound]

We would get 5 x 6 x 4=30*4

[dire obsidian]

if you multiply both sides by 4

wouldn't it become

20|120

[compact hound]

That is true as well

But also notice that 5 is a factor of 120 too

The biggest trick with this is that you purposefully group numbers together to still say 5|120

Let's start with what you are saying. 20|120 is definitely true

So this says 20*6=120

We can break up the 20 to get 5*4

[dire obsidian]

yup

[compact hound]

So we have 5x4x6=120

4x6=24

So, we have 5*24=120, which means that we can say 5|120

[dire obsidian]

so you just divide the other side after multiplying to see if it still works

[compact hound]

So when you take that 5|30 and multiply by an integer you want, 5|30 * (new thing) will still be true

[dire obsidian]

basically what you did here is 120/5 = 24

so 5|120

[compact hound]

Yeah you can think of it like that

Intuitively it makes sense and then our proof formalizes that thing

[dire obsidian]

I'm still confused about ak = b though

wait ak|b

because it looks to me you are just multiplying one side

[compact hound]

ak=b is the definition of divisibility from a|b

[dire obsidian]

oh right

[compact hound]

if we multiply by whatever integer we want we would apply the same logic we did for the 5|30 example

So if we take a|b, ak=b, and multiply by c

[dire obsidian]

so with divisibility you can't multiply only one side

[compact hound]

We get ac|bc, akc=bc

[dire obsidian]

but theoretically I think multiplying right side only works

[compact hound]

You can group the akc=bc to get a(kc)=bc, so a|bc

Divisibility still follows algebraic properties. So whatever side you multiply one thing by you have to multiply by the other

I would be careful of thinking of it in that manner

But in terms of going from a|b to a|bc

You can think of it that way

[dire obsidian]

well like I said if we have

5|30

5|30*C would still apply

[compact hound]

But I would strongly recommend to think of how it works from definitions

[dire obsidian]

because 5 already takes care of entirety of 30

doesn't matter how many 30s there are

[compact hound]

Exactly

You got it

I think we're on the same page, but using different language

[dire obsidian]

But this example I'm giving is like only multiplying by right side

I don't think multiplying only left side works

but only right side should work

[dire obsidian]

you treat c as both an integer and a variable?

[compact hound]

5|30 does indeed not imply 5C|30

[dire obsidian]

yeah

[compact hound]

c is an arbitrary integer

[dire obsidian]

I'm confused why you are allowed to just remove the kc

[compact hound]

Whenever you're working with divisibility properties, you'll assume everything you're working with is an integer

Unless specified otherwise

[dire obsidian]

since left side is more strict than right side

[compact hound]

So the definition of divisibility states that a|b implies ak=b for some integer k. Note that a and b are also integers

So if you have integer times some other integers = integer, you can use the definition of divisibility to say that they divide

So like if you were given ak=b

and a,k,b are all integers

you could say a|b

[dire obsidian]

ok so you treat (kc) as k

[compact hound]

so when we have akc=bc. I grouped kc to be one big integer

Exactly

So that's why I wrote it as a(kc)=bc to show the grouping. So you can say a|bc

[dire obsidian]

why exactly are you allowed to leave behind one c

actually ok

so lh side is allowed to do a(k) groupings

to manipulate stuff

while rh side is allowed to multiply by anything

[compact hound]

Exactly. This technique comes up a lot in divisibility proofs

You're multiplying by stuff to keep the left side the same

In our case a|

And then you're manipulating right side to be something else

[dire obsidian]

the part that gets me is proportionality because you still have a c left over in the rh side

[compact hound]

So that's how your teacher got the whole a|bx+cy from a|b and a|c

[dire obsidian]

I'm kind of having trouble wrapping my head around that

like is it actually true that it still divides

if we leave behind the c on the rh side

and group up the kc on the lh side

[compact hound]

Yep it still does

Think of it back with your number example

5|30 means 5*6=30

Multiply by 4, we get 5x6x4=30x4. Group the 6 and 4 to get 24

That 4 is still on the rh side and we grouped the 6,4 on the lh side

But 5 still divides 30x4

[dire obsidian]

I see

[compact hound]

Same case with arbitrary integers

[dire obsidian]

because the actually important part is 5

as long as you have the 5 it is

basically divisible

[compact hound]

Yep

Here is some good basic divisibility properties that are helpful to know

That we covered

The last one is what your teacher used. So, from that

He/she could say this part

Note that he/she did specify a,b,c,d have to be positive integers

This is just because he defined r to be a greatest common divisor of b and d

And a greatest common divisor isn't negative

So he/she is just stipulating that to avoid problems

[dire obsidian]

I'm confused at step 1 how you know immediately to use a|b and c|d in the proof

[compact hound]

The reason why he knows that r|b and r|d is because r is the greatest common divisor of b and d

So r obviously divides both b and d

And then he/she applies the property we found to say r|d-bc

[dire obsidian]

it's a he

[compact hound]

So your teacher used the first thing we showed because they were given that d=a+bc

Alright cool

[dire obsidian]

I thought the d=a+bc is a twisted version of gcd?

also isnt r|d-bc
basically r|a?

How do you prove that?

[compact hound]

In this case d is just a positive integer

And yes exactly

[compact hound]

This is because he defines it in the beginning of the question as such and not as a gcd

[compact hound]

So do you understand the r|d-bc part or do you wanna go over that still

I can write it up in latex rq if you want

[dire obsidian]

yeah I'm also confused why you can just go ahead and say a|c first step in the proof

I get gcd(a,b) shows s|a, s|b

but

idk how it leads to step 1

[compact hound]

So your teacher is just referencing the first part as a property of divisibility

So he can say the whole r|d-bc stuff

Lemme write up your teacher's proof being overly formal

Or at least writing more stuff

[dire obsidian]

Ok i have to confess this is not my prof's proof he never did any of this stuff in class.
(he just threw us the tb exercises then said 'good luck')

It was stuff I copied online

[compact hound]

Hahahahahaha it's all good and no problem

Discrete can be rough. I'm assuming this is your first time doing proofs? It's usually this or some number theory class for most people

[dire obsidian]

I'm kind of new to this kind of proof

Set proofs are so much more understandable

[compact hound]

Ahhh gotcha

[dire obsidian]

Honestly discrete needs good prof that can explain stuff clearly. I didn't have this much trouble in earlier chapters in my course

I do have this really good video lecture I watch online but that prof got sick when he was supposed to cover divisibility and euclidean

so i am completely in the dark for divisibility and eudlidean

grimaldi textbook sucks at explaining I honestly wish that dude never decided to write a discrete mathematics textbook

[compact hound]

😔

[dire obsidian]

There's no public video lecture on youtube that actually explains discrete mathematics deeply

trevtutor and kimberly are too surface level

this is why discrete math is hard no good teachers that can explain well

but you are doing stellar job I'm actually starting to understand this stuff thanks a bunch

but yes I'm still confused at the first step of the proof

Why you are allowed and how you know to go ahead and say

'If a|b and a|c'


Like what frame of mind caused this decision

[compact hound]

So I'm still writing up the latex proof, but basically it saves time

If you're allowed to use the property or prove it to use it

You save a lot of time

[spring zephyr]

I got this question wrong on a test

Could someone please walk me through this problem so I know what's wrong

[dire obsidian]

Dude can you wait until I am done

@compact hound we can take this to help channel

[compact hound]

For sure

[spring zephyr]

I'm not holding your hand off weirdo

[compact hound]

@ me in whatever help channel you want

[spring zephyr]

This is a public server

[dire obsidian]

damn I guess common courtesy doesn't exist in a public server shame

[spring zephyr]

I just asked a question you don't have to be a jackass

It's not like the person who's helping you will immediately jump to my question abandoning you

I don't have to scan the entire chat before sending a text

[dire obsidian]

Well I personally never intrude on someone who is currently trying to solve a problem in public channel (help channels exist for a reason) but whatever floats your boat I guess

[severe swan]

There are 26 letters in the English alphabet.

How many strings are there consisting of exactly 5 uppercase letters?

(Note--if a question does not mention any requirement about no repeated letters, then repeated letters ARE allowed.)

This looks to me that the answer would be 26^5 but that is not an option for the answers.

Here is how I see the problem:
If there are 26 letters in the alphabet and if you are looking for the 5 letters exactly then it would be 26 options for the first letter, 26 options for the second letter ect ... 26 letter options for the 5th letter in the string. I It looks like repeats are allowed.

My guess then is D if I am wrong and repeat letters are not allowed. D is the option that has if one letter gets used then it is taken away for the next letter in the string.

answers
A 24×23×22
B 26×25×24×23
C 25×24×23×22
D 26×25×24×23×22
E 26^3
F 26^4 G 26^5 H None are correct

[stray reef]

??? you say 26^5 is not one of the answer options, but option G says 26^5???

[cerulean wind]

f(n) = 1 + … + (n-1)^2 + n^2 <= n^2 + … + n^2 + n^2 = …

[stray reef]

@severe swan 26^5 is the correct answer and appears as option G in your list of 8 answer options

[sacred ore]

i want to ask a question but im not 100% sure if its for discrete math

can i ask it anyway?

[glacial lynx]

just ask

[sacred ore]

m=13

[cerulean wind]

25 = 13q + 38
25d = 52p + 38d

note that 52 = 4 • 13…

maybe try multiplying 25 = 13q + 38 by 4

[sacred ore]

Alright!

thank you so much

[hushed fiber]

A solid object formed by sticking the bases of two square
pyramids together. All the faces are isosceles (but not equilateral)
triangles of the same dimensions. (N.B. it is not a regular octahedron.)
The faces on the top pyramid are labelled 1, 2, 3, 4 in cyclic order. The
faces of the bottom pyramid are labelled 5, 6, 7, 8 with face i sharing
an edge of with face i + 4, for i = 1, 2, 3, 4. A top view is shown in
Figure 2 with the bottom pyramid being flipped over about the edge
shared by faces 1 and 5.
Find the group of geometric transformations that leave the solid invariant.

[hushed fiber]

since all the vertices have the same number of edges
I was thinking that the generator permutation will be (123456)
but the part that says "this is not a regular octahedron" is throwing me off

[tidal tulip]

If f: X->Y and g: Y->Z are bijections, find the inverse of g o f in terms of g and g. Prove your answer.

Proof:

Let,
f: X->Y
g: Y->Z
Be bijective functions

Since f, g are bijective functions then their composition (g o f) is a bijective function due to theorem . Due to another theorem we know that since g o f is a bijective function then there exist an inverse function (g o f)^-1.

We also have bijective inverse functions:

f^-1: Y->X
g^-1: Z->Y.

We will show that the inverse function (g o f)^-1 = (f^-1 o g^-1).

We will need to show that:

(a) (g o f) o (g o f)^-1 = z = g(f(f^-1(g^-1(z)))
(b) (g o f)^-1 o (g o f) = x = f^-1(g^-1(g(f(x)))

Proof of (a):

(g o f) o (g o f)^-1(z) = z

g^-1(g o f) o (g o f)^-1(z) = g^-1(z)

f o (g o f)^-1(z) = (g^-1)( z)

f^-1(f o (g o f)^-1(z) = (f^-1 o g^-1)( z)

(g o f)^-1(z) = (f^-1 o g^-1)( z)

?

Proof of (b):

i’m trying to prove (a) is this the right approach? i am getting (g o f)^-1(z) = x and not z and don’t see what’s wrong

[cerulean wind]

We will show that the inverse function (g o f)^{-1} = f^{-1} o g^{-1}

this part

just do this

without any z's

show that (g o f) o (f^{-1} o g^{-1}) = Id_Z and (f^{-1} o g^{-1}) o (g o f) = Id_X by using associativity

then f^{-1} o g^{-1} must be equal to (g o f)^{-1}

[tidal tulip]

checking

what allows us to use assoc

[cerulean wind]

function composition is associative

[tidal tulip]

how about this @cerulean wind

We will need to show that:

(a) (g o f) o (g o f)^-1 = id_z = (g o f) o (f^-1 o g^-1)
(b) (g o f)^-1 o (g o f) = x = (f^-1 o g^-1) o (g o f)

Proof of (a):

(g o f) o (g o f)^-1(z) = id_z

g^-1 o (g o f) o (g o f)^-1(z) = g ^-1 (id_z)

f o (g o f^-1) (z) = g ^-1( id_z)

(f^-1 o (f o (g o f^-1) (z) = (f^-1 o g^-1) (id_z)

(g o f^-1) (z) = (f^-1 o g^-1) (id_z)

what do i need to fix

[cerulean wind]

id_z is a function (it appears as if you are treating it as an element of Z)

there really is no need to use a variable z

at some point you messed up the parenthesis on (g o f)^{-1}

[tidal tulip]

i don’t see how to do it

can you show me for (a) km confused

from there i will attempt b using same method

[cerulean wind]

(g o f) o (g o f)^{-1} = id_z

f o (g o f)^{-1} = g^{-1} o id_z = g^{-1}

(g o f)^{-1} = f^{-1} o g^{-1}

there’s no “part b” after doing it this way

this is it

[tidal tulip]

ahhhh wow

a lot simpler than i thought

but don’t you have to show the other “side”

[cerulean wind]

nope

[tidal tulip]

like usually it’s f o f^- = something

f^- o f = something

how come you only can do one side

[cerulean wind]

you already know that the inverse function exists

if you found another expression for it, then you’re done

[tidal tulip]

oh

[cerulean wind]

starting from whatever “side” you want

[cerulean wind]

the method i was suggesting was coming from a different perspective

[tidal tulip]

isn’t f^-1 o g^-1 like a “candidate” for the inverse and you have to show both sides to show it’s actually the inverse

i mean i know i have a misunderstanding so trying to get rid of my confusions here lol

[cerulean wind]

that would be correct if you wanted to do it this way

but your way, we just obtained the correct expression

[median mica]

anyone know why 7 is the correct answer here?

[tidal tulip]

ok thx i’ll think this over- will ask more questions once i can unfortunately busy most of tonight but this puts me closer to understanding the

ty

[cerulean wind]

number of roots (with multiplicity) is the degree of the polynomial

[median mica]

OH OK, it has TWO roots that each have a multiplicity of 3, and ONE root that has a multiplicity of 1

thank you for that

[tidal tulip]

few questions: why don't you have an input element on the LHS? also isn't g^-1 = y and not z?

[cerulean wind]

i don’t have an input element on either side

[tidal tulip]

oh

[cerulean wind]

id_Z is the identity map on Z

[tidal tulip]

can you explain again why you dont need to do (f^-1 o f) and (f o f^-1) again

[cerulean wind]

because you showed that the inverse of g o f is exactly equal to f^-1 o g^-1 by ur method

[thin relic]

Hey guyes
I am stuck with this question
How to get the value of 'm' such that
(n/m) ^m is maximum? (both m and n are natural numbers)

[viral crown]

say, for this question, just a guess, but for anyone who knows how to do it, is the answer ||3||?

[severe swan]

Would this be correct?

[wide vine]

why are you doing 10^9? I assume your options are 1 or 0?

ohh

nvm

if it is 0-9 I guess that sounds right

[weary tiger]

I'm having a hard time differentiating different counting techniques. For this I thought you would have 6 places to have the 'i', and then 5^5 ways to permute the other 5 slots of the password? so 6*5^5?

[cerulean wind]

not permute, but 5^5 total strings of vowels to pick from

so yes, 6 * 5^5 total passwords to try

[weary tiger]

so this the answer i get back tho.

which, completely confuses me

[coral parcel]

6·5^5 overcounts passwords such as iiiiii that have more than one i.

[weary tiger]

yea but it says atleast one i?

am I missing something?

Six, 'i' for the password would be valid?

[coral parcel]

Sure, but iiiiii is just one possibility. However 6·5^5 counts it six times.

[weary tiger]

oh I see

Now I get where you are coming from.

As you would count each i distinctly

rather than once

[coral parcel]

The model answer looks like it's doing its best to camouflage the method behind obfuscating symbolism.

The idea is just: To count those strings that have at least one i, start by counting all strings and then subtract those that don't have any i.

This is useful because both those numbers are easy to get.

[weary tiger]

Right that makes sense,

Wish Zybooks just explained things a bit better

Feel like that should be one of those side annotations of a common pitfall/trap in a way of thought for these types of questions.

Thank you.

[weary tiger]

University math looks hard

[coral parcel]

All math that you haven't learned yet looks hard.

[stray reef]

@tardy comet there are 14 edges

[spring surge]

is there any algebraic elegant way or math definition to check if two permutations are the cycles of each?

[tidal tulip]

If f: X-> Y and g: Y-> Z are bijections, find the inverse of g o f in terms of f and g. Prove your answer.

i have if h:=gof we need to show

For all x in X, and for all z in Z

h^-1 (h(x)) = x
h(h^-1 (z)) = z

i got h^-1 (h(x)) i think but need help with the other

Proof of: h^-1 (h(x)) = x

h(x) = g(f(x)

g^-1 h(x) = g^-1 (g(f(x))

g^-1 h(x) = f(x)

f^-1 (g^-1 h(x)) = f^-1 (f(x))

f^-1 (g^-1 h(x)) = x = h^-1 (h(x))

Proof of h(h^-1 (z)) = z:

h^-1 (z) =

how do i finish this off

[wide vine]

can I get some confirmation as to if these look good regarding my answer. This is just a HW for my class.

Just making sure I am understanding the R to R. I believe the domain has to include all of R but the range just has to be a subset of R or could be all of R

so in all these cases, x must be valid for all R but our output just needs to be in the set R (could be all of R or a subset of R)

[proven relic]

Answer is c

Any value you enter you get an answer

While the other no for example in the first it can’t be negative inside the root

Can any one help me?

[visual tiger]

discrete math

S U T is NxN

are you given that x and y must be integers

[proven relic]

yes x, y are integers from N

[weary tiger]

p —>q is T when p is T and q is F.

Can someone explain because intuitively.
p—>q should be F
Because the statement reads
If p is true, then q is true
But p is T and q is F
Therefore,
p —> q should be F

[coral parcel]

p —>q is T when p is T and q is F.
No, on the contrary that is the single case where P -> Q is false.

[simple vale]

i have this sentence $\exists x \in \mathbb{R}: \x^2 = 5$. I know that is false but what counter example can i give to prove that?

Sorry, i'm trying to use latex but something is wrong

[coral parcel]

You should't have a backslash before the x.

$\exists x \in \mathbb{R}: x^2 = 5$ is true, by the way.

[vital dew]

Troposphere

[simple vale]

Oh, and why is it true?

[coral parcel]

The square root of 5 is an element of a R.

[simple vale]

Oh yeah, of course it is. Thanks. Just another question, can i prove that with a "math sentence"?

[coral parcel]

"Let x = sqrt5. Then x^2=5, Q.E.D."

[tidal tulip]

can i get a proof check

Let,
f: X->Y
g: Y->Z
Be bijective functions

We also have bijective inverse functions:
f-1 : Y->X
g-1 : Z->Y

Proof:

h := g o f: X -> Z is a bijective function due to theorem proven in class.
h-1 := (g o f)-1: Z -> X is an inverse due to other theorem in class.

Take any z in Z.
h(h^-1(z)) = z
g(f(h^-1(z)) = z
g^-1(g(f(h^-1(z)) = g^-1(z)
f(h^-1(z) = g^-1(z)
f^-1(f(h^-1(z)) = f^-1(g^-1(z))
h^-1(z) = f^-1(g^-1(z))

Thus, h^-1 = f^-1 o g^-1

can i get a proof check

@cerulean wind is this what you meant yesterday

[severe swan]

How can I solve this problem? Am I doing it correctly? I tried B but it was not correct.

[wide vine]

Are you sure if the question is looking for 0-9 as valid values or only 1 and 0. I see they say bit of string length 11. Maybe they are asking about a bit string which in a case like this would only have 0 or 1 as valid inputs

so instead of the 10^9 which you had because of the 0-9 values you would only have 1 or 0 and then you have 2^9

[tidal tulip]

can someone check this

[shadow geyser]

If I have a number 7 * (1 mod 20) + 8 * (1 mod 20) + 6, how can I show that this number is always 1 mod 20?

Can I assume that its 7 * (1 mod 20) + 8 (1 mod 20) + 6 * (1 mod 20) such that 7 + 8 + 6 = 21 mod 20 is 1 mod 20?

Please let me know if that's the right way to go about this problem

[viral crown]

i don't know if your method works but this is really easy to show when you consider that every number 1 mod 20 is a number in the form 20n + 1

[mental pecan]

I don't understand your question. mod in that case would be an operation, so 1 mod 20 would just be 1. Can you send a picture of your question?

[shadow geyser]

Imagine a number such that it holds the property 1 mod 20

So yeah as valley said 20n + 1 ig

[mental pecan]

how did you get fro mthat

[mental pecan]

to this

[viral crown]

technically you'd have to change one of them to 20k + 1 too

[shadow geyser]

wdym

[mental pecan]

like

that was the whole question?

[shadow geyser]

Its an induction problem but the inductive step is to show p(n+1) where 7 * an + 8 * an + 1 + 6 to be 1 mod 20

[viral crown]

what?

[shadow geyser]

Where the inductive hypothesis is that an is a number 1 mod 20

[viral crown]

why would you ever use induction for that

[mental pecan]

a_n?

[shadow geyser]

Yea

Sorry im kinda lazy

[mental pecan]

all g

[shadow geyser]

Required by the problem

[viral crown]

uhhhhh

wow

that sucks

[mental pecan]

not sure how 15a_n + 7 would be in the form 20n + 1 though

[shadow geyser]

Modulo properties

[mental pecan]

you should send the whole problem (in its entirety--preferrably a picture) so we can see if you are approaching it properly

this might be a (not so rare) case of https://xyproblem.info/

[viral crown]

@mental pecan is there a reason you would do induction over just this

[shadow geyser]

No its ok i think someone else said it was the correct approach

[mental pecan]

in this channel?

[shadow geyser]

At least @obsidian flicker

I asked in a help channel

[mental pecan]

oh then yeah it would be the correct approach

[shadow geyser]

And cogwheels said it was fine

I just used modulo properties

Just wanted to make sure that was fine

[mental pecan]

well even then can you send the whole problem

so we can see it

[viral crown]

yeah i do wanna see

[shadow geyser]

uhh

Ok

[mental pecan]

thanks

[mental pecan]

well you left out the part of it being floor n/2

[shadow geyser]

Yea dw about that part

[mental pecan]

don't u have to consider 2 cases for this

even n and odd n

[shadow geyser]

If n is odd then its 2k+1 such that its a_k+1 and if n is even then its 2k such that a_k

[mental pecan]

oh u already did the cases

[shadow geyser]

But by the inductive hypothesis k and k+1 are 1 mod 20 numbers

So yea

Like a_k and a_k+1

Are 1 mod 20 numbers

So at that point we just multiply and add with modulo properties and then yea

Thats 1 mod 20

[mental pecan]

well if n is 2k+1

then it would be a_2k

and the other one would be a_k

[shadow geyser]

No

2k + 1 + 1 all over 2 is k + 1

2k + 1 all over 2 is just k

k + 1/2 floored is k

k + 1 floored is k + 1

[mental pecan]

yeah but for the a_{n-1}

say n is odd

then it would be

a_{2k+1-1} = a_{2k}

[shadow geyser]

not sure why we care about a_n-1 though

Or how you can induct like that

If you start with p(1) you can only go to p(2)

You dont really know p(2) in this case

Because its a recursive defined function

[viral crown]

cauchy induction, no?

[shadow geyser]

Naw but this is recursion

Its impossible to reach p(2) without p(1)

Rather i should say

P(4) without p(3)

So i dont confuse with the base cases

[weary tiger]

i think they're referring to this

[shadow geyser]

Ya i think thats the recursion part though right

[candid fractal]

what would be a combinatorial interpretation of the cauchy product formula? (if the two series in question are generating functions). Some places say it represents the union of disjoint sets, while others say the union of disjoint sets is the addition of their respective generating functions, rather than their product. So which one is it?

[rugged bobcat]

could someone maybe verify my reasoning through this problem?

pretend C means subset idk i am at work rn

[dire obsidian]

How does this proof look?

[stray reef]

how did you get that s | na => s | a?

that's not true in general.

[dire obsidian]

It is I 'proved' it with 3K the day before yesterday

[stray reef]

so you assert that for all positive integers s, n and a it is true that if s | na then s | a.

do i understand you correctly?

[dire obsidian]

yeah

[stray reef]

then what about s = 42069, n = 42069 and a = 1?

[dire obsidian]

did you mean a =42069, s = 1

1|42069 => 1|[(42069)*(42069)] works

[stray reef]

i meant what i said.

[dire obsidian]

what?

42069n = 1???

[stray reef]

no

it is true that 42069 divides 42069*1, but it is not true that 42069 divides 1.

(s, n, a) = (42069, 42069, 1) is a counterexample to the statement that you just asserted right in front of me

put simply, you asserted something that is in fact false.

i would ask you to present the proof you say you wrote 2 days ago, but i'm about to be busy in a zoom call so i won't.

[dire obsidian]

Ok so where exactly in my proof did I assert this? I think the old screenshot I sent was wrong but this one is okay?

ok wait

I se

e

[stray reef]

right here

[dire obsidian]

shoot

what shoudl I have done instead?

[tidal tulip]

Let,
f: X->Y
g: Y->Z
Be bijective functions

We also have bijective inverse functions:
f-1 : Y->X
g-1 : Z->Y

Proof:

h := g o f: X -> Z is a bijective function due to theorem proven in class.
h-1 := (g o f)-1: Z -> X is an inverse due to other theorem in class.

Take any z in Z.
h(h^-1(z)) = z
g(f(h^-1(z)) = z
g^-1(g(f(h^-1(z)) = g^-1(z)
f(h^-1(z) = g^-1(z)
f^-1(f(h^-1(z)) = f^-1(g^-1(z))
h^-1(z) = f^-1(g^-1(z))

Thus, h^-1 = f^-1 o g^-1

can i get a proof check on this? i can think of at least 3 different ways to prove fhis

want to see if this way is valid

[dire obsidian]

wtf

[tidal tulip]

providing (g o f)* = f * o g*

knowing f and g are bij

[dire obsidian]

what should I have done instead of doing

$s|na \land s|nb \implies s|a \land s|b$?

[vital dew]

Salt

[dire obsidian]

also

$s|a \land s|b \implies s|na \land s|nb$ still works right?

[vital dew]

Salt

[dire obsidian]

what should I have done instead of doing

$s|na \land s|nb \implies s|a \land s|b$?

[vital dew]

Salt

[weary tiger]

can someone help me with this proof:

prove, by contradiction, that 9 does not divide nˆ2 - 3

n is any integer

[compact hound]

I have to go to another class soon, but hopefully this is enough to help you out @weary tiger

Note $n^2 \equiv 0,1,4,7 \bmod 9$

[vital dew]

3K

[compact hound]

Note $n^2-3 \equiv -3,-2,1,4 \bmod 9$

[vital dew]

3K

[compact hound]

This is equivalent to saying $n^2 -3 \equiv 6,7,1,4, \bmod 9$

[vital dew]

3K

[weary tiger]

im so lost

[compact hound]

Note that this is not divisible by 9 then as it $n^2-3 \equiv 0 \bmod 9$ isn't an option, so you're done. You could say to begin the proof suppose that 9 divides n^2-3 for purposes of contradiction and ah I see

[vital dew]

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

[compact hound]

Have you learned about modular arithmetic yet or no

[weary tiger]

i know what mod is but i've never seen it written in that form

my prof was using def of odd and even to do these problems

and show that an integer equals a non integer, which is a contradiction

[compact hound]

Ah I see gotcha

[weary tiger]

most of the stuff ive seen online uses different format like what you were saying

so im just kind of lost because i don't understand what it means

i have the even part down

but idk how to approach odd

also I saw someone use the QRT to do cases

but they said that n = 3q, 3q + 1, and 3q + 2

and i dont understand how they got rid of the square on the n

to end up with n = 3k + 3

[compact hound]

Gotcha. I gotta bounce now, but I can try to help later if anyone else doesn't help you before hand

[weary tiger]

okay. i would rly appreciate help later if you're interested

have a good class

[compact hound]

For sure

[compact hound]

@weary tiger

Professor is having trouble setting up the projector Imao, so I’m typing this up rq.

I’m gonna use what that other person said with n=3q, n=3q+1, n=3q+2. These all together can get all integers. You can find proofs of this online if you haven’t already proved it in class.

It’s similar reasoning for each using modular arithmetic.

Case 1: n=3q

Then n^2-3=9q^2-3.

9q^2 is a multiple of 9, so when it is divided by 9 remainder of 0.

Then n^2-3=9q^2-3 divided by 9 will have a remainder of -3 (equivalent to a remainder of 6 for mod 9), so contradiction.

Case 2: n=3q+1

Then n^2-3=9q^2+6q+1-3=9q^2+6q-2.

9q^2 is a multiple of 9, so when it is divided by 9 remainder of 0.

Note that 6q divided by 9 gets you the possible remainders of 0,3,6

So, then 6q-2 divided by 9 gets you the possible remainders of -2,1,4. -2 is equivalent to a remainder of 7 for mod 9.

Then n^2-3=9q^2+6q-2 divided by 9 will have a remainder of 1,4,7, so contradiction.

Case 3: n=3q+2

Then n^2-3=9q^2+12q+4-3=9q^2+9q+3q+1.

9q^2+9q is a multiple of 9, so when it is divided by 9 remainder of 0.

Note that 3q divided by 9 gets you the possible remainders of 0,3,6

So, then 3q+1 divided by 9 gets you the possible remainders of 1,4,7.

Then n^2-3=9q^2+9q+3q+1 divided by 9 will have a remainder of 1,4,7, so contradiction.

Ah wait. I forgot your professor did integer equal to non-integer. I'll try to see if I can find a manner to do so in that way. Although I think this would be easier if your professor allows it. If they want it a specific way then rip. Lemme know if you need help understanding some part

[shadow geyser]

Hello there!

I'm stuck on this problem - can anyone break it down and help me understand it?

Do I assume that when there exists an n >= 100 P(n) then from 10...n P(n) is true? Would that suffice for all A?

I also don't understand how A could be empty or how A could be N

[weary tiger]

how do you get to n = 3q

or, rather, n = 3q + 3

I don't understand how nˆ2 - 3 = 9k, for some integer k (def. of divides) turns into that

[compact hound]

n=3q and n=3q+3 will give the same outputs of possible integers

For n^2-3=9k

You aren't trying to get into that form. You are supposing n is equal to that for a case

And testing what happens if that case is true

And then you wanna show "Hey when n is equal to this. 9 doesn't divide n^2-3. This is a contradiction"

[weary tiger]

how do you know to assume that

i understand every other part of the proof

if it helps

[compact hound]

n=3q, n=3q+1, n=3q+2 can get you all possible integers. It's equivalent to the set of integers

If you prove that none of these work

Then 9 will never divide n^2-3 regardless of what integer n is

[weary tiger]

I thought that you had to test cases as long as r < d

like how do you know what to put for d

in n = dq + r

[compact hound]

There's proofs online for the n=3q, n=3q+1, n=3q+2 being equivalent to the set of integers

So for this we aren't using division algorithm at all for this, but I guess you can think of it that way (or at least I wasn't thinking about it). I was using previous knowledge about n=3q, n=3q+1, n=3q+2 being equivalent to the set of integers

[weary tiger]

so what you're saying is that by the QRT, n = 3q, n = 3q + 1, and n = 3q + 2 regardless of the formula

or the equation

[compact hound]

Nah. I'm saying that n = 3q, n = 3q + 1, and n = 3q + 2 represents the set of all integers

lemme run the odd proof rq. that might make more sense than using the n = 3q, n = 3q + 1, and n = 3q + 2 represents the set of all integers

[weary tiger]

okay

I wasn't aware that was a fact in discrete math

[compact hound]

It's all good. If you haven't proved it then best to not use it

Unless you wanna prove it to use in the proof

[weary tiger]

I've been shaky on the QRT because the definition in my text literally just says n = dq + r and 0 <= r < d

and then a couple pages later it talks about cases

[compact hound]

Hahahahaha gotcha

[weary tiger]

so I feel like r could scale all the way up to d

and like I need to get a problem in the form of n = dq + 4

so now I'm understanding that is not the case of the matter and that r 0 through 2 can be used to represent any integer, correct?

[compact hound]

n=3q, n=3q+1, n=3q+2 can be used to represent all possible integers yes

For division algorithm, it's saying this

So there is a UNIQUE q,r

So only a single one of each

[weary tiger]

I think I understand? the 0 through 2 for remainder is just a standalone fact

[humble coyote]

Yoyo, quick question. What is the length of a language containing only the empty string?

[weary tiger]

im just shocked that information isn't explicitly stated anywhere in my text

[compact hound]

the n=3q, n=3q+1, n=3q+2 is a standalone fact yeah. For the division algorithm, it's saying. Let's take any two integers a,b and where b is notequal to 0. Then there are two unique integers q,r such that a=bq+r with 0 <= r < |b|. So this is saying that there are q amount of b that divide a

and that r is the left over remainder part

[compact hound]

should be 0 as no symbols in an empty string

[compact hound]

Yeah you're fine. I hope I'm not coming off as too passive aggressive. I'm just trying my best to not give you faulty info and correct minor things

[weary tiger]

you aren't coming across as passive aggressive

I'm just lost because everything else makes sense to me

I think i understand that there are q number of b that divide a

i don't understand how that can be applied to anything

im probably just gonna do this problem with the standalone fact because i can do that

@compact hound would you mind if i send my work to you in a few mins when i finish

[compact hound]

Later you'll learn that the division algorithm can be used to get the Euclidean Algorithm and oh I see what you meant earlier. I misunderstood

yes you can use the division algorithm to find cases of various possible remainders when dividing by stuff. I wasn't choosing b=3 in a=bq+r as I was using the standalone fact

And for sure

you are correct though. if something is like a=4q+r and you are dividing by 4. then r=0,1,2,3 is less than 4

Here's the odd version you can think of too if it makes more sense

Suppose n is odd. Then we know that n could have the remainders of 0,1,3,5,7 when divided by 9

Squaring n we get that the possible remainders can be 0,1,9,25,49 when divided by 9

simplifying this we get 0,1,0,7,4 when divided by 9. so possible remaidners of 0,1,4,7

subtracting 3 from this to get the possible remainder of n^2-3, we get -3,-2,1,4

-3 is equivalent to 6 for mod 9 and -2 is equivalent to 7 mod 9

so the possible remainders of n^2-3 when divided by 9 are 1,4,6,7. contradiction and you're done

[compact hound]

We finished discussing it in DMs. Feel free to use chat

[weary tiger]

i dont understand the n^2(cn+d)2^n part

[weary tiger]

Could some one help explain C to me?

[weary tiger]

Sorry I meant to say,
p —> q is T when p is F and q is T

Shouldn’t p —> q be F, in those conditions because the statement reads if p is T, then q is T

but p is F therefore q must be F.
unless the truth value of q is not entirely dependent on p

[coral parcel]

Perhaps one of the explanations at https://math.stackexchange.com/questions/70736/in-classical-logic-why-is-p-rightarrow-q-true-if-p-is-false-and-q-is-tr would convince you?

[weary tiger]

Yea already understood it, thanks though

[sweet ingot]

Is this correct?
R = {(1,1),(2,2),(3,3)}
Symmetric -True
Anti-Symmetric -True
Transitive - True

[sleek loom]

Yes

[sweet ingot]

thnaks

[sweet ingot]

For this question I need to know if its is reflexive, symmetric, anti-symmetric , transitive.

What i need help on is figuring out how to do symetric, how do I get the relation containing the ordered pairs?

I think N in this case = {0, 1, 2, 3, ...}

[viral crown]

N is naturals, right? don't you specifically exclude 0 there?

[sweet ingot]

we do in Australia and this course

Its different in different countries, the teacher covered that.

[sleek loom]

try using a form like a > b, then if we call the > relation R then we know aRb

and then you can play with the algebra to prove the properties of the relation

[sweet ingot]

Thanks ive got them all right so far basing them off the cartesian product of N X N, then applying the x > y. I just wasnt sure how to get the ordered pairs to begin with, is it always just the Cartesian product of the set?

[sleek loom]

a relation on a group A is always a subset of the cartesian product AxA

[sweet ingot]

awesome thank you

[weary tiger]

what set is the relation on?

{1,2,3}?

[royal tartan]

Is there a proof by combinatorial argument for this identity $$ \binom{n}{0} F_m + \binom{n}{1}F_{m+1}+\cdots + \binom{n}{n}F_{m+n}=F_{m+2n}$$

[vital dew]

whitedwarf

[royal tartan]

Where F_m is the mth Fibonacci number

I was trying to look at tilings of a (m+2n)X2 board with 2x1 Dominos

But then the left hand side dosent make much sense to me as to how to count it

[candid fractal]

How do we use inclusion exclusion for part b? I understand part a would be be (23 choose 3) by stars and bars

[royal tartan]

Oh I guess we also have to use the fact that (AUBUCUD)'=A' and B' and C' and D'
Now let A be event x_1 >9
B be event x_2 > 9 and so on
We can find AUBUCUD by inclusion exclusion and then subtract it with the total no of solutions

also I believe A and B and C and D size is 0

And u can calculate A by like setting x_1 =10+X_1 and so on

[candid fractal]

was able to to solve it that way thanks

[royal tartan]

np:)

[sullen vessel]

How would i find how many permutations of order r are in S_n? Is it just n!/(n-r)! ?

[unreal stump]

If r is prime yes

[vocal rain]

I'm working on some code where I am trimming very large video files by grabbing every nth frame. However, I'm getting stuck on how I would calculate the correct frame number from the n frame skip, as well as calculate the number of frames dropped (assuming remainder frames get dropped off the end), and prove it would work for any number of frames.

For example:
Original File Frames- 1 2 3 4 5 6 7 8 9 10
Every 3rd frame- 1 - - 4 - - 7 - - 10

I can see that it's not as simple as just dividing by n (10/3 = 3, but we end up with 4 frames).
I've been trying to prove a formula for 2n and 2n+1 to say "It works for evens, and odds, so it will work for any N frames."
But maybe I should prove "if n is true and n+1 is true, then all N is true."

I'm not looking for a proof because I wanna figure it out myself, but does anyone have any tips on how I should approach this?

[true venture]

So from your example n=2 is 4?

[vocal rain]

Well, it depends on how many frames you'd have. If there were 10 frames, grabbing every 2nd frame, starting with one , the result would be 5 frames: 1,3,5,7,9

With one dropped frame at the end.

[true venture]

Oh gotcha so you want the total number of frames

[vocal rain]

Right. I'm pretty sure (frames + 1)/n gives me the correct number of resulting frames, but I realized I don't know how to prove that.

[true venture]

Ok I think looking at is n is true and n+1 is true is the right direction

[vocal rain]

Alrighty, I appreciate the input 👍

I ought to buy a discrete/proofs book

[true venture]

Lol me too, I enjoy thinking about problems but have never learned proofs

Never really thought how CS related discrete math topics are

[vocal rain]

Discrete and Linear Algebra are required for my CS degree. My school goes hard on math for compsci, all I have to do to get a math minor is add Differential Equations

I wish I had more time to study and really absorb it, I find myself running into issues where I wish I'd done better in those classes.

[true venture]

Similar experience in engr. I took only linear algebra to get the minor. You can always come back to subjects later, having interest is what really matters

[wide vine]

How do I show this is not onto? I feel like it isn't but I don't know how I can show it that it isnt onto.

[austere cedar]

find z in Z, which is not in the imgae of f, ie find z in Z such that x^2-y^2=z has no solution with x,y in Z

[wide vine]

I have a feeling 2 isn't but I don't know how I prove it

[austere cedar]

look at modulo 4

[wide vine]

well lots of numbers I guess but I have not done any proofs regarding onto and how to show it

[wide vine]

we have not looking at modulo yet is the problem

or doing anything with it

so I don't think we have learned how to show such things

[austere cedar]

then without modulo... We want to show that x^2-y^2=2 has no solution. WLOG x, y are natural numbers. So we are looking for 2 square numbers with a difference of 2. Square numbers are pretty rare. How close together can square numbers be? What is the closest square number to n^2?

[wide vine]

x^2 -0^2 ?

that would get you to n^2?

f(x,0) or f(0,y). not sure if that is what you meant

would factoring it into (x+y)(x-y) help us at all?

[austere cedar]

you can do that, it works (and its better than what i thought of)

[wide vine]

hmm I guess now that we know we are working with integers we are looking for cases like. (1)(2), (-1)(-2), (2)(1), (-2)(-1)

[austere cedar]

yes

[wide vine]

well lack thereof I guess

if it isn't true as we might assume :l

well I guess we know it can't be 1

unless y =0

or x = 0

[austere cedar]

these are the possible values for x+y and x-y. You can now for each of the cases compute x and y and you will see that they are never whole numbers, which means that there is no solution

[wide vine]

yeah

thanks

[severe swan]

Can someone explain how to solve this problem?

[stray reef]

base 3

you completely ignored the fact that the problem talked about base three, and not base ten as you wrote

(also the choices for the second and third digits would be 0-9 and not 0-10 even if it were base 10!)

@severe swan

[weary tiger]

[severe swan]

A multiple choice quiz has 2 questions with 3 choices each and 4 questions with 5 choices each. How many ways are there to answer the questions on this quiz?

Why is the answer (3^2) * (5^4) and not (2^3) * (4^5)?

[coral parcel]

Perhaps start by looking at a simpler situation. If there were a question with 2 choices, a question with 3 choices, a question with 4 choices, and a question with 5 choices, what would you get then?

[dense glade]

I don't understand this question

does anyone get it?

isn't f defined if its one to one?

this function isn't one to right?

[hard citrus]

$\text{A relation }R \subseteq A \times B \text{ is a function iff: } \1) (\forall x \in A )(\exists y \in B) \text{ s.t. } (x,y) \in R \ 2)\text{ if }(x,y_1)\in R \land (x, y_2)\in R \text{ then }y_1=y_2$

[vital dew]

.nai

[dense glade]

@hard citrus I

dont gett he 2nd

one

are u saying it has to be one to one?

[hard citrus]

It means that if one element x maps to two different elements then they must be the same

[dense glade]

yeah then 1 to 1

[hard citrus]

No

[dense glade]

but this function isn't one to one right?

because for example

hm?

[hard citrus]

It means

If you have an x in the domain, then there is exactly 1 y related to it

For example

[dense glade]

but in this case

-1 and 1 map to 8

[hard citrus]

(1,2)
(1,3) is not a function

[hard citrus]

-1≠1

[dense glade]

wait why is (1,3) not a function

[hard citrus]

Because 1 unique x maps to two different y

One unique input has two different outputs - > not a function

[dense glade]

Ok I'm really confused 1 sec

so the pair (1,3)

how do u use it in the equation given?

[hard citrus]

Let me ask you something

[dense glade]

Sure

[vital dew]

.nai

[dense glade]

Yes

no

[hard citrus]

But according to you it is not

But the answer is that it is a function

[dense glade]

hmmm

[hard citrus]

You're confusing injective function with function

[vital dew]

.nai

[dense glade]

yes

[hard citrus]

No.

[dense glade]

why not

hmm

[hard citrus]

x=4 maps to both 2 and -2

And you can't have that for a function.

,w graph y^2=x

[vital dew]

Results provided by WolframAlpha

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

Requested by .nai#9187

[hard citrus]

And also, y^2=x doesn't pass the vertical line test

[dense glade]

ahhhh

I see

I knew the vertical line test

but i couldn't tell

well

I thought because -1 and 1 map to 8

so that means is not a function

but I guess

the problem would've been

if was the inverse

if 8 pointed to -1 and 1

I get it I was confusing one to one with functions as u said

[hard citrus]

If 8 mapped* to -1 and 1

[dense glade]

yes

mapped*

not a math major

🤣

[hard citrus]

In your question you are basically given

,w graph y=x^2+7

[vital dew]

Results provided by WolframAlpha

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

Requested by .nai#9187

[dense glade]

it passes vertical line test

[hard citrus]

Yes

[dense glade]

so do we ever

care about

horizotal line test

[hard citrus]

It's just not continuous, it's discrete

[hard citrus]

Yes, for injectivity

[dense glade]

I see

[hard citrus]

,w graph |x|

[vital dew]

Results provided by WolframAlpha

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

Requested by .nai#9187

[hard citrus]

Still a function, but not an injective function

And also not surjective if you define it as R->R

[dense glade]

yeah

thank you!

I appreciate your

patience

[hard citrus]

Np

[wide vine]

I noticed you were discussing y^2 = x vs y=x^2 and how one is a function or not but how would you formal write this out as to show how one is a function and one isn't. I feel like there is a bit of implication that goes on with y^2=x, right?

in the case that we are referring to y^2=x as a function of x vs function of y perhaps?

like f: y-> x : f(y)=y^2 is a function , right?

[wide vine]

I guess this is all to say when someone applies the "vertical line test" we are assuming that we are working with a function that map x -> y vs y -> x

[hard citrus]

The vertical line test is informal. It works to test if a curve is a function when the domain is represented on the horizontal axis. If you take the domain to be the vertical axis, as you did by switching to f: y->x f(y)=... the vertical line test would test for injectivity. That's why there's a formal-ish way to define a function.
Take any two sets A and B and some mapping f. Then you can define f to be a function from A to B by making sure that every element from A maps to exactly one unique element in B. We write: f: A->B f(a)=..., a in A, f(a) in B. As such, there is no confusion for the domain and codomain of f.

[hard citrus]

yes, and also yes about the one above

[wide vine]

okay oaky I see

[dense glade]

How do I solve A?

[unreal stump]

$x=\floor{x}+frac(x)
\implies \floor{7x}= 7 \floor{x}+ \floor{7frac(x)}$

[vital dew]

BYE BYE!

[unreal stump]

If 7 frac(x) <1 the sums will be equal

[dense glade]

what

is frac(x)

[neon sandal]

Presumably "fractional part", defined by

frac(x) = x - floor(x)

[sleek loom]

Has anyone finished a discrete math course and remembers compatibility relations well?

[unreal stump]

Yea latex doesn't like {x}

[stray reef]

\{ x \} works just fine

[tardy remnant]

Can someone help

[rapid lily]

any1 help pls?

[coral parcel]

I'd say all of the options are wrong in the first part. The next-to-last is almost right but fails to match the string 0.

[rapid lily]

turn out next-to-last was correct somehow, thanks anyway

[hard citrus]

FINKI struggles... relatable x)

[tardy remnant]

HAHAHAHA

Bukvv

[hard citrus]

How'd you do?

[tardy remnant]

I guess alright

Wby?

[hard citrus]

I dont have discrete math, I did this first semester discrete structures

[tardy remnant]

R u on seis?

[hard citrus]

KN

[tardy remnant]

Ahaam

[hard citrus]

I was surprised to see another one from FINKI on this server, had to say hello

[tardy remnant]

Mnogu dvosmisleni bea 😦

[tardy remnant]

I was shook too hahahhh

[hard citrus]

Tends to be that way, the second part is easier though, with relations and graphs/trees

[tardy remnant]

Yess I know I have already passed discrete math

I was helping a friend

[hard citrus]

Hahhahah, gonna be together on a mail by disciplinska komisija or were you... ahm... discrete about it

[hard citrus]

You on seis?

[tardy remnant]

Noo we were solving the tasks after the exam hahahahaha 😂

I don’t mess with prepisuvanje xD

[hard citrus]

Which answer did you arrive at?

[tardy remnant]

Idk he doesn’t remember

I was trying to solve it afterwards but I couldn’t specifically remember what consistent meant

[hard citrus]

It's when it is possible for all 6 of those claims to be true

Otherwise it'll lead to a contradiction and the requirements can't ever be met

[tardy remnant]

So all of them should be a tautology?

[hard citrus]

Not necessarily. It just cannot be a contradiction. A contingency is fine as well, I think

[tardy remnant]

Ohh okay ,makes sense

Tnx : )

[dense glade]

for F) why is the answer [9,16]u... sHOULDN'T IT BE [0,16]? since e for example is [0,49]?

[obtuse lance]

what element in (-4,-3] U [5,6] squares to make 0 or 1 since 0 and 1 are in [0,16]

[dense glade]

ok so why is [-7,2]?

none of them give 0 right?

[obtuse lance]

well what squares to make 0?

and then check if that's in [-7,2]

[dense glade]

oh

are we

including all numbers

between -7 and 2?

I see

I thought it was only 7 and 2

[sleek loom]

Search up closed and open intervals

[brisk fog]

which among these can be considered computable?

a. fetch me a bottle of water.
b. can a computer fetch a bottle of water?

My guess is that (a) is not computable because we're really not computing anything. (b) on the other hand can be if we can precisely describe the machine that is to carry out the task.

[coral parcel]

Neither looks like an utterance that the concept of "computable" even makes sense about.

[brisk fog]

what makes (b) nonsensical in the context of computability?

[brisk fog]

I was typing a longer response to sketch out my line of reasoning for (b)'s computability but midway I realized I am not yet ready to ask this question. Nonetheless, @coral parcel, I appreciate you taking the time to leave a response. Thanks!

[coral parcel]

I meant, I'm not aware of a definition of "computable" that even assigns a truth value to the claim "(b) is computable".

Computability as far as I know it is always about computing some symbolic output from some symbolic input. Actions in the physical world are simply not what the concept I know is about.

[brisk fog]

My definition of computable here is that an algorithm exists that can output yes or no for (b). But yes, this question isn't coming from a textbook. There's a good chance both of them are nonsensical to present as problems whose computability can be argued.

[coral parcel]

A single question is always computable, as long as it has a definite yes/no answer -- it is either computed by the algorithm that immediately answers "yes" or by the algorithm that immediately answers "no" (and just because we don't know which of the algorithms works doesn't change the fact that one of them does).
The concept only becomes interesting for a family of questions speficied by some input to the algorithm.

[flint harness]

Does anyone have a great resource to help me become better at proofs by induction in discrete math? I need to understand it in order to be able to do recursion and tail recursion functions in functional programming.

[severe swan]

How many bit string palindromes of length six or seven start with 1?

Answer is 12

Can someone explain how to get 12? When I tried solving it I got 2^4 for length 6 and 2^5 for length 7.

[wide vine]

You don't really have 2^4 and 2^5 options

if you want it to be a palindrome

what you have here

you are basically saying 1 0 0 0 1 1 would be valid

[tidal tulip]

to prove there are infinites larger than R can i say the power set of R is such a number and to prove that would i prove the power set of anything is strictly larger then the power set of the thing?

and do i need to break that proof up into cases for finite and infinite sets

[wide vine]

but in reality you don't have the freedom of picking 4 values and really only have the freedom of picking 2 values as the other 2 must match on the other side

so for 6 bit string that ends with in 1's 1 x x x x 1 is more like 1 a b b a 1 as you have to keep the pairing but you have calculated something more like 1 a b c d 1

where a, b would be the bit values you manipulate 0/1

with the 7 bit case we have something like 1 a b c b a 1 and so we have freedom on a,b,c being 0/1

[tidal tulip]

if i want to prove power set of N is strictly larger than N do i need to break it into cases of where N is finite and N is countable infinite and N is uncountable infinite

[wide vine]

so for 6 bits strings palindromes you have 2^2 = 4 and 7 bit palindromes you have 2^3 = 8 and this is where your 12 comes in as 4+8 = 12

[viral crown]

i think it's just enough to show that the cardinality is always 2^n, where n is the cardinality of the previous set

not sure though, i could be wrong

[tidal tulip]

ok

you would do that by showing there isn’t a surjection between the power set and set yeah?

[viral crown]

i think you want bijection here

[tidal tulip]

well if there was a bijection the two would be equal which they aren’t

since power set is strictly larger than the set

[viral crown]

lmfao i'm stupid i forgot what a surjection was for a sec

[viral crown]

wait no im just fucking idiotic

[cerulean wind]

power set of N is uncountable

[viral crown]

i meant "you want to show no bijection here'

which is the same as showing no surjection or injection

[viral crown]

he wants to prove it

[cerulean wind]

no, no cases

there is a general proof

that there is no surjection from X to P(X) for any set X

if there is a set X with a surjection f : X --> P(X), look at {x in X : x not in f(x)}

[tidal tulip]

k

ty

[severe swan]

Thanks @wide vine

[severe swan]

Can someone explain how to solve this?

How many positive hexadecimal integers with exactly six base 16 digits are there that start with a letter and contain no 0's?

A 516^6
B 515^6
C 616^6
D 616^5
E 616^5
F 615^5 Correct Answer

[obtuse lance]

well generically speaking there are 16 ways to pick a digit

but if the first digit has to be a letter, how many letters are there as digits? only a,b,c,d,e,f which is 6

so there are 6 ways, then the rest of the digits you want them to just not have 0, so instead of 16 ways there are 15 ways to pick those

it might help to work out a smaller example by hand like make it only 2 digits and you can draw a kind of table for it

rows being all letters, column being all digits except 0, then look at each place you make the combination makes a 6 by 15 box which is counting all the possibilities for 2 digits

[wide vine]

It is possible to have a relation between two sets A and B in which A = B. A binary relation on a set A is a subset of A x A. The set A is called the domain of the binary relation. when they say this, it is still possible you could could have a relation where it equals to the set A x A?

or no?

like If all of set A mapped to every one of the set B then you would have A x A, right?