discrete-math

[kindred sand]

That's kind of crude. Technically you would say it can be reduced in polynomial time to another problem

[nimble pond]

so here what I have to prove is VCover is poly time reducible to MinCover right

[kindred sand]

Yeah exactly

[nimble pond]

And to do it I have to prove both ways

[kindred sand]

yes

[nimble pond]

Which is Use VCover to get MinCover and use MinCover to get VCover

[kindred sand]

🎆

[nimble pond]

VCover is a decision problem

So I can just use MinCover, compare the value it returns with the k

and get my result

But MinCover is optimization

Minimization here exactly

How can I use it to get MinCover

wait

so call

[kindred sand]

It can still be reduced in polynomial time by iterating over values of k

[nimble pond]

VCover

got iy

from 0 to k

call VCover

the first value would be MinCover

[kindred sand]

As an example let algo A be O(n^2) and algo B be O(n^100). Both are still in P despite on being obviously way harder than the other

[nimble pond]

Yes

[kindred sand]

similarly mincover might be harder than vcover but both are in the same complexity class

[nimble pond]

yes

one question tho

if you dpnt mind

dont*

[kindred sand]

sure

[nimble pond]

MinCover is an optimization problem and VCover is a decision problem

can we use the same metrics to classify them

[kindred sand]

Yeah. The definition of P is that the problem is solvable in polynomial time

[nimble pond]

Got it

So here to start my proof I have to assume that MinCover and VCover are working algorithms?

[kindred sand]

Yeah its an assumption that they are in P.

[nimble pond]

I have another question with this

My question states that MinCover gets a graph as input and outputs the mincover

and VCover gets a graph and k as input

but there is no output and instead a question

so I was wondering if I can assume that it will give me an asnwer

[kindred sand]

Yeah ig. They can both be formulated as questions or outputs. The vcover output is yes / no. The mincover question is what is the size of the minimum vertex cover.

[nimble pond]

Okay thanks a lot

that clears it for me

I was just not sure since it said question and not output

[kindred sand]

yeah could've been formulated better

[nimble pond]

I will also email my professor about it just to be sure I guess

Thank you so much for your help @kindred sand and @agile magnet

[steady moon]

Meaning of this line?

[little prism]

probably "divides" if I had to guess. more context would help

[grim tapir]

https://ioactive.com/wp-content/uploads/2015/07/ldc_tutorial.pdf

Specifically, we consider the input and output
differences of the S-boxes in order to determine a high probability difference pair.
Combining S-box difference pairs from round to round so that the nonzero output
difference bits from one round correspond to the non-zero input difference bits of the
next round, enables us to find a high probability differential consisting of the plaintext
difference and the difference of the input to the last round. The subkey bits of the cipher
end up disappearing from the difference expression because they are involved in both
data sets and, hence, considering their influence on the difference involves exclusive-
ORing subkey bits with themselves, the result of which is zero

confused by this part at the end of 4.1

[indigo rapids]

can someone explain to me how the cycle:

(1234) = (14)(13)(12) = (21)(24)(23) = (35)(14)(53)(13)(12)

[little prism]

wdym how

[regal ice]

Does anybody know a good video resource (like youtube, coursera, udemy etc) that covers the topics above?

[indigo rapids]

nvm ignore that question i think i understand it. But any chance you'd be able to explain to me how to go from pi^2 to pi^3.

cuz from pi -> pi^2, i multiplied pi.pi. and then followed the cycles from right to left

[little prism]

well multiply pi.pi^2 and then follow cycles

there is no ^1.5 or something if that's what you are hoping for

[indigo rapids]

omg i see hahaha

i was just reading the cycles wrong hahahaha

thanks XD

would there be a quicker way to compute large cycles like these?

for example

if i was given the disjoint cycles for pi, and told to compute pi^7, would there be a quick way of doing it?

[little prism]

well really it's just about going 7 steps inside of each of those cycles

[indigo rapids]

or would i have to write out how many times until the id reforms

[indigo rapids]

what do you mean by that?

[little prism]

like doing 7 steps in (2359) for 2 is 3,5,9,2,3,5,9 and so 2->9

so it starts (29

then you'd do 7 steps from 9

and get 5

so (295. and then it obviously has to end on 3. so (2953)

of course here you could skip a few steps cause 7 is longer than the cycle

[indigo rapids]

omg you legend

actually saving my life sm rn

fkin awesome

thank you so much

damn

thats so simple hahaha

legend

Assume multiplication of permutations f,g obeys the rule (fg)(x) = f(g(x)) so (1,3)(1,2)=(1,2,3) not (1,3,2)

can someone explain to me how youd get (1, 3, 2) from (1, 3)(1, 2)?

ahh ones left to right a

[little prism]

by reading from the wrong side?

[indigo rapids]

and the other is rigth to left

yeah

haha

thank you

[river comet]

can someone help me
?
i have the following equation: f(x)=-0,07x²+7 ; what is the vertex shape,general shape and factored form

[regal ice]

ATTENTION PLEASE

[hazy galleon]

Write trevtutor

[hazy galleon]

How many license plates can be made using either 2 uppercase letters followed by 3 digits or 3 uppercase letters followed by 2 digits?
Do you know how to do this one? by any chance I did (26^3 x 10^2)+(26^2 x10^3) = 2,433,600 but Im not sure if its right

[coral parcel]

That sounds reasonable, if you accept that, for example, ABO23 and AB023 count as different plates.

[fathom lark]

Im like 95% sure this is true

Would appreciate some confirmation

[coral parcel]

Yes, whatever {CSCE235} is, you can see it plain as day as the second of the two listed elements of the set.

[fathom lark]

Thanks Im just triple checking

[regal ice]

Unfortunately it is not complete it has only three videos on it:(

[hazy galleon]

Try kimberely brehm

[leaden hinge]

This is computer science, but where did you find that page?

[weary tiger]

Could anyone possibly give me an understanding of how to get different base decimal representations for a decimal?

[wheat mauve]

how do you identify polynomials

my exam tommorow

[stray reef]

wdym "identify"

do you mean tell which expressions are polynomials and which aren't?

[wheat mauve]

i mean how do you tell if its a monomial,binomial,or trinomial

[steady moon]

To be able to tell if the relation is transitive or not, I need to find at least 1 example or every combination?

[real flame]

p => q is equivalent to (~p)vq. The implication p=>q is true provided either p is false or q is true.

^^ why is this true?

[stray reef]

@wheat mauve those words refer to the number of terms

one, two or three respectively

[wheat mauve]

4y-5xz

[steady moon]

?

[wheat mauve]

you said you need a example

[steady moon]

I didnt

[wheat mauve]

my bad

[stray reef]

@wheat mauve did i answer your question as to what the words "monomial", "binomial" and "trinomial" meant?

[wheat mauve]

yea thank you

[steady moon]

@stray reef do you know the answer to this?

[stray reef]

feels too slippery to answer

[steady moon]

Because lets say I find one example that the relation is transitive and there is only this example, then would I say that the relation is transitive or not?

[stray reef]

depends on what you mean by "example" and also whether the set your relation is on has 3 points or more

like

one trio (a,b,c) such that (a,b), (b,c) and (a,c) are all in R

is not enough

[steady moon]

Would you say that this relation is transitive? A = {1, 2, 3, 4}

[stray reef]

yes

you would need to check every pair of pairs of the form (a,b) and (b,c) though

[steady moon]

okay thanks

[urban mantle]

I need to find such a subset of edges of graph, that there is paths without common nodes (except E) between nodes (A,B,C,D) to node E. See second image as example.

In the end I need to have a tree, where only node E have degree >2.

So I have a starting end nodes(A,B,C,D) and common node (E), which is gonna connect everything else

I am trying to find if something like this was already solved.

It would be cool if I could do this using networkx

[urban mantle]

Yeah, maxflow will do the work. I thought that max flow used in networkx using real-value measure for flow, but it is not the case.

It is discrete, so I can apply max flow to this one

[crimson thistle]

can someone show me a youtube channel that can teach me how to get certain ideas so i can solve discrete math problems?

I feel like I don't have the necessary tools for solving them

and the answer is always something that i would never think about

[weary tiger]

I asked my students to compute the number of necklaces one can make with 3 colors having 6,4,2 marbles in each class.
The book answer considers the necklace as a line and computes 12!/(6!4!2!) necklaces. So far, so easy.
But the smart ones started asking questions about accounting for the cyclic symmetries on the possible necklaces... How would one go about that? I was thinking in the direction of Burnside's lemma, but how was that applied again?

Or is this essentially a programming exercise?

5,4,3 would be easy enough, since 5 and 12 are co-prime and there are no cyclic symmetries and I only have to consider reflections, yielding [12!/(5!4!3!)] / [5!/2!²]. but the cyclic symmetries you get for 6,4,2 make this kinda hard.

[weary tiger]

You can add an artificial source S connecting to all sources A-D with capacity 1.
Set all other edge-capacities to 1.
A max flow on this network then gives you a set of edge disjoint paths from S to E.

[vague island]

anyone know how to solve these 3?

[ivory badge]

For (d), what is required for R to be reflexive?

similarly for (e), what is the requirement to be symmetric

[ivory badge]

What do you think the answer is/answers are?

[vague island]

Well for d I think the minimum number of ordered pairs are 4 having a,a b,b c,c and d,d

[ivory badge]

Reflexive is that x R x for all x terms on the set yeah

So you know it needs those pairs

[vague island]

For e if this is an empty relation (because there's no relation given) then the minimum number of ordered pairs could be 0 knowing that empty relation means it is symmetric and transitive

yea I know d but for e and f im not sure

[ivory badge]

Well, is the definition for symmetric that x R y -> y R x?

[vague island]

e could also be 4, for example having (a,b), (b,a) and (c,d) , (d,c)

yea

[ivory badge]

Well that is symmetric, but that’s definitely not minimal

Since (a, b) and (b, a) as elements is also symmetric

Empty relation would indeed kinda vacuously satisfy the requirements that x R y -> y R x

[vague island]

hmmm thats what im wondering, am i supposed to include all the elements?

or i dont have to

[ivory badge]

Time to list all the elements:

Done

But symmetric doesn’t have to include every element I believe

[vague island]

i see

oh then for transitive i can just include abc

for transitive are a,b b,a c,a a,c b,c c,b the minimal?

[ivory badge]

Well, transitive is (x R y and y R z) -> x R z yes?

[vague island]

yes

[ivory badge]

Well, that would be transitive, but so would the reflexive relation yes?

So clearly not minimal in element count

[vague island]

im not sure if its reflexive

but i guess its symmetric

(a,b) (b,c) (c,a) is enough i think

[ivory badge]

Im saying {(a,a), (b,b), (c,c), (d,d)} is reflexive, symmetric, and transitive

[ivory badge]

This is not transitive

[vague island]

btw i forgot to mention one thing

this is a directed graph

[ivory badge]

Well, is {(a, a)} transitive, is the empty set transitive?

[ivory badge]

Doesn’t matter

[vague island]

a,a is reflexive no?

[vague island]

its reflexive only

[ivory badge]

No?

For any pair such that x R y, we also have y R x yes?

Therefore symmetric

Similarly for the transitive condition

[ivory badge]

If the only pair is (a, a), then it is also symmetric and transitive too. Not reflexive though

Is the empty relation symmetric, and is the empty relation symmetric?

[vague island]

well by definition yes

[ivory badge]

Then that’s minimal immediately

Because you can’t get smaller than that

[vague island]

ahh so this is correct

ok thank you!

[glacial radish]

Let us consider the function g : R2 →R given by g(x, y) = |x|+ |y|.
(i) Describe the equivalence relation ∼ on R2 which is induced by the function g.
(ii) Describe (with proper arguments) the following equivalence classes of ∼ :
(a) [(0, 0)]
(b) [(1, 0)]
(c) [(1, 2)]
(d) [(0.5, 1.2)]
(iii) Find two different transversals for ∼.

Can someone help me with this

[ivory badge]

For (i), how would you make an equivalence relation out of g

[glacial radish]

How to make an equivalence relation out of g

????

[ivory badge]

Yes, that’s what I’m asking, that’s the first step in this

How would you make an equivalence relation out of a function

How would you suggest someone do so

[ivory badge]

Hint: consider when g(a) = g(b)

[drowsy verge]

Equivalence relation refers to relation that is reflexive, symmetry and transitive.
Prove it one by one.

[vital locust]

i'm having trouble with these kinds of questions asking to find a recurrence relation

after listing J1,J2 and J3

i still dont see the pattern

[little prism]

well the pattern only starts there

try J4 and J5

[vital locust]

hmmmmmm i think i see the pattern now

Ou where u is in J(n-1)

or 10 where u is in J(n-2)

or 110u where u is in J(n-3)

[dawn gulch]

This is my worst nightmare ever

Taking this class

And I have a midterm warning

Just out of curiosity is this class difficult

I have an intellectual disability and I have a hard time processing information from my professor and I feel like I need to be proactive and just idk

I’m having a mental breakdown

Is this hard is what I’m trying to figure out

Why is this so complicated for me

I think I know why

It’s not simple

You’re using letters and not numbers

[ivory badge]

You’re the one taking the class, so I feel like you’re the most qualified to answer that

[dawn gulch]

I feel like an actual idiot honestly

It’s hard for me to understand

It’s a requirement to take the class

@ivory badge well I feel like I’m at a disadvantage

I just want some insight

[ivory badge]

You are at a disadvantage

[dawn gulch]

How so

[ivory badge]

Well you did blatantly say “intellectual disability”

[dawn gulch]

Yea it’s nothing new

[ivory badge]

That sounds like a disadvantage to me

[dawn gulch]

How are you able to grasp at something that easy

[ivory badge]

What parts give you trouble

And for what end do you take the class

[dawn gulch]

Wdym by the second question

The first question I can definitely answer

[ivory badge]

Why are you taking it

[dawn gulch]

It’s a requirement

For my degree

[ivory badge]

For CS, for math, etc

[dawn gulch]

CS

bachelors

[ivory badge]

Aight

Name a problem

[dawn gulch]

The thing that troubles me is breaking down material to understand and process

I feel like I am outcasted

Because

[ivory badge]

That’s a very vague issue

[dawn gulch]

Okay

You want me to narrow it down?

[ivory badge]

Yes

[dawn gulch]

Essentially if my professor is giving a lecture of some kind

I feel like I’m the outcast of the room

Apparently people in my class gets it

I’m the denominator

To be ironic

[ivory badge]

I don’t think the use of denominator there is correct but

[dawn gulch]

I’m just saying

I feel like I’m the only person who can’t grasp the material

[ivory badge]

That sounds like you’ve convinced yourself you’re “different” in a pejorative sense

[ivory badge]

What material do you not get

[dawn gulch]

Well set theory I kinda get

But once you got into the complex things

Like the big E and the other variables

[ivory badge]

What is E

[dawn gulch]

The fancy one

On the calculator

[ivory badge]

You mean

$\sum$

[vital dew]

The great Sharp

[dawn gulch]

That

[ivory badge]

Sigma

[dawn gulch]

That’s the last things we learned

It’s like basic variables like that I don’t get

But then you have variables of letters you use for numbers

It’s substitution for them

[ivory badge]

I am curious as to why that’s showing up in discrete math, and why you wouldn’t see it in calculus

[dawn gulch]

Applies discrete maths

*applied

But sure

[ivory badge]

The sigma I usually see as a summation

[dawn gulch]

@ivory badge want me to put it in simple terms

[ivory badge]

That would be desirable

[dawn gulch]

I can’t break down certain aspects of things that we learned

And memorize them

Sometimes I feel like it’s basic algebra

And then it’s like what am indoing

*I

[ivory badge]

What’s an example of a problem you couldn’t figure out

[dawn gulch]

Uhhhhhh

Well keep in mind

[ivory badge]

Or a specific topic from a lecture you didn’t get

[dawn gulch]

Okay hold on

Okay remember truth tables

I can’t understand it

Sometimes I do

I sometimes forget that certain equations I can plug in

You know variables with numbers and that sort of thing

Or recursions

@ivory badge

[ivory badge]

Well truth tables are just substituting in variables with either true or false?

Or rather, substituting in all of the possible ones

[dawn gulch]

Again sometimes my brain doesn’t register to substitute

[ivory badge]

It’s just like graphing 3x+1 as a line

[dawn gulch]

I know what basic algebra is

I learned about linear, quadratic and exponential graphs

I learned basic geometry

[ivory badge]

You throw in all the possible values and collect it as the graph

Similarly with a truth table, the truth table for, say, $x\lor y$ is just substituting in either true or false for each of $x$ and $y$

[vital dew]

The great Sharp

[dawn gulch]

The arrows are complicated too

Sometimes I just have to memorize

Isn’t the down or

[ivory badge]

Yes

[dawn gulch]

God help me

I feel stupid

So we essentially plug numbers in?

In simple terms

Right?

[ivory badge]

Yep

But instead of plugging in real numbers, it’s plugging in {True, false}

[dawn gulch]

You mean from the table?

[ivory badge]

That’s how you make the table

[dawn gulch]

Now I’m class we are learning about the circle thing

What’s the thing where you use the pyramid circle thing

I forgot what it’s called

*in

[ivory badge]

I have no idea what you mean by pyramid circle

[dawn gulch]

Ahhhhhh

Hold on

You know the 3d or 2d models of that thing

[small temple]

Sorry for interrupting you both, but i really need help on this, any clue??

[dawn gulch]

Second order recursion @ivory badge

[ivory badge]

!help

[lofty cloud]

Please read #❓how-to-get-help

[dawn gulch]

Second order recursion is what we are learning in class

Oh man it’s complicsted

[ivory badge]

I’m not quite sure how you get a pyramid from that, could you demonstrate?

[dawn gulch]

He was showing us a 3d model of some mind#

*kind

It’s like those circle stacks

And by circles I mean rings

You know what I’m talking about

https://i.etsystatic.com/15536406/r/il/1ff0d1/2296322934/il_fullxfull.2296322934_28o3.jpg

These @ivory badge

He was showing us about the stupid peg game

[ivory badge]

Tower of Hanoi

[dawn gulch]

I wasn’t following on why

But it looked cool

[ivory badge]

Why weren’t you following on why

[dawn gulch]

Because it looked complicated when he was talking

So I wasn’t sure where he was going

[ivory badge]

So you just stopped paying attention?

[dawn gulch]

So in my mind I was a bit confused

Well my brain

Goes off

It’s not that I don’t pay attention

Sometimes I am trying to get it

And I don’t ask for clarification

[ivory badge]

Ask for clarification

And go to office hours

[dawn gulch]

Is it wrong not to

Or am I just being superstitious

Because I feel like im the elephant in the room

[ivory badge]

It’s wrong not to ask yes

[dawn gulch]

It sounds simple

But

I feel like I’m the only person that doesn’t understand things

[vale cairn]

Wrong is perhaps the wrong word lol

[dawn gulch]

And that makes me

Well

Left out

[ivory badge]

Well then ask a question so as to not be left out

A direct solution works sometimes

[dawn gulch]

Even if it sounds stupid?

[ivory badge]

If you get your answer you’re less likely to have an issue

[dawn gulch]

Is it bad to be the only person that doesn’t get it

Like majority of the people in my class understands it but me

[ivory badge]

That’s speculation

I can tell you right now a good few people in every class don’t get it

Or almost every, at least

[dawn gulch]

What does that mean in layman terms

[ivory badge]

Other people don’t get it too

Swallow your pride and ask a question sometimes

[dawn gulch]

Hm

[lofty patrol]

Hi! Does anyone have resources that they found really helpful for better clarifying concepts in dicrete math? And just for extra practice (like youtube channels, websites, just direct links/pdfs lol, studying, etc.)

[halcyon slate]

is the answer n^2?

[unreal stump]

2^n

There are 2 possible values for f(1)

Same for f(2),f(3)...f(n)

[spiral plinth]

What is 5+4-3/7

[halcyon slate]

got it

[lunar sentinel]

Hi Could anyone help me to show that :
Show that an interval graph is the complementary graph of a comparability graph ?

[hoary halo]

Can someone explain how

[weary tiger]

Let n be an integer. Then n is not divisible by 3 if and only if n
2 −1 is divisible by 3.

[golden robin]

$$\frac{(y+2)^2}{36} - \frac{(x-2)^2}{28} = 1$$

[vital dew]

Synx

[weary tiger]

I dont get the proof of the n! orderings

the notation is bad

[river garden]

a^ib^j | i!=j and i!=2j

how can I prove that this language is CFL

[unreal stump]

Try constructing a PDA

[river garden]

I can construt for i!=j

Similarly for 2j

But pda are not closed under intersection

[haughty garden]

Try constructing a grammar that recognises the language. Consider the languages L_1 = {a^i b^j | i > 2j}, L_2 = {a^i b^j | i < j}, and L_3 = {a^i b^j | j < i < 2j}. Convince yourself that L = L_1 U L_2 U L_3. Grammars are closed under union; therefore, it is enough to find CFGs for each of these languages

[weary tiger]

is there a better/faster way of doing this problem?

[whole dust]

eulers theorem

[river garden]

Ty

[next sail]

is the LHS logically equivalent to the RHS? where P and Q are predicate symbols, x is the predicate variable and D is the common domain.

also does the RHS count as a statement?

[stray reef]

yes they are logically equivalent

and i don't see why the rhs wouldn't count as a statement. it's a statement of set inclusion, after all.

[next sail]

oh i see

thanks

[meager mural]

hey can someone explain this to me? isn't both just proof by contradiction? it's just different forms of it right? for example, proof by contradiction on a statement P and proof by contradiction of a conditional statement

[vale cairn]

Essentially the first is when you want to prove that P holds and you prove that assuming "not P" leads to a contradiction, which shows that not not P holds

In classical logic, that is the same as P

Whereas in the second, we want to prove that not P holds, so we show that P holding would lead to a contradiction

The difference is perhaps more clear if you consider actual examples

Say we want to show that x^2 + 1 =0 has no real solutions. Well we can suppose there is a solution and then we have 0 = x^2 +1 >= 1 > 0, absurd

[meager mural]

This example is for the 1st one right?

[vale cairn]

Sorry yeah that's proof by negation

I was trying to think of a good example of a proof by contradiction lol

[ivory badge]

Negation just uses something like: We want -P. We show P leads to contradiction, therefore -P

Contradiction is like this:
We want P. We show -P leads to contradiction, therefore -(-P), therefore P

The -(-P) -> P is the trick that makes it contradiction, and constructivist don’t really like it. A good few are fine, however, with -(-(-P)) -> -P

Basically it’s contradiction if you negate it twice

[coral parcel]

¬¬¬P -> ¬P is intuitionistically valid. Are there constructivists that reject it?

[ivory badge]

I am not aware of any which reject it, but I wouldn’t be surprised

[cyan plover]

Hey guys, I'm trying to convert decimal numbers into two's complement binary numbers and adding them. I'm a little confused if I'm doing this right as I'm getting the decimal equivalent of 16 instead of 0 for 21-21.

[coral parcel]

The addition at the bottom is wrong. You should get 0 with a carry out in the leftmost bit.

(Looks like you forgot to carry the one from the 8s place).

[cyan plover]

thank you... but 8s place? There's only 5 places right?

Oh wait do u mean the last 1

[coral parcel]

Counting from the right, we have the ones column, the twos column, the fours column, the eights column, and the sixteens column.

[cyan plover]

thank you! I didn't know they were referred to that way. I'm getting 100000 now

[coral parcel]

But you're only working with a 5-bit word, so the carry out of the sixteens column is just thrown away.

[cyan plover]

is that because of 'overflow'?

[coral parcel]

Well, yes and no. It would be overflow if you were adding unsigned 5-bit numbers, but if you're using 2's complement, detecting overflow is a bit more complex than that.

Wait, though, actually ...

[cyan plover]

Oh okay. I was wondering because idk how to choose the appropriate bit number to avoid overflow.

[coral parcel]

You can't represent 21 as a 5-bit 2's complement number -- that can only represent -16 up to 15. You need more bits if you want to speak about 21.

[cyan plover]

I just thought that because both the numbers were 5 bits, i didn't have to do anything?

[cyan plover]

no I did it for -21

[coral parcel]

-21 is not in the representable range of a 5-bit signed number either.

[cyan plover]

Do i add more 1s behind the binary equivalent -21 then?

I'm just a bit stuck when it comes to calculations involving two's complement

[coral parcel]

Generally you don't let your word sizes vary with which numbers you're calculating with. (At least at the most basic level). You start by selecting your word size -- say, 8 bits would be good for a pen-and-paper example here, that lets you represent integers from -128 to 127 -- and then represent your input numbers with that many bits.

[cyan plover]

ok. So does that mean, I represent 21 and -21 as 8-bit numbers?

[coral parcel]

That's what I'm recommending, yes.

(6 bits would be enough for this particular task, but 8 bits is a much more usual width, so it makes the example feel a bit more realistic).

(Also, having more bits than strictly needed helps make it clearer how the system works).

[cyan plover]

I'm now getting 1 0000 0000 as the answer to the addition

[coral parcel]

That's more than the 8 bits you have room for!

[cyan plover]

🥹

[coral parcel]

Your adder only has an 8-bit output. The carry out of it disappears.

[cyan plover]

so disregard the 1?

[cyan plover]

May i dm you about this question, please?

[coral parcel]

No.

[cyan plover]

just to clarify, do i disregard the 1 or not?

[coral parcel]

Well, yes, but it's better to think of it as "only the 8 rightmost bits even exist".

[cyan plover]

ok thank you

[sacred fern]

Hello

I was wondering how I might be able to find the “closed form” of the generating function for the sequence given by a_n = 2n

[coral parcel]

Start with the generating function for (1,1,1,...). Differentiate it to get (1,2,3,..), then multiply by x to make (0,1,2,...). Then hopefully you can see the final step to (0,2,4,6,..) yourself.

[sacred fern]

That’s actually genius, thanks 😊

[ivory badge]

Just think for 5 seconds and follow what you do or don’t have access to

Also @noble parrot #❓how-to-get-help

[spiral aspen]

The men-proposing variant of Algorithm 1 is man-optimal :
every man is matched to the best partner possible in any stable matching
can this be proved by showing the example below cant happen?
e.g: w prefers m', w' prefers m but m prefers w and m' prefers w'
in the end w gets matched with m' and w' gets matched with m

and that e.g cant happen because m will propose to his first preference first and so will m'

[prime dagger]

I have a question. In how many ways can 8 people be seated on a round table if 4 people must sit next to each other?

The answer I am getting is 4! x 4! because we can group all the 4 people that must sit next to each other into one and then seat only 5 giving us 4! ways, then we can permute the 4 people within that group giving us 4! ways hence in total we are left with 4! x 4! ways

Is this how I should approach this problem

[coral parcel]

That sounds reasonable.

[prime dagger]

in this do we divide 5! by 5(like I did) or by 8?

[coral parcel]

How I would think of it is the 4 selected people sit on one side of the able and the other 4 on the other. We can choose where to place the dividing line between the two sides, but "round table" is usually code for "we don't count that difference", so there's no reason to count it just to divide it out afterwards. Just number the 8 chairs starting with "the rightmost of the 4 selected people, no matter where that is".

[prime dagger]

I see, so the approach I took should work?

[coral parcel]

I agree about the 4!4!.

[dense copper]

if I have a semi-eulerian graph, do I have to start at an odd vertex to traverse it?

i seem to be getting that a lot

but is there a proof for this? is it even true? or am I assuming things?

[wet quartz]

Hey, so i had this in help forum but i think it fits here a bit better.

I recently have been screwing around on desmos after having my interest piqued by a youtube video of all things, and have found an odd pattern to something.

Ive mocked up a mini setup describing in mathematical terms what ive seen

Im just wondering how the hell this has happened, and also what solutions or questions could i ask from this

because, what appears is regions between two square numbers contain twice a triangular number, based on the combination of both tau functions

actually, now thinking about if there are any similar representations which combine both sets of square numbers and triangular numbers to form this sort of representation.

[obtuse lance]

I don't really follow what you're asking for

[wet quartz]

i dont even know what im really asking

im feeling very confused on which topic to put this under and also how to structure my specific problem with it

because im not particularly sure if ive done something wrong or just stumbled across something quirky

[obtuse lance]

Idon't know what I'm looking at here, are you saying there's a triangular number between every pair of consecutive squares or somethin

[wet quartz]

yeah, i believe thats what the graph shows

well, what the graph shows is that for every square number, the value at which the root approximation functions have an equal inaccuracy is double a triangular number

math has my brain tired.

[obtuse lance]

can you back up and explain what you mean by root approximatino functions

[wet quartz]

so ill explain how i got to the graph, I saw on youtube a technique to "approximate" square roots of x, By finding the nearest integer square number and then some additional math which is in total defined by the function mu.

These approximation functions obviously dont work fully, so i created the tau function to represent how far off they are from the actual square root of x

But when given an x value that is twice the value of a triangular number, both mu functions are effectively off by the exact same amount and give the weird effects of this graph.

this also appears to give the user the ability to prove if a number is a triangular number or not based on what ive seen

i will be honest, im new to the entire area of asking about things in maths and my mental thing is where im not good at explaining at all about any problem i have

[obtuse lance]

well I guess this on its own isn't too bad to prove, since twice a triangular number will be of the form n^2+n it will be between n^2 and (n+1)^2

not sure if this is part of what you're interested in or not, or you already knew that

[wet quartz]

ive sorta just been dipping into various possible things to do with this, but not investigating any singular one because well. I dont know if i fully comprehend the mechanics behind why what ive come up with shows this pattern

which is why idk where to really put this. When i put it into a general area like the problems thing i got someone completely derailing because it was way out of their league.

[obtuse lance]

to me it seems like you're just having fun playing around, which is fine but I don't see anything in particular to really latch on to

[wet quartz]

yeah im not sure if there really is anything to latch on to, other than maybe making a proof for any given number being triangular by using the math ive provided

[obtuse lance]

you didn't really answer me on this

[wet quartz]

sorry, it didnt click in my brain

[obtuse lance]

do you know how to prove twice a triangular number is between two perfect squares

[wet quartz]

no it didnt even occur to me

i now regret asking

[obtuse lance]

why lol

[wet quartz]

i have massive misinterpretation issues, Not hiding behind them or anything but im on the brink of crying rn because my brain just feels blockaded by it.

[wet quartz]

which is the reason for this

im literally at war with someone in my class rn because it makes me feel shit because i always feel behind them

but anyway, Yeah im not gonna say i feel completely out of my depth with this, but i will admit i didnt know there was a proof that the twice a triangular numbers lies between two perfect squares

[obtuse lance]

try to prove it I'll help you if you run into problems

I should have been more precise too: between two consecutive perfect squares

[wet quartz]

yeah, i used excel to reason that

wait let me quickly pull up what i found on excel

A is integer input, C is lesser of perfect square thats closest to value, D is upper instead. I is the floor version of the approximated square root squared again and J is the same but ceiling.

[obtuse lance]

sure no rush, I'll probably be hanging around in different browser tabs all evening

[wet quartz]

lmao, im in the GMT00 timezone so im pretty much just chilling in midnight

ignore 2.439E18, thats a massive triangular number that excel ran into a memory limit

[obtuse lance]

well the thing I have in mind for proving this doesn't really involve a bunch of data, we can prove it symbolically with algebra

[wet quartz]

yeah, i made the excel table to skip having to scroll around in desmos or get my writing pad out

[obtuse lance]

but collecting data is good for making conjectures

[wet quartz]

yeah

[obtuse lance]

one trick to try when you have something is try to reformulate all the words into symbols, and see if laying it out that way helps

[wet quartz]

spent way too long on word equation editor to do that

[obtuse lance]

specifically: "twice a triangular number is between two consecutive perfect squares"

just do it one step at a time, what's the form of a triangular number

[wet quartz]

i would probably use sets to define a triangular number based on its index

so the first few are 1, 3, 6, 15, 21, 28, 45

i imagine theres a function of some kind to convert a given index to a triangular number.

But a triangular number can be manually calculated by using the index as a side length of a triangle made up of dots, completing each side length and then filling that triangle. Then counting the total number of dots

In the end you get a quasi formula where the set indexed by n + 1 involves the value of the set indexed n and a constant based on n+1

Basically like the Fibonacci sequence

im horrible at explaining things

[obtuse lance]

it's ok

[wet quartz]

im visualising it but the words mannn

[obtuse lance]

I was looking for something like, you can represent perfect squares by n^2

what can you represent triangular numbers as

in terms of some algebra like that

[wet quartz]

well if the perfect square is n*n

that sounds like area to me

but my dumbass would say n^2 / 2

[obtuse lance]

there's a kind of nice trick if you've never seen it before by Gauss for how to find the form of triangular numbers

close, good guess

[wet quartz]

hm

[obtuse lance]

if you start plugging in integers to that you get .5, 2, 4.5, 8, ... which aren't too far off from the triangular numbers

you can think of the triangular numbers as building up layers like you were saying

1, 1+2, 1+2+3, 1+2+3+4, ...

and then we can simplify this further, a general term will look something like 1 + 2 + 3 + ... + (n-2) + (n-1) + n

does that make sense what I'm saying so far?

[wet quartz]

yeah

something sorta like this i had in mind

where U index 0 is 0, U index 1 is 1 and then it works providing n is greater than zero

[obtuse lance]

ok cool

[wet quartz]

wait im dumb, forget the n-1 part. I forgot how sets work

[obtuse lance]

it doesn't matter cause you didn't specify the base case, so it's not too serious where you index them by

the main trick to simplifying this is the Gauss trick I mentioned earlier

which involves writing it backwards and summing it up

let me just shwo what I mean here

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

pretend they line up one over the other

if you add up the pairs that way you get
(n+1) + (n+1) + (n+1) + .. + (n+1) + (n+1) + (n+1)

there are n of these, so

we have n(n+1)

and since we added it to itself we double counted so we can divide by 2

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

[wet quartz]

right

that makes sense

[obtuse lance]

cool, so now we know triangular numbers are of the form n(n+1)/2 and that sort of answers my original query here, so we can continue

[obtuse lance]

we're wanting to reformulate the words here into symbols

we have a triangular number is n(n+1)/2, how would you represent twice a triangular number now

[wet quartz]

n(n+1)

seems pretty fair

[obtuse lance]

yeah perfect

ok now if it's between two consecutive perfect squares, let's just try to make a guess at what those would be

is n^2 bigger or smaller than n(n+1)?

[wet quartz]

smaller

n(n+1) is equal to n^2 + n

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

or have i just gotten that wrong

[obtuse lance]

the last part looks suspicious, what's (n+1)(n+2)

[wet quartz]

sub in n+1 to n for n(n+1) gives (n+1)(n+1+1)

given a perfect square is where its root is an integer

[obtuse lance]

this is a true statement but I don't see why you're doing it

[wet quartz]

because n^2 < n^2 + n < n^2 + 2n + 1

[obtuse lance]

we want to show n^2+n is between two consecutive squares

the first square is n^2, what's the next square after this?

[wet quartz]

wait i see what i did wrong

isnt it (n+1)^2

[obtuse lance]

yeah

[wet quartz]

idk where my brain went wrong doing that

[obtuse lance]

I think you just subbed into the wrong expression that's all

[wet quartz]

brain got carried away

so that means n^2 < n^2 + n < n^2 + 2n + 1

[obtuse lance]

wait, what's (n+1)^2

[wet quartz]

im so tired rn

But ok i think i fixed it

i dont even know how im doing A Level further maths rn

[obtuse lance]

mistakes happen, plus you're tired, you can go easy on yourself lol

what helped me cut down on making mistakes was to just work problems very thoroughly and slowly making sure I made no error at any step of the way, and over time I got faster at doing that

my rationale at the time was, I would be reworking the same problem like 2 or 3 times and spending a lot longer over all

maybe that helps you, but anyways yeah that's it we're done

[wet quartz]

i forcibly use lambda and mu for implicit differentiation because v and u look too similar to me. Plus using those funny greek letters makes something in my brain go brr

Oh yeah i love doing the same thing multiple times

maths being unpredictable/new leads to my brain melting

[obtuse lance]

lol I don't love reworking something cause some minor mistake I made at the start forced all my work to be wrong

[wet quartz]

shhh, error carried forward only cuts off one mark in year 1

[obtuse lance]

now something else interesting about this I think might be related to your problem too

notice that we can write it in a suggestive way as:

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

twice a triangular number is basically as close to the middle between the consecutive squares as you can get

since n below and n+1 above are the squares

[wet quartz]

makes sense

yeah, i saw that in excel. When twice a triangular number is given, the approximation functions are the exact same

Which on the graph is between the consecutive squares

[unreal stump]

So does anyone here know about DES?(the block cipher)

[obtuse lance]

cool, hopefully this kind of approach to data you collect and turning it into algebra in the future will help you solve your problems

I know that DES is insecure and outdated

[wet quartz]

i havent had to use anything other than MD5 and some Huffmann stuff

[obtuse lance]

so is triple DES (3DES)

[unreal stump]

Ok,do all DES implementations follow the same table for things like this

[coral parcel]

The S-boxes have to be the same, otherwise it is not DES.

[unreal stump]

So the key and the mode of operation are the only things that are allowed to be different?(for standard DES)

[coral parcel]

"Allowed" is a curious word here. If you change any of the internal working you may or may not still have a cipher that is as secure as DES (which, as Merosity mentions, is not very), but it will not be the cipher that is called DES.

[wet quartz]

well im gonna go to sleep. Thanks Merosity for ur help.

[unreal stump]

Well like I am trying to do a linear cryptanalysis attack DES and I am trying to see what will be the things that will be varying

[coral parcel]

Oh. A cryptanalysis of DES with a modified S-box might still be an interesting learning experience. (Though if you change them to something more linear, most would probably consider that to be cheating).

[obtuse lance]

you're welcome, goodnight

[unreal stump]

I think morally all such "DES"s will still be vulnerable to linear cryptanalysis

[coral parcel]

In any case, the only thing that's intended to vary is the key.

[cyan plover]

I'm trying to simplify a boolean expression into SOP form using K-map... could I simplify my expression more? How do you know if it's fully simplified?

[unreal stump]

You can simplify it further

@cyan plover
Consider you can actually get a octets with 3 and 4

You have to do a wraparound for that

Well if you have 4 octets you can't really get a better simplification than that

In other cases, try to check if you can reduce your quads to octets, or pairs to quads,etc

[unreal stump]

Well you can,but it's the case where everything is 1

[coral parcel]

There needs to be 4 terms, but the terms themselves can be simpler; does that count?

[unreal stump]

Well that's based on intuition. You can't consistently realise if a term can be simpler or not

Like here it's recognisable because a+a'b=a+b is a common identity

[cyan plover]

Thank you. I've tried again with a different grouping...

[unreal stump]

Yeah that is correct

[cyan plover]

thank you

[coral parcel]

That's a also what you get if you just naively De Morgan not(ABCD).

[cyan plover]

what about this... I think it's in POS form? Not too sure how to use a k'map for this

[unreal stump]

Well kmap for POS is funny

You group all the 0s

Instead of 1s

[cyan plover]

but do I make whatever is say, ~A = 0 and A = 1 in the squares?

[unreal stump]

It's the opposite

https://dyclassroom.com/boolean-algebra/product-of-sums-reduction-using-karnaugh-map

[cyan plover]

thank you. POS confuses me:/

[unreal stump]

Yeah it's weird

I don't know who cares about POS tbh

Well actually ig POS can give you simpler circuits than SOP in some cases

[lavish peak]

i need help proving this inequality by induction

$\left(\frac{x+y}{2}\right)^n\le \frac{x^n+y^n}{2}$

[vital dew]

silveh

[lavish peak]

can someone help me

im stuck here

[unreal stump]

Well proving
$x y^k+x^k y \leq x^{k+1} + y^{k+1}$ is what you need prob

[vital dew]

DraK

[lavish peak]

okay thank you

how does that help me exactly?

[unreal stump]

Well what are your constraints on x and y

Are they positive

[lavish peak]

yes

[coral parcel]

That's not generally true, say, if x and y are between 0 and 1. Whoops misread it.

[unreal stump]

Look at the second last inequality

Now use C<=A+B and B<=D implies C<=A+D

[coral parcel]

Somewhere you'll need to use an assumption that x and y are both nonnegative -- since the final goal is not true if one or both can be negative and k is odd.

[unreal stump]

That's given here

[cyan plover]

what happens to the last term on the right side @unreal stump it looks like it isn't in POS form

[unreal stump]

Well the original thing was an intuition. That's why I asked for the exact constraints

[coral parcel]

Yeah, just saying that knowing you need to use that assumption can inform which kinds of steps to look for.

[unreal stump]

Well it's 3 terms actually

[lavish peak]

hmm ill try but i doubt ill reach the final answer

[cyan plover]

yeah sorry three terms. This is what i have so far

[unreal stump]

Ok you need to convert it into the canonical form

[cyan plover]

you mean the boolean equation on top?

[lavish peak]

okay i still dont know what to do

[lavish peak]

does proving this prove that

[unreal stump]

Yeah

[lavish peak]

?

cus that doesnt make sense

[unreal stump]

Well right most term should be
$\frac{x^{k+1}+y^{k+1}}{2} + \frac{x^{k+1}+y^{k+1}}{2}$

[vital dew]

DraK

[lavish peak]

so just ${x^{k+1}+y^{k+1}}$

[vital dew]

silveh

[lavish peak]

ughh im kinda lost in the steps now

[lyric panther]

Do you know about convex functions ?

[lavish peak]

yeah i guess

is there a relation

[lyric panther]

Absolutely

[coral parcel]

If the problem had not explicitly wanted an induction proof, I'd definitely go via convexity here.

[lavish peak]

yeah i guess but this is practice for induction proving

[lyric panther]

This is a typical ahah moment for convexity

But induction is fine here

[lavish peak]

okay so idk where to go from here

[lyric panther]

What is the step that you dont understand

[lavish peak]

i cant just say A<=B and B<=C so A <=C because B=>C

my last step is where im stuck

[lyric panther]

This ?

[lavish peak]

basically what i mean here is

[lavish peak]

^

[lavish peak]

yes

[coral parcel]

Isn't that missing the initial factor of 1/2?

[lavish peak]

I have multiplied the whole equation by 1/2

if u look at the left most term, it is divided by 2^k not 2^k+1 anymore

[coral parcel]

Oh. But then the LHS has been changed from what we were supposed to show something about.

[lavish peak]

yeahhhhhhhhhh...

i was kinda desperate to find anyway to solve this

as i said ikd what to do

[lyric panther]

X,y are positive ?

[lavish peak]

yes

[lavish peak]

^

[coral parcel]

We can definitely not just discard the cross terms, because if x=y they're necessary for getting even equality.

[lavish peak]

okay

i just want to show that the equality holds true for n=k+1

[coral parcel]

What about Drak's suggestion from :46?

[lavish peak]

yeah i looked into it and i either dont know how to prove it or i just simply dont know how it will benefit me

[coral parcel]

I'm not independently sure it can be done, but if it could be done, it would immediately solve your problem.

[lavish peak]

and how so?

because i still havent proved that the middle equation is smaller than the right most equation

[coral parcel]

You'd use it on the last term here.

[lyric panther]

If you show what dirak proposed then youre done

[lavish peak]

okay so given that this is true

how does that prove the main inequality?

its still a term that is added to the RHS

[coral parcel]

Apply. It. To. The. Last. Term. Of. What. I. Quoted.

[lavish peak]

ok

[lyric panther]

^^^^

[unreal stump]

Well that reduces to showing that (x^k-y^k)(x-y) is non negative which is true since (x^k-y^k)=(x-y) * (non negative term)

[coral parcel]

You'd get $$ \begin{array}{c} \left(\frac{x+y}{2}\right)^{k+1}
\le \frac12\left(\frac{x^{k+1}+y^{k+1}}{2} + \frac{x^ky + y^kx}{2}\right) \
\le \frac12\left(\frac{x^{k+1}+y^{k+1}}{2} + \frac{x^{k+1}+y^{k+1}}{2} \right)\end{array}$$

(sigh).

[lavish peak]

lmao

[vital dew]

Troposphere

[lavish peak]

wait

so it is equivalent????

[coral parcel]

What do you mean?

[lavish peak]

u replaced it like it is equivalent

i can do that?

[coral parcel]

"Equivalent"?

If you know A <= B then you also have C+A <= C+B

[cyan plover]

I'm stuck with this problem...I've tried converting it into canonical form but idk wat to do for the last 3 terms

[lyric panther]

If you have A+B then if B<=C then A+B<=A+C

[coral parcel]

Or, in this case, ½(C/2 + A/2) <= ½(C/2 + B/2).

[lavish peak]

ohhhhhhh

okay that makes a lot of sense

okay it just clicked

alright thank you so much

appreciate the help

[lyric panther]

Maybe you can show the ineq of drak now ?

[lavish peak]

ill implement it but i dont think ill go with proving it as a lemma

ill just

state it

[lyric panther]

Its not hard

[lavish peak]

ill try doing it now

[unreal stump]

The canonical form is really stupid for this
$\bar{A} = (\bar{A} + B + C + D)(\bar{A}+B+C+\bar{D})(\bar{A} + B + \bar{C} + D)...$

[vital dew]

DraK

[unreal stump]

Basically fix \bar{A} and take all combinations of B,C and D

You should get 8 terms

If you do not want to do this, note all the entries that will give you zero when applied to the expression.

For example A=1 ,B=0,C=0,D=0 will make \bar{A} zero. So mark a 0 in that box

Same for A=1, B=1 ,C=0 and D=1

[cyan plover]

why is ~A = to the canonical form?

[unreal stump]

Well ~A is technical a sum term

A sum term with one entry

[cyan plover]

i'm confused

I thought it would be Y = (the boolean equation)

[lyric panther]

@lavish peak if there is any issue ask

[unreal stump]

Well if you find canonical form for each term, you will just multiply all of them together to get the canonical term for exp

[lavish peak]

okay thank you

[cyan plover]

I understand that but why is the expression equal to ~A?

[unreal stump]

Well so you find can(A)

Well you have \bar{A} , \bar{B} and \bar{D} at the end

[cyan plover]

yes

[unreal stump]

So you have to find can(A), can(B) and can(D)

[cyan plover]

ohh okay

[unreal stump]

*can(\bar{A}),can(\bar{B}),can(\bar{D})

[cyan plover]

i'm still a little confused, how do you find can(A)

[lavish peak]

here is my attempt at proving the inequality 🧍‍♂️

this obviously requires y to be smaller than x

which is not what i want

[lyric panther]

When you have an inequality the first thing you should do is get everything on one side

[lavish peak]

im guessing i made a mistake

[unreal stump]

So you just find the values of A,B,C,D that make the expression 0

And then find the corresponding maxterm

And multiply all these maxterms

[lavish peak]

okay ill attempt that

[lyric panther]

Scrath that

[unreal stump]

So here
(1,0,0,0),
(1,0,0,1),
(1,0,1,0),
(1,0,1,1),
(1,1,0,0),
(1,1,0,1),
(1,1,1,0),
(1,1,1,1)
are the values of (A,B,C,D) that make the expression \bar{A} 0

So max term corresponding to (1,0,0,0) is (\bar{A}+B+C+D)

[lavish peak]

i can only factor by x+y if i do that

[unreal stump]

Find all such max terms

Multiply

And you have your canonical form

[lyric panther]

In fact your are done

Sorry that is my mistake

[lavish peak]

its okay dont worry

[lyric panther]

.

[lavish peak]

so i was done at this step?

[lyric panther]

Suppose x>y and x=y

And x<y

[lavish peak]

but the inequality i found

the last one

is not always true if x and y are any positive real numbers

[lyric panther]

In fact it is

[lyric panther]

Split cases

[lavish peak]

im confused, so what if y=4, x=2 and k=3

the inequality is false

64<=8

[lyric panther]

?

[lavish peak]

oops

[lyric panther]

You have minus

[lavish peak]

yes yes my fauly

[lyric panther]

Read my message

[lavish peak]

arent these 2 equivalent?

[lyric panther]

ahah

[lavish peak]

if i divide by x-y

both sides

[lyric panther]

Be careful

Read my previous message

[lavish peak]

split cases?

[unreal stump]

Alternatively rewrite that as 0 <= (x^k-y^k)(x-y)
and factor out (x-y) from (x^k-y^k)

[lavish peak]

okay

ok when i rewrite as drake mentioned, the inequality always holds

[lavish peak]

but really quickly can you explain why this cant be done?

[cyan plover]

sorry... how do you know if the expression is 0

[lavish peak]

i feel like its a stupid mistake

thank you for everyone that helped heres my final answer

heres the question

appreciate it

[unreal stump]

You substitute the values in expression

Do you agree A=1, B=0,C=0,D=0 makes \bar{A} 0?

[cyan plover]

I'm still a little confused with bar A tbh

but would this k'map be in the right direction?

I'm getting Y = (~A+~D)(~C+~B)

[swift gyro]

Hey does anyone have any practice problems/ worksheets (with sol) for discrete Math topics - number theory , modulo congruence, propositional logic , predicate logic and induction.

[sour scarab]

I'd recommend getting a textbook you enjoy to both study and work out the exercises in

[agile magnet]

what textbook does your class use?

just work out of that

unless there is no text then people here probably have recommendations

[swift gyro]

They don’t use any . Just give notes and one worksheet which is not enough imo

[swift gyro]

Which textbook do u recommend?

[sour scarab]

discrete math can vary in the material covered, so check your syllabus if it has a recommended textbook at the very least first. Otherwise, google is your friend.
This thread on math stack exchange has a lot of computer science focus but should be a decent resource for a variety of different books. again, google is your friend.
https://math.stackexchange.com/questions/1533/what-is-the-best-book-for-studying-discrete-mathematics

[swift gyro]

Got it . Thank you so much

[spiral aspen]

can someone explain how this works? i dont get the combinations

i can do it manually but not the formula way

so say length = 3 {001} {111}
this means i can have 1 (ways of arranging 111) + 3 (ways of arranging 001 is 3!/2!)

but then for length 5 we have {00000} {11111} {00001}
so 1+1+5!/(2!*2!) (ways of arranging {00001},

this is wrong though. wats the correct way of doing arrangement for 00001?

[lofty patrol]

Hey! I'm a bit confused on cardinality of sets relating to countability. Why would choice A be countably infinite? And same question for B: but what even is left after we subtract the rationals from the cartesian product? I'm confused on how to approach this.

[sour scarab]

firstly A is countably infinite as you can list all of them in an infinite amount of time. More precisely, Q is countably infinite, so it must be that Q - N is countably infinite.
secondly, (Q x Q) - Q is just (Q x Q) as the two sets are disjoint. One is a set of tuples, and the other is a set of rational numbers.

is there something else I can help you with?

E should be uncountably infinite as it's a power set of real numbers

[sour scarab]

does this help?

[cyan pecan]

Question 2a

[hexed shore]

How do I prove a solution of a recurrence relation?

[lofty patrol]

Thank you! So for (Q x Q) - Q, we are subtracting out what is found in both (Q x Q) and Q? So, since there isn't any just rational numbers in the cartesian product, is that why we're left with the same thing?

[hexed shore]

Non homogenous

Saying a_n = 2a_{n-1} + 2^n with the solution a_n = n2^n

[lofty patrol]

And to confirm, for choice D: is it countably infinite because it's kinda just like the cardinality of positive integers? I got confused because i know that real number sets are uncountable. but here, we're just saying that the numbers in the set happen to be real. is that why/the difference?

[sour scarab]

precisely. "-" isn't subtraction as much as it is a difference between the sets, i.e. "A - B" is whatever is in set A but not set B. in this case we're comparing a set of tuples to a set of rational numbers, which are two different objects.

[sour scarab]

and yes it's because the cardinality is the same as the integers. I'm not sure if you've gone over functions yet, but any set that has a bijection between itself and the natural numbers (and by extension the positive integers and integers in general and also rational numbers) is countably infinite. the set in part D is very nearly defining that function but as a set

[iron sorrel]

why are they choosing different numbers

for x1 and x2

when x1=x2

[coral parcel]

The point of that example is tat you don't necessarily have x1=x2.

[sour scarab]

it's to prove by definition that f is not one-to-one. f(x1) = f(x2) when it's not always the case that x1 = x2 means f is not one-to-one

f would be one-to-one iff f(x1) = f(x2) => x1 = x2

[iron sorrel]

yea and we get x1andx2 = 1

so its not 1-1

i see

[sour scarab]

exactly

[iron sorrel]

would u know how we solve this

i dont get how to solve when they give us question like this

[sour scarab]

so this is a question for cardinality. have you guys gone over that yet?

[iron sorrel]

cardinality?

[sour scarab]

like, how big a set is.

[iron sorrel]

could u give an example of what u mean

[sour scarab]

the cardinality of $ { a, b, c } $ is 3

whereas the cardinality of Z+ is countably infinite

[iron sorrel]

yea

[sour scarab]

ok cool and do you know what a power set is?

I'm essentially just trying to see if you know Cantor's theorem.

[iron sorrel]

example?

[sour scarab]

a power set of set A is defined to be the set of all subsets of A

[iron sorrel]

yes

i have learnt that

[sour scarab]

ok D isn't exactly a power set, but it might as well be one.

Cantor's theorem states that the power set of any set A is strictly larger than the set A itself

[iron sorrel]

have not learnt this

[sour scarab]

I'll go and get a proof really quick but it's pretty simple

actually, let's work this out right here I think that's the point of the problem.

[iron sorrel]

i dont think we are supposed to do this if we havent leart that

[sour scarab]

yeah

so a function is one-to-one if we map every element of its domain at most once to some element in its codomain, right?

and likewise a function is onto if for every element in the codomain, we map something in the domain to that element.

in a way we're saying that a function is one-to-one iff $n(A) \leq n(B)$ where A is the domain, B is the codomain, and n(A) is just the number of elements in A.

[vital dew]

Borger

[sour scarab]

This is because we have to have every element in A mapped to B at MOST once. Some elements in B may not be mapped to, so there are cases where n(A) <= n(B).

[iron sorrel]

oh and for onto all n(A) = n(B)

[sour scarab]

Conversely, a function is onto iff $n(A) \geq n(B)$. Think of this as going in the opposite direction. Every element in B must be mapped to, but some elements in A can be mapped to more than one thing.

[iron sorrel]

since all y have to go to an x

oh nvbm

[vital dew]

Borger

[iron sorrel]

i see

ok

[sour scarab]

but you're on the right track! n(A) = n(B) when?

if we have onto implying $n(A) \geq n(B)$, and one-to-one is $n(A) \leq n(B)$, what can we say about the function when $n(A) = n(B)$?

[vital dew]

Borger

[iron sorrel]

if onto implies all A go to b once

and 1-1 implies all B go to a once

n(a) = n(b) if all domain and codmain go to each other only

once

[sour scarab]

exactly. that's called a bijective relation, or a one-to-one correspondence

[iron sorrel]

yea i have learnt that

[sour scarab]

anyways that's off track from the question but I personally think it's important for this kind of math

[iron sorrel]

correspondense if onto and 1-1

[sour scarab]

yep yep

so right now we have that:
n(A) >= n(B) iff T is onto
n(A) <= n(B) iff T is one-to-one
and the power set is strictly larger than the original set

since D is, for all intents and purposes right now a power set, what can we say about T: Z+ -> D?

[iron sorrel]

d is a subset of Z?

no

[sour scarab]

no D is a collection of subsets of Z+.

[iron sorrel]

idk then

[sour scarab]

remember the power set is strictly larger than the original set. If D were a tiny bit bigger and WAS the actual power set of Z+, what would D's cardinality be relative to Z+?

https://proofwiki.org/wiki/Cantor's_Theorem

just for reference

[iron sorrel]

wb this question

how is 2n not onto

[sour scarab]

this is an exercise for just proving two different things, remember the definition for something being one-to-one and onto. See if you can prove it or find some counterexample that doesn't work.

[haughty garden]

Can you obtain odd integers?

[iron sorrel]

how is it not onto

[haughty garden]

If it’s onto, it should, for example, map an integer to 1

Is this actually possible though?

[sour scarab]

I actually thought this would be onto since there's a bijection between integers and even numbers...?

huh. I should review that

[haughty garden]

There is, this is not the bijection

The bijection would require the codomain to be 2Z

[sour scarab]

ah.

[haughty garden]

This function maps integers to integers, but it only hits even integers

[sour scarab]

that makes sense my bad

[iron sorrel]

im confused

how is this not onto

because it only goes for even integers?

[sour scarab]

there's an element in the codomain that isn't mapped to, e.g. 1

[sour scarab]

yes

[iron sorrel]

so like 1,3,5.7

[sour scarab]

precisely

any odd number is not mapped to

like opengangs said, if the codomain were the set of even numbers instead, it would be onto

[iron sorrel]

ok im so confused

how are u supposed to tell if it is onto or one to one

like the examples my teacher is this

[sour scarab]

that's admittedly hard to read. Trev tutor has some good videos on functions I'll send them here

[iron sorrel]

4n-5=y

[sour scarab]

https://youtu.be/bZred_Ksz2k

[iron sorrel]

n=y+5/4

4(y+5/4) -5

= y

[iron sorrel]

im using textboox

[sour scarab]

yeah but these are just some videos to follow along with if you want

[iron sorrel]

like here

[ebon berry]

what is the negation of an if then statement

im studying for my midterm on tuesday and im trying to make notes

i tried looking it up but i dont get a direct answer

[chrome osprey]

and how do u prove either side

[chrome osprey]

i would expand the if statement

(p -> q)

(~p v q)

so

~(~p v q)

expand that