right, I see
#discrete-math
blazing rose
oblique rock
Anyone able to explain the last step, I get that they used property (2) here, but I'm not sure how to use it when there is an exponent involved? Why is the exponent ignored?
last flicker
By repeatedly applying property 3, if n is an integer and a=b (mod c), then a^n=b^n (mod c)
oblique rock
By repeatedly applying property 3, if n is an integer and a=b (mod c), then a^n=...
Are you able to help me here? I'm trying to prove that 3^41 - 5 is divisible by 7.
I'm not sure if I did it right though
oblique rock
i found it 🥲
indigo ferry
For no x element of A ?
You'd say there does not exists x in A such that P(x)
∄ x∈A | P(x)
or are you asking for a way to prove this?
chrome sand
so basically no element in x in A could make P(x) true
indigo ferry
yeah
chrome sand
oh ok
chrome sand
∃ x∈A ¬P(x)
does this say
there exist atleast 1 x in a so that P(x) is false?
¬ ∀ x∈A P(x)
there exist no x in a which makes P(x) true
brave rock
there exist atleast 1 x in a so that P(x) is false?
This is right
brave rock
there exist no x in a which makes P(x) true
No, this is wrong. This says "not every x in A has P(x)"
indigo ferry
¬ ∀ x∈A P(x)
So this is equivalent to saying ∃ x∈A ¬P(x)
chrome sand
so in our script it says every number n in N and geater or equal 2
is a product of prime numbers
what is with 3
how is 3 a product of prime numbers
isa 1 a prime number
chrome sand
e.g. 3 is a product of 3 * 1
3 ia a prime number but 1 is not a prime number
how can 3 be a product of prime numbers
coral parcel
3 is the product of one prime number, namely 3 itself.
chrome sand
how can a product have only one number
coral parcel
By convention, if we speak of a product of a list of numbers, then for a list with a single element, we get that element itself.
It's not particularly deep, just makes a lot of results (such as prime factorization) easier to state.
coral parcel
3¹.
In fact the convention is very often extended to saying that the product of a list of no numbers is 1, so 1 has a prime factorization too: the empty factorization.
coral parcel
Actually makes good sense. It corresponds to a straightforward way of computing the product of a list:
a = 1
for n in listOfFactors:
a = a * n
return a
and the products of lists with no elements or one element is the natural consequence of that.
(Assuming you'll be comfortable with programming since you're classifying your question as "discrete math").
chrome sand
are you familiar with the satz of bezout
that the greatest common divisor of 2 numbers can be written as a liner combination
coral parcel
Usually known (for odd reasons) as Bezout's identity, yes.
chrome sand
why is it the min of that set
do you maybe have a concrete example
i i have 4 and 6
ggT(4,6) = 2
what would be the linear combination of that
2 * 1 + 4*0?
coral parcel
No, because you're looking for 4·(something) + 6·(something else) = 2.
For example 4·(-1) + 6·1.
chrome sand
isnt 2 · 1 + 4 · 0 =2
coral parcel
Yes, but you said you're looking for gcd(4,6) not gcd(2,4).
chrome sand
and another question how you go about learning stuff like this
you treat those sentences as an abstract concept
or you try to translate them into real examples
like 4 and 6
coral parcel
Definitely keep concrete examples in mind, as much as you can.
chrome sand
and why is it the min of that set
coral parcel
The point is that the numbers that can be written as ax+by are exactly all the multiples of the gcd.
chrome sand
ahhh than that makes sense
weary tiger
¬(p ∨ q) this ¬ covers p and q both right ? without parentheses it would be ¬P∨ ¬q
vestal bronze
yes
weary tiger
¬(p → q) what about this
→ would change with what ?
or just p and q would swap places
vestal bronze
(p → q) means (¬p ∨ q)
weary tiger
how is that im bit confused
ebon tide
Are there any good discrete math resources online?
weary tiger
Are there any good discrete math resources online?
on zybooks.com
stray galleon
can anyone teach me how to solve this without truth table
fathom void
#3 and #4 is that not Modus Tollens
vital arch
@stray galleon Here is the solution:
~t and p->t => ~p
~p => ~p v q
~p v q -> r and ~p v q => r => ~p /\ r
~p /\ r -> ~s and ~p /\ r => ~s
~s and s v ~q => ~q
for the 2nd step with addition, can we pull anything to ~p?
that's not explicitly negated
in other words how did you come up with vq
vital arch
That's "or introduction" If something is true, then it or something else is also true trivially
fathom void
the or could have been anything?
vital arch
Yup
fathom void
example t, even if it was stated as a premise ~t?
or do we need to take the ~t into consideration
vital arch
I'm not sure what you mean
vital arch
Sure, but that wouldn't advanced the proof
fathom void
similarly, could I have picked ~p v ~t?
vital arch
Sure, it's still true because ~p is true (or deduced rather)
fathom void
thanks
so really for an or-introduction (or addition as i've learned) the v can be ANYTHING even if the premise says the opposite
it makes me feel a little uneasy how easy i can make something appear out of nothing
sudden minnow
if it is true that "I'm a mathematician" it is also true that "I'm a mathematician or I'm the president of the United States"
vital arch
Well, you always have p v ~p because of the Law of the Excluded Middle (LEM), so you can always get something out of nothing (unless you're an Intiuitionist)
fathom void
if it is true that "I'm a mathematician" it is also true that "I'm a mathematici...
makes sense!
does the or HAVE to be something false?
vital arch
No
sudden minnow
you could say I'm a mathematician or I'm a mathematician
vital arch
Or is inclusive in mathematics
fathom void
- pVq=>r premise
- sv-q premise
- -t premise
- p=>t premise
- -p^r=>-s premise
- -p (3,4 modus tollens)
- -pVq (6, addition / or-intro)
- -q (6,7 disjunctive syllogism)
i came up with this
would that work?
spring hound
1. pVq=>r premise
2. sv-q premise
3. -t premise
4. p=>t premise
5. -p^r=>-s pre...
6 and 7 alone cannot prove ¬q.
If ¬p is true, then ¬p ∨ q is satisfied solely by ¬p, with no requirements on q.
q could be true or false and 6 and 7 would be true.
fathom void
fallacy of confirming the conclusion!
twin basin
Hey I am trying to figure this out, I have already turned it in, but I am just wondering how to get sum of product form from the reduced form given
spring hound
Hey I am trying to figure this out, I have already turned it in, but I am just w...
It looks like they circle the 1s instead to get the sum of products. Like the bottom half circled gives you y in the sum at the top.
twin basin
I'm sorry, I'm not following 😦
wait
okay, so pretend I wasn't given the map, like just the function, that's what I was supposed to figure out, it doesn't matter now because I already turned it in, but I just wanted to see how I did it wrong
given F, find the kmap were the instructions
spring hound
You mean take the top line and get the table in the middle?
twin basin
yes
spring hound
OK, so you have an empty 4×4 table.
Then, you go term by term.
First term is y. So, you mark all slots where y = 1 as 1.
That's why the bottom half is all 1s.
Second term is x'z', so you mark all the spots where x = 0 and z = 0 as 1s.
twin basin
okay, yeah got that, and then do the same for w'xz
spring hound
Right.
twin basin
wow, okay, that makes more sense, i think it was the way it was given to me in the instructions, im just nervous I won't be able to learn it in time to pass the course, prob gonna need to study discrete on my own to help out, is the Rosen book a good start?
spring hound
Oh, I'm not sure on books.
twin basin
Your 2 min explanation helped me more than the professor did in 2 lectures
spring hound
To get the minimized forms from the table, you know how in some games, the board or map wraps around?
twin basin
yeah
spring hound
OK, it's like that.
If you go up from the top, you end up at the bottom. If you go left from the left side, you end up on the right side, and so on.
To get the sum of products, you want to create the biggest rectangles around 0s that you can.
That will tell you the reduced form at the top that you started with.
Oh, sorry, surround 1s with rectangles to get the sum of products.
So, the entire bottom half can be handled by one rectangle.
Similarly, the corners of the grid are 1s, and they can be handled by a 2×2 square that wraps and hits all the corner slots.
twin basin
I think I read where groups can only be powers of two correct? so 1, 4, 8
spring hound
Yes, the dimensions of the rectangle must be powers of 2, but they don't have to be the same power of 2.
So, the bottom half is covered by a 2×4 rectangle.
twin basin
and instead of looking at it in terms of minterm since its product of sums, it would be maxterms
spring hound
I forget what those terms mean, but covering the 1s with the largest rectangles possible does the sum of products and covering the 0s with rectangles gives the product of sums.
So, for the 1s, you've got the bottom half, the corners, and the last 1 is covered by a 2×1 rectangle (make the rectangle as large as you can, so don't do 1×1).
And you can't do 4×1 there, so you're stuck with 2×1.
twin basin
okay, so I understand how you made the map, now how do I get the product of sums from the map, okay covering the 0 with rectangles and then what? group the 0s according to the rules, but then how do I get the actual terms?
spring hound
OK, it's similar.
The map you have already has the 0s covered by the biggest rectangles possible.
So, you look at the three rectangles. Let's look at the one in the top row.
What variables don't change in that rectangle?
Well, w changes, but nothing else does. x y and z are all 1, 0, and 0.
So, you do (x' + y + z).
It's sort of like DeMorgan's.
twin basin
gotcha, and we're saying that x' == 0 in this case
spring hound
Right.
twin basin
we want our term to equal 0
spring hound
With a product like before, you'd have xy'z'.
Then you do DeMorgan's on it to get (x' + y + z).
And the same with the other two rectangles.
twin basin
huh why does the one in the second row have a rectangle around 3 0s?
spring hound
It's two 1×2 rectangles overlapping.
spring hound
Right.
twin basin
welp, I'm a day late and a dollar short on learning this, but honestly better late than never, I definitely understand a lot better now. I will probably fail this exam, but maybe I will at least get these type of questions right thanks to your help.
spring hound
If you want to get more confidence, you can create some 4×4 tables like that one and fill them in randomly with 1s and 0s. Then, get the two reduced forms from that.
And then, copy the reduced forms to another page and get the table back from it.
If you want to.
twin basin
True, that is very smart and great practice. I will definitely need to try that
spring hound
Just make sure it's really random, so that you'll occasionally have some big blocks of 1s or 0s to practice on those.
,w Table[RandomInteger[{0, 1}], {i, 1, 4}, {j, 1, 4}]
vital dewBOT
spring hound
Wolfram Alpha can give you some practice tables.
twin basin
yeah I think that's a great idea that I didn't think about,
wow that's impressive
what are those second and third parameters?
spring hound
Those are the dimensions of the table.
So, 1 to 4 for width, then 1 to 4 for height.
Just remember to use the 01 and so on labels on the top and left sides from your example before.
The ordering of that is important.
One bit changes as you go forward.
00 → 01 → 11 → 10 has one bit change each time.
If some other number of bits change, the Karnaugh table doesn't really work anymore.
twin basin
gotcha, cool I will practice with that, and yeah I remember that was an important thing we were taught
It is interesting stuff it's just very challenging, and I'm prone to beating myself up, when really it's just something else to learn, especially discrete math because it applies directly to what I want to be: software engineer
spring hound
Yeah, the only thing you can really do is try to get a decent understanding and practice it if you have time.
twin basin
Yup, working on that discipline, because I know that a lot of algos and data structures have their foundations in logical proofs, which are covered in discrete
spring hound
If you're interested in going further in learning proofs, there are math courses like discrete math beyond calculus that tend to require proofs.
Also, the math or philosophy department might have a course in first order logic (though make sure ahead of time that it covers that, some courses don't), which deals with symbolic logic skills useful in creating and verifying proofs.
SamuraiJack just above your original question was doing a bit of that.
twin basin
I've heard it's a good way to understand math, or have a better appreciation for what's going on, I'm just trying to break my own personal mental block of giving up when things get tough, because I can't really grow and learn with that attitude, especially math
carmine swallow
hey, does anyone knows where did the 4 came from?
runic ginkgo
Anyone know any useful relations between undirected Eulerian graphs and directed Eulerian trails?
Let $\vec{G}$ be a digraph that is not Eulerian, but where its underlying (undirected) graph $G$ is Eulerian. Show that $\vec{G}$ does not have a directed Eulerian trail.
The only related result I know of is: a weakly connected digraph $\vec{G}$ has a directed Eulerian trail if and only if at most two vertices have their indegree and outdegree unequal in which case for one of them $u \in V(\vec{G})$ : $d^+(u)-d^-(u)=1$
vital dewBOT
e57721
silk lily
Absolutely lost with this one:
Show that $(0, 1)$ and $\mathbb{R}$ have the same cardinality by showing that $f(x) = \frac{2x-1}{2x(1-x)}$ is a bijection from $(0, 1)$ to $\mathbb{R}$
vital dewBOT
Haticus
cerulean wind
what have u tried?
twin basin
@spring hound thank you so much, there were like 3 kmap questions on my test and I got them right because of what you explained to me
coral parcel
Absolutely lost with this one:
Show that $(0, 1)$ and $\mathbb{R}$ have the sam...
This is not very discrete, but the exercise seems to give clear instructions about how to proceed. Have you sketched the function it tells you to prove is a bijection?
civic spoke
What are some prerequisites to understanding discrete math?
wide vine
can anyone help me determine what maze generation algorithm I am using
okay so I have some grid of x by x
11x11
then the first step
create "neighbors"
pick any random neighbor to start the maze generation
Then randomly dig in a given direction
and keep the process going randomly digging until you find all the neighbors, back tracking if required
and it can only dig through to walls that connect non connected "neighbors"
so it can dig through itself
and then it is done
idk what this algorithm is called though
twin basin
Hey, I was wondering on how to reduce this,
F(abcd) = (a'b + ab')(cd + c'd') + (ab + a'b')(c'd + cd')
brave rock
What do you mean by "logically equivalent" exactly?
mighty flame
like if I had set A and set B, and I already know A=B, I mean logicially equivilant in the sense that saying "I have set A" is the same as saying "I have set B"
brave rock
Sure I guess, but I've never heard of such a thing.
brave rock
That is just the definition of A = B.
mighty flame
ok thanks
that clears it up, I was struggling to find the right words to finish the proof
ornate creek
is (d) considered to be well ordered?
I would say yes because the minimum of any subset is just the smallest combination of m/n.
ornate creek
Also could the set of rational numbers greater than let’s say 2 for example, be a subset of the rational numbers greater than or equal to sqrt(2).
stray reef
well-orderedness is not a matter of consideration
however, G is finite. so yes, it is well-ordered.
G may be stupidly large (about a googol^2) but finite it still is
ornate creek
well-orderedness is not a matter of consideration
I see thank you 🙂
wicked bolt
G may be stupidly large (about a googol^2) but finite it still is
how is it finite? 😕
ornate creek
how is it finite? 😕
I think it has a smallest element possible (1/googol). So we can't have an infinitely small number. But it has an infinite maximum
vital dewBOT
Wuff
Compile Error! Click the 
reaction for more information.
(You may edit your message to recompile.)
brave rock
That doesn't look like a power set to me, you're missing a few subsets.
uncut coral
how can i set up a recurrence for climb stairs problem with a condition such a person cannot climb 2 stairs in a row?
i know without condition its t(n) = t(n-1) + t(n-2) with t(1) = 1, t(2) = 2
cerulean wind
could you provide an example of what you mean for n = 3 or 4?
cerulean wind
P(M) = {$\emptyset$, {Alex}, {Hannah} , {Klaus}, {Isabel} {Klaus, Isabel},
do you mean M = {0, {A}, {H}, {K}, {I}, {K, I}}?
uncut coral
could you provide an example of what you mean for n = 3 or 4?
so a person can climb either 1 or 2 stairs at a time, but cannot continuously climb 2 stairs. for example, for n = 4, a person cannot climb 2 stairs + 2 stairs, for n = 5, cannot climb 1 + 2 + 2 or 2 + 2 + 1 but 2 + 1 + 2 works
cerulean wind
okay
uncut coral
i actually found the relationship T(n) = T(n-3) + T(n-1), but how can I find the solution for the recurrence?
cerulean wind
i actually found the relationship T(n) = T(n-3) + T(n-1), but how can I find the...
sorry i got distracted. yes this is the correct relationship. do you know what the characteristic polynomial is?
uncut coral
yeah i was trying to solve using that
but uhmm
tbh i found that relationship by trying to find patterns
so i dont rlly know why that relationship works
and is x^3 = 1 + x^2 the characteristic polynomial for this?
cuz then the root is a bit weird
cerulean wind
i can't quite put together a good explanation as of now, however, the way to think about it is to look at how the number of ways to get to the last step is determined by the number of ways to get to the second to last step (n-1), the third to last step (n-2), and the fourth to last step (n - 3)
uncut coral
i got roots like 1.146557123187677 lol
cerulean wind
there are three roots, two of which are complex
uncut coral
oh then i have to involve complex roots as well
cerulean wind
yes but finding the roots to this polynomial seem a bit difficult
uncut coral
oh
the question didnt ask me to solve the recurrence
lol
if f(x) is smth like (x-a)/(x-b) and g(x) is constant, then is f(x) = O(g(x))?
im pretty sure that f isn't just a linear eq so
coral parcel
so i dont rlly know why that relationship works
Whenever you reach a step you can either choose to move 1 step or 1+2 steps, and once you set the right start conditions that's the only context you need to consider twos in.
cerulean wind
if f(x) is smth like (x-a)/(x-b) and g(x) is constant, then is f(x) = O(g(x))?
yes. lim f(x) = 1 as x --> infinity
uncut coral
thanks!!
hard canyon
can some one explain this to me
dry raven
Can someone explain why I was wrong in these?
covert bolt
can I say $x^2 - y^2 \equiv 0 (mod p)$?
vital dewBOT
Opify
unreal stump
Yea sure
covert bolt
I dont understand the solution for 6d
haughty peak
do you guys know what this is asking? i’m kind of confused
stray reef
@haughty peak part a asks you to draw two weighted graphs which are isomorphic if you ignore the edge weights but aren't if you don't.
haughty peak
<@812193807109849088> part a asks you to draw two weighted graphs which are isom...
what do they mean by weighted graphs tho? the number of degrees a vertice holds ?
stray reef
no
...you could have said "I don't know what a weighted graph is", honestly. would've been clearer what your confusion is.
haughty peak
my bad
stray reef
a weighted graph is a graph in which each edge has a number attached to it.
that number is, as the name suggests, often called the weight of its edge.
blazing steppe
I had a random thought the other day that "self similarity" might be formalised in terms of isomorphism.
Today, I tried sketching out what a formalism might look like (I stuck to sets because I don't know any other mathematical abstractions well enough to play around with them in interesting ways).
It's kind of bare, but I think it's comprehensive enough (any notion of similarity can be encapsulated in our choice of equivalence relation) and unambiguous given an explicit specification of said equivalence relation.
https://www.lesswrong.com/posts/zhhYwM7gk8LZsDzxj/dragongod-s-shortform?commentId=sLC9ANwAGCiYtCDng
haughty peak
that number is, as the name suggests, often called the _weight_ of its edge.
makes sense. so i can basically draw two triangles for which they have 3 vertices and are isomorphic, depending on how i draw them, and just add different weights to the edges?
stray reef
your graphs don't need to be triangles specifically
though with 3 vertices there is not much to do on that front
but yes, draw two copies of the same (unweighted) graph and then add different weights to the edges
haughty peak
your graphs don't need to be triangles specifically
i understand but yea drawings are limited when it comes to 3 vertices is what i know for sure lol
haughty peak
but yes, draw two copies of the same (unweighted) graph and then add different w...
and ight
stray reef
theres only four different graphs on 3 vertices up to isomorphism i think
triangle, path, edge w/ loose point, or 3 loose points
haughty peak
@stray reef
fathom void
can someone explain why this is false?
I'm imagining 2 small circles joined together inside a bigger circle. Doesn't this imply that everything outside of the 2 smaller circles, is bigger than everything outside the bigger circle?
Just thinking again... is it because A, B, and C can be the same size?
so >= would be the more valid response?
outer kayak
am i on the right track? im a bit confused here
brave rock
You were so close until the fourth line, starting "Suppose we have ..."
Also just want to point out that you need to write \{ and \} to make braces appear in TeX. Also be aware that you're not using math mode in some places that you should.
Anyway, onto the actual argument
You should simply say "if a R b, then by definition b is in [a]".
However you start to go off track
brave rock
You begin by assuming x is some arbitrary element of [a], but this is totally extraneous
outer kayak
im listening.
brave rock
Why do we have to consider an arbitrary element of [a]? We're not trying to prove anything about all elements of [a]
brave rock
You should simply say "if a R b, then by definition b is in [a]".
As I pointed out here, this is enough.
There are some further issues though
It is worrying that you say x \in b... this is not meaningful
coral parcel
You rang?
brave rock
Some new guy trying to be funny
brave rock
It is worrying that you say x \in b... this is not meaningful
@outer kayak can you explain what your thought process was when you wrote x \in b? It concerns me that you put this down
outer kayak
yes @coral parcel @young oriole entire comment history is him being not so nice
outer kayak
<@707365051996045334> can you explain what your thought process was when you wro...
one second catching up to your comments
coral parcel
As you wish.
outer kayak
You should simply say "if a R b, then by definition b is in [a]".
you mean as my if then template? or at the suppose part
outer kayak
Why do we have to consider an arbitrary element of [a]? We're not trying to prov...
true
brave rock
you mean as my if then template? or at the suppose part
I don't know what you mean by that, but I mean that what I said there finishes the argument after the 3rd line. Everything after "Suppose we have..." is not only unnecessary, but incorrect
outer kayak
<@707365051996045334> can you explain what your thought process was when you wro...
this was following the line of thought of that arbitrary element, you pointed out its not needed
outer kayak
I don't know what you mean by that, but I mean that what I said there finishes t...
will remove.
brave rock
this was following the line of thought of that arbitrary element, you pointed ou...
OK it concerns me that you're saying this, because the issue I have with the statement x \in b is not the line of logic, it is the fact that b may not be a set, and may not contain anything at all
What do you mean precisely by x \in b?
outer kayak
what i was trying to do was show if [a] = [b] from part 1, and x is an element of[ a], then x is also an element of [b]
brave rock
Right, so this was just a typo and you meant x \in [b]?
brave rock
what i was trying to do was show if [a] = [b] from part 1, and x is an element o...
I should point out that this is just what it means for two sets to be equal
outer kayak
yes
outer kayak
[b] not b is what i meant
i guess my question is how can i go from what i have now to my conclusion
brave rock
You haven't argued why [a] = [b] properly
But it really doesn't matter
I'm not going to walk you through this because I think you can do this entirely on your own. Try to argue why it's sufficient to show that a \in [b] implies b \in [a]. (as I have helped you show)
outer kayak
ok thank you
hollow tartan
Can someone please explained in detail why this answer is correct?
outer kayak
does anyone have any ideas here ?
outer kayak
@brave rock ?
brave rock
Hi, please don't ping me to ask for help. I'm not always available or willing to help.
I have a life outside of this discord server!
outer kayak
got it, sorry
uneven violet
does anyone have any ideas here ?
You have a group of n physicists. Among these you want a subgroup of size k that get to inhabit Mars. One of the chosen physicists has to fly the spacecraft.
See if you can write this in two different ways as the product of a number of choices.
outer kayak
You have a group of n physicists. Among these you want a subgroup of size k that...
thank you i took care of it
what about this? the RHS seems straightforward but the lhs....
sudden minnow
what about this? the RHS seems straightforward but the lhs....
you want to pick n things out of 2n things
imagine dividing your 2n things into 2, n things
sudden minnow
once you get good at seeing a bunch of additions as just one sigma, it wont be so overwhelming
torn grail
Hi, can someone advise me on this problem? I'm not sure how to approach it
the k is throwing me off
coral parcel
Can you compute the probability that the card you see in step n has not been seen before, independently of which other repetitions there might have been?
(It might be easier to think of the probability that the card you see in step n will not be seen in any of the steps n+1, n+2, ..., k).
torn grail
ok so step 1 would be 52/52 , step 2 would be 52-1/52, step 3 is 52-2/52.... step k 52-k/52
wait i think i read your statement wrong
coral parcel
Try the second formulation instead.
torn grail
i'm not sure what you meant in the second sentence
coral parcel
Suppose you draw a card with replacement 17 times.
What is the probablity that whichever card you draw as number 8 is the last time you see that card?
Huh, why?
coral parcel
I mean the 8th draw.
torn grail
ok so basically all cards up until the 8th draw
coral parcel
No.
torn grail
draw 1 card with replacement?
oh wait
we're not looking to draw a specific card
yes so 1
and after the 8th draw would be 1 - 1/52?
coral parcel
That fraction is certainly part of the calculuation, but it's not the final probability I asked about, right?
torn grail
(1 - 1/52)^9
coral parcel
Yes.
Now imagine we're drawing cards with replacement 17 times, writing down what we get on 17 separate lines of a piece of paper.
Afterwards for each card we've seen, we put a star next to the last time we saw that card.
Notice:
a) The exercise is to find the expected number of stars on the paper.
b) What we've just computed is the probablity that there's a star on line 8.
torn grail
so in this case, we're putting a star at every step
coral parcel
Only the steps where we see some card for the last time.
If some card appears multiple times, we'll only put a star the last of those times.
deep ravine
how do i convert 25 into a log with base e??
weary tiger
give me tips or advice to master graph theory (from a programmer's perspective)
small atlas
how can I prove the correctness of euclid's gcd algo using induction?
spring elk
for verifying its an identity can someone let me know if my argument is correct?:
f(A, D) = A for a unique D. This means A=emptyset and D=Not(A). Since A is an element of P(U) this can only be true if U is empty. But it is given that U is not empty therefore it does not have an identity
tribal laurel
anyone can solve C?
elder berry
for verifying its an identity can someone let me know if my argument is correct?...
I mean if you show why it means that A = \emptyset and D = A' then sure
You could approach it differently with a contradiction
we need to show $\overline{A \cup D} = A$, but also $\overline{A \cup D} \subseteq \overline{A} \not\subseteq A$ which contradicts it
vital dewBOT
peaceGiant
spring elk
I mean if you show why it means that `A = \emptyset` and `D = A'` then sure
A is empty set and D = A' because there is no other way I can get not(a union d) = a
is this not enough?
elder berry
why is there no other way to get not(a union d) = a?
you need to formally prove that
spring elk
ahh
spring elk
**peaceGiant**
how is this a contradiction? (why is not A union D a subset of not a)
ohh
no wait actually i dont see it..
how would the proof by contradiction start? its like we assume not (A union D) = A?
spring elk
why is there no other way to get `not(a union d) = a`?
im not sure how id formally prove this
elder berry
We need to check given $f(A, B) = \overline{A \cup B}$ whether $f$ has an identity element.
I'll assume the answer is no, and prove by contradiction.
\
With contradiction, you have to show that given "$f(A, B) = \overline{A \cup B}$ and $f$ has an identity element is false.
\
We are given that an identity element exists, say $D$, and that the following is true
$f(A, D) = f(D, A) = A$ or $\overline{A \cup D} = A$.
\
But if we assume this, we get a contradiction because $A \neq \overline{A \cup D}$ which I showed above.
For $A$ to be equal to $\overline{A \cup D}$, the first has to be a subset of the second, and the second has to be a subset of the first, but we know that $\overline{A \cup D} \not \subseteq A$.
vital dewBOT
peaceGiant
elder berry
im not sure how id formally prove this
so not(A union D) = A can't happen if we assume an identity element D, which means our assumption is wrong and an identity element doesn't exist (assuming non-empty U)
spring elk
thanks! This makes sense now
shut bolt
isnt the answer to this question going to be the first one since all natural numbers have to be defined in A(x)
since natural numbers are just positive integers?
coral parcel
Yeah.
shut bolt
Can the greatest common divisor of 2 integers be symmetric and antisymmetric?
spring hound
<@537482727557955597> thank you so much, there were like 3 kmap questions on my...
Glad to hear it 🙂
celest drum
Good day, I am new to the server. we started a new topic on congruences i am struggling to understand, can i post the question here?
spring hound
Can the greatest common divisor of 2 integers be symmetric and antisymmetric?
What do you mean by symmetric and antisymmetric with regard to a function with two inputs and one output?
stray reef
@celest drum you can and should post your question.
shut bolt
What do you mean by symmetric and antisymmetric with regard to a function with t...
something like this where two integers are related if they are co-prime
its definitely symmetric so its not asymmetric
spring hound
Ahh, to be both symmetric and antisymmetric, I think only items that would help make the relation reflexive are allowed, as in (a, a) (though it doesn't need to be fully reflexive, as it can leave some out).
shut bolt
if its symmetric here, doesnt that contradict antisymmetric here
since gcd of two integers can be co-prime and they dont have to be equal
spring hound
If you have some that have (a, b) with a ≠ b, it can't be both.
If there are no items or the only items are (a, b) where a = b, then it will be both.
shut bolt
so its not antisymmetric then
shut bolt
got it thank u for the clarification
spring hound
No problem.
shut bolt
one quick thought, if co-primality is not reflexive, we could say its not irreflexive either since the gcd(1,1)=1 right?
celest drum
<@1019610239147966506> you can and should post your question.
I dont understand how this is working.
it is from the topic of congruences so the equal sign is meant to represent congruent
spring hound
one quick thought, if co-primality is not reflexive, we could say its not irrefl...
Yes, that's correct.
shut bolt
thats kind of interesting how something cant be reflexive or irreflexive
spring hound
Yeah, irreflexive doesn't mean not reflexive in the logical sense of not, because "not" means "every other possibility except this".
In this case, there are lots of ways for relations to not be reflexive. For example, it can be missing only one (a, a) element and fail to be reflexive, without losing (b, b) and so forth.
Irreflexive, on the other hand, is an opposite, which isn't "every other possibility except this", it's "the one possibility that is farthest away from this" or something along those lines.
Like, on a traffic light, the opposite of red is green, but the "not" of red is either yellow or green.
@shut bolt
stray reef
I dont understand how this is working.
is it the "how" that escapes you, or the "why"?
shut bolt
Like, on a traffic light, the opposite of red is green, but the "not" of red is ...
good way to put it
celest drum
is it the "how" that escapes you, or the "why"?
The why... why do we use to the power 3. why not any other power like 2 or 4. How do i decide which power to use
stray reef
does not really matter
they went with repeated cubing but honestly repeated squaring would have worked just fine, maybe being more laborious
if you want to be fancy you could examine the representations of 333 (the exponent) in bases 2, 3 and maybe 5(?) to see if one of them has significantly more zeros than the others
celest drum
if you want to be fancy you could examine the representations of 333 (the expone...
hahaha baby steps please i am still trying to grasp what is happening here
stray reef
this is why i asked you if you wanted the how or the why
i.e. the mechanics of the steps that are happening or the overall motivation
celest drum
i guess both. The topic was introduced yesterday that was the example after going through the theory of congruences so my knowledge is a bit foggy
celest drum
i.e. the mechanics of the steps that are happening or the overall motivation
the mechanics
stray reef
okay so the how
right. so do you know some basic properties of congruence?
such as the fact that it respects addition and multiplication
namely if a = a' and b = b' (both mod m) then a+b = a'+b' (mod m) and ab = a'b' (mod m)
celest drum
namely if a = a' and b = b' (both mod m) then a+b = a'+b' (mod m) and ab = a'b' ...
yes, well i learnt that yesterday but yes i understood that
stray reef
right
then do you understand up to and including the line that says "find the remainder"?
celest drum
yes
celest drum
the 1st part i did not get is why we choose the power 3 which you explained that it doesnt really matter
I guess that is mostly what i dont get. What is happening on the righ hand side i understand. why we chose 3 thats what was the main question. If i encounter a different question like: Show that 6^321 - 6 is divisble by 123. Which power do i start with
stray reef
well you are going to compute 6^321 mod 123
you cannot really go wrong with repeated squaring
celest drum
you cannot really go wrong with repeated squaring
ok let me attempt that then get back to you give me a few minutes. Thank you so much for the help so far
shut bolt
Can I say this isnt symmetric cuz of V(1,2) and V(2,1); and this isnt asymmetric and antisymmetric cuz of V(3,7) and V(7,3) right?
spring hound
What do you mean with 3 and 7?
shut bolt
3 and 7 are integers in the relation
spring hound
Why do you say that?
shut bolt
cuz 3/7 is not related and 7/3 is not related so its symmetric
spring hound
How would you describe the relation in simpler terms than they give?
shut bolt
well V(x,y) is symmetric is V(x,y) is related and V(y,x) is related
but that cant be true because V(1,2) and V(2,1) makes it false
spring hound
No, I mean, if I were to ask you what the relation describes, what would you say?
shut bolt
the relation is if two integers can evenly divide
spring hound
No.
There are several things that can mean. They both divide each other, one divides the other but it doesn't matter which one, the element on the left divides the one on the right, the element on the right divides the one on the left.
Which one do you mean?
shut bolt
for symmetric?
spring hound
No, to describe the relation.
shut bolt
i mean this is the relation
spring hound
Yes, and what is it in simpler terms?
shut bolt
the one on the left divides evenly with the right
spring hound
OK, the left divides the right.
Another way is that it's an integer on the left and an integer multiple of the left on the right.
Now, how do 3 and 7 fit into that?
shut bolt
I used 3 and 7 to prove that the relation is not asymmetric and not antisymmetric
shut bolt
yes but x and y are defined to be any two positive integers here
they dont have to be a multiple of each other
spring hound
No, that's incorrect.
shut bolt
spring hound
The definition isn't that x ∈ ℤ⁺ and y ∈ ℤ⁺.
It's that y/x ∈ ℤ.
That's a stronger requirement than them being positive integers.
shut bolt
I mean thats what the instructions say
spring hound
They say several things.
They say both that they're positive integers and that y/x is an integer.
You can't leave part of it out.
3/7 is not an integer.
7/3 is not an integer.
(3, 7) is not in the relation.
(7, 3) is not in the relation.
shut bolt
yes what i'm saying is that both are not related in both ways
barren willow
what channel should i go to for quaternions
shut bolt
yes what i'm saying is that both are not related in both ways
if both arent related in both directions then they are symmetrical
spring hound
if both arent related in both directions then they are symmetrical
That's incorrect.
Symmetric doesn't mean that you need at least one for every pair.
It means that whenever you have one, you also have the other in a pair.
You don't fit the "whenever you have one" part with that.
You can either have (a, b) and (b, a) or neither for all a and b.
If that's true, then it's symmetric.
For example, (1, 1) being the only thing in a relation would be symmetric.
shut bolt
yes but the relation isnt necessarily symmetric for other integers
so we cant say that the relation is symmetric for all x and y
spring hound
You need to show a counterexample.
shut bolt
yes
spring hound
Where one is in the relation, but the reverse isn't.
spring hound
Yes, that's a good example.
shut bolt
ok now for asymmetric
u said i cant use (3,7) cuz they need to relate in one direction and not relate in the other right?
so in that case it is asymmetric meaning its also antisymmetric right?
spring hound
No, it's not asymmetric.
Asymmetric means if you have one way, you cannot have the other way in all cases.
(3, 7) doesn't help because it doesn't fulfill the "have one way" thing.
You need to show that, for everything in the relation, if (a, b) is in, then (b, a) isn't.
Neither of them being in is fine, because the if part is false, so the statement is true.
shut bolt
but when u say we need to have something one way, cant that one way be not related, and the other way just cant be related also
spring hound
No, for if X then Y to be false, you need X to be true and Y to be false.
It's like an insurance thing.
If your house burns down, then I pay to rebuild it.
If your house doesn't burn down, I'm fulfilling my end.
If I pay to rebuild it, I'm fulfilling my end.
celest drum
you cannot really go wrong with repeated squaring
I hope you able to read past the handwriting 😅 . i tried to the power 2 then also to the power 4 is this correct?
spring hound
The only way for me to not hold up my end would be if your house burns down and I don't pay to rebuild it.
stray reef
,calc 6^2 mod 123
6^4 mod 123
6^8 mod 123
6^16 mod 123
6^32 mod 123
spring hound
The only way for an if then to be false is if the if part is true and the then part is false.
shut bolt
I just cant think of any integers that relate in one direction and also relate the other direction
vital dewBOT
Results:
36
66
51
18
0
There is one pair.
shut bolt
are we assuming x and y are different integers?
spring hound
are we assuming x and y are different integers?
Does the problem require that?
stray reef
@shut bolt @spring hound could you perhaps take your convo to #proofs?
er
that one
spring hound
OK.
stray reef
it's a little hard to have 2 convos in the same channel
,w (6^4, 6^8, 6^16, 6^32, 6^64, 6^128, 6^256) mod 123
vital dewBOT
stray reef
hope this works
okay
let's check against yours
@celest drum ok your arithmetic checks out
celest drum
if you want to be fancy you could examine the representations of 333 (the expone...
Can you explain what you meant by this
stray reef
do you mean semantics or intention
celest drum
do you mean semantics or intention
Semantics. How would i actually do it to make achieve the same thing but faster. repeated squaring works but it is pretty long
stray reef
right so ok
let me try to demonstrate on 333
idk if itll be a good example
,w 333 in base 2
vital dewBOT
stray reef
,w 333 in base 3
vital dewBOT
stray reef
in binary, 333 is represented as 2^8 + 2^6 + 2^3 + 2^2 + 2^0
meaning that to compute a^333 mod m youd need to multiply 5 things together at the end
i.e. a^(2^8), a^(2^6) etc.
while in ternary 333 is represented as 3^5 + 3^4 + 3^2
which means only 3 things need to be multiplied at the end
so it's a tiny bit of cost savings
celest drum
so it's a tiny bit of cost savings
Oh i see. very well let me work on different examples then. Again thank you for your time you really helped me a lot
shut bolt
def need some verification, but given these conditions, I think its still possible for both sides to co-exist aka be true at the same time right?
since co-primality doesnt have to be two prime numbers, it could be a prime and a non prime number that can still be co-prime
lusty garnet
hey all, i been working on this proof for hours and can't figure it out.. any one wants to give it a shot? Must be proof by induction.
Without using the Tree theorem (which we will see in the next couple of days), prove that if a
graph G is connected and |E(G)|≤|V (G)|−1, then G is acyclic.
(G is acyclic iff G has no cycles).
gritty crescent
Please don't spam your question across channels. Keep it to #proofs-and-logic now.
midnight mural
Alright, I am sorry.
elder berry
hey all, i been working on this proof for hours and can't figure it out.. any on...
I think a proof by contradiction would be enough.
If I'm not mistaken, something like: ||If a cycle of length k <= |V| exists, then the cycle requires k edges. ||
||But then all other vertices that are not a part of that cycle (in total (|V|-k) vertices) also require at least one outgoing edge towards another vertex to be connected (since if a vertex has no outgoing edges, the graph can't be connected)||
||Thus in total you must have at least* |E| = k + (|V|-k) = |V| edges which is the wanted contradiction (we had assumed |E| < |V|.||
mighty ivy
,tex \emph{How can i approach this problem?:} \newline
A = {1,2,3, ..., 8} \newline
\emph{How many different surjections are there from A to A that always send even numbers to an odd number?}
vital dewBOT
Magnus
mighty ivy
,tex \emph{Would this approach be correct?:} \newline 4\cdot4\cdot3\cdot3\cdot2\cdot2\cdot1\cdot1
vital dewBOT
Magnus
Compile Error! Click the reaction for more information.
(You may edit your message to recompile.)
gritty crescent
,tex \emph{Would this approach be correct?:} \newline 4\cdot4\cdot3\cdot3\cdot2\...
Looks good to me
Although you should try to justify how you reached that exact number
I would recommend graphing the function f(x)=2x^4-x^2-2. Check the subset for which the graph lies below (or on) the x-axis.
Maybe it could be found out directly as well, I'd just be too lazy to do that
gentle bronze
Maybe it could be found out directly as well, I'd just be too lazy to do that
i tried solving the inequality
but
would it take too long to solve the quartic?
gritty crescent
Yeah, I think you can avoid it altogether
I don't think the point of this exercise is to be able to solve quadratic inequalities anyway
gentle bronze
ok ill have a go
gentle bronze
would u still draw a graph here?
balmy dune
guys my answer is 0.005 is it correct?
fathom void
can someone help with this
I can't see why this is also strictly increasing and strictly decreasing.
f(x) | y
1 1
2 1
3 1
4 1
I can see f(x)≤y and also f(x)≥y, so that should only satisfy increasing and decreasing. But I don't understand strictly meaning > or <
am I looking at it wrong?
elder berry
f(x) | y
1 1
2 1
3 1
4 1
I can see f(x)≤y and also f(x...
By f(x): 1, 2, 3, 4 do you mean the values that x can take?
if that's the case look at the domain of the function again, f: {1} -> {1}
gritty crescent
would u still draw a graph here?
This time the expression can be worked with directly: x(x^2-sqrt(2))<=0 or x(x+sqrt(sqrt(2)))(x-sqrt(sqrt(2)))<=0. You can check for which intervals you have a negative sign for the expression
There's one thing you overlooked 👀
What is x supposed to be?
Oop my bad
I processed your answer incorrectly
It's correct 
fathom void
if that's the case look at the domain of the function again, `f: {1} -> {1}`
thanks. Either way, I don't see how it can be strictly increasing or decreasing
1 is not > 1
and 1 is not < 1
elder berry
the definition of increasing and decreasing is whenever you have two inputs x, y such that x < y,, then the for the values of the function it should be true that f(x) < f(y)
however, since you are working on a domain with only one input, that first part of the implication is false, there is no other element y you can choose that is going to be greater than one
so this would be an example of a vacuous truth (I think!)
fathom void
So by definition of conditionals if the premise is false then the statement is true?
elder berry
yep, if x<y then f(x)<f(y) would be of form: F -> F which is always true
fathom void
Thank you!!
shut bolt
yall think this is a contradiction based on these conditions? I think it isnt cuz other integers outside the subset S could work for A(x) right?
gentle bronze
It's correct <:catthumbsup:614540188747563008>
ms says inf A does not exists
rip
how
gritty crescent
Oh, I didn't notice closely before
But for x sufficiently large, x^3>\sqrt(2)x
For negative x, the inequality flips
Notice, for instance, that for $x=-10$, [x^3-\sqrt{2}x=-1000+10\sqrt{2}<0]
gentle bronze
?
gritty crescent
Why is TeXit down now
Anyway
The point is that the function f(x)=x^3-sqrt(2)x is negative on (-∞,sqrt(sqrt(2)))
Which means you don't really have an infimum
gentle bronze
icl im still confused why inf A isnt -sqrtsqrt 2
gritty crescent
icl im still confused why inf A isnt -sqrtsqrt 2
Note that the function is also negative in the region I marked
Not just the yellow part you highlighted
gentle bronze
yh
gritty crescent
And over here we don't really have a lower bound
It just keeps sinking to negative infinity
It's positive on (sqrt(sqrt(2)),+∞)
Note that the graph is above the x-axis on that interval
gritty crescent
How?
gritty crescent
Well sure, here it is below the x axis
But after that it is strictly positive
Which is why it won't be a part of our set
And we do get a sup
gritty crescent
gritty crescent
gentle bronze
<:KEK:586240877358350341>
so could we say this function is 'bounded above'?
gritty crescent
It is not
The point is that we were only interested in those values of x for which f(x) was non-positive
That subset is bounded above, yes
But the function itself is not, as you can see from the graph
gentle bronze
ight cool that makes sense now cheers
lastly i have this problem
my max is correct
but everything else is wrong
gentle bronze
What is sin(π/2)?
1
gritty crescent
Why did you put sup(f(x)) as π/2 then?
gentle bronze
Why did you put sup(f(x)) as π/2 then?
i thought the interval notation was between pi/2 and -pi/2
gritty crescent
That's the domain, yes, but the sup/inf/min/max are being sought for the function f
Which refers to the range of f with the given domain
gentle bronze
Which refers to the range of f with the given domain
i see
gritty crescent
This would be too much filler if they only wanted to ask the details for (-π/2,π/2) lol
Check the function definition: they defined f to be sin(x) on all points but π/4
What is sin(π/4)?
gritty crescent
You have your answer 
gentle bronze
You have your answer <:catshrug:563818735085944843>
yh that makes a lot of sense
gotta be careful with these questions
thanks
gritty crescent
No worries, goodluck!
solar flame
can anyone help please
im looking to finds solutions of predicates turned into english
ornate creek
The Problem is: Use the Well Ordering Principle to prove that every finite nonempty set of real numbers has a minimum element.
I came across this solution but I am having trouble understanding what is meant by {x₀}
spring elk
counter example. Can i say for x {1, 2, 3}, consider p(x) to be x is an even number and q(x) to be x is an odd number. the first statement will always be true but the second statement can be false if we take x=1 for p(x) and x=2 for q(x)
spring elk
A^2 means that R is a subset of (AxA)x(AxA) and A is an element of P(R) where P is a powerset?
but if thats the case this wouldnt make sense. i cant add sets
gritty crescent
Where do you have to add sets?
spring elk
is what I said about R right?
gritty crescent
The relation R is defined in a way such that two pairs of numbers in A are related iff they satisfy the given inequalities
Yes, that is correct
gritty crescent
Are you conflating $R$ and $\bR$ here?
vital dewBOT
Chaigenvalue
gritty crescent
(The first symbol refers to the relation on A, the latter refers to the set of real numbers)
spring elk
no. A is a subset of real numbers right? so A would an element of a powerset of realnumbers
gritty crescent
Yes, that is correct
spring elk
so isnt a subset of the relation what i said above?
gritty crescent
so R is sth like ({1}, {1}) R ({1}, {1})
No, this isn't right
spring elk
(a, b) is an element of AxA right?
spring elk
but A is an element of a powerset
ohh so since a is an element of A it would get the value...
gritty crescent
Yes
spring elk
alright i see now. Im gonna attempt to solve it now again.Thanks
gritty crescent
spring elk
for asymmetric would I need to show (a, b) (b,a) implies a=b?
if i take (2, 3) R (3, 2) this would satisfy both conditions but it isnt asymetric right?
wait no id need (a, b) R (c, d) and (c,d)R(a,b) and id need to show that (a, b) = (c, d)
tho idk how to do that
sour scarab
for asymmetric would I need to show (a, b) (b,a) implies a=b?
this one is correct
sour scarab
generally speaking, when proving something asymmetric, (a,b),(b,a) implies a=b yes
spring elk
but for the exercise above?
sour scarab
which exercise? sorry
sour scarab
I'm assuming you're tackling part b, which in that case you need only draw a diagram
spring elk
oh sorry for being unclear. I am still doing part a
need to prove its poset
so i need to show its asymmetric
anyways what I did is :
take (a, b) R (c, d) and (c, d) R (a, b)
(a, b) R (c, d) is true if a-b <= c-d
(c,d)R(a,b) is true if c-d<=a-b
therefore a-b=c-d which means (a,b)=(c,d)
sour scarab
that's perfect, yes. sorry, after reviewing your previous comment and the exercise itself that's an excellent proof
now you just need to prove that the relation is transitive and you're fine, assuming you haven't already. use the same line of reasoning by considering pairs as elements rather than just a,b etc
spring elk
thanks!
hidden sparrow
Can you place infinitely many queens on an infinite chessboard so that each queen threatens exactly six others?
The answer is 'yes' when six is replaced with five (and anything below), but I'm unsure about this case
shut bolt
i know it cant be the last one cuz 1 isnt a prime factor, so how would I approach the remaining two choices
hidden sparrow
Can you place infinitely many queens on an infinite chessboard so that each quee...
<@&286206848099549185>
reef dirge
how does one approach B?
sudden minnow
do you have an idea whether it is true or false?
reef dirge
pretty sure is False
sudden minnow
yeah
so you want to find a counterexample
just wondering what kind of hint I could give that wouldnt reveal an answer outright
basically, you want to think in terms of prime factors
where a has a lot of one factor, b has a lot of another factor
reef dirge
i already know a counter example but i feel like i have to prove with contradiction or contrapositive or something
sudden minnow
uh
if you want to show a conditional p -> q is false
suffices to show an example where both ~~not p and q ~~ p and not q holds
in fact, a counterexample is how you are supposed to prove it is false
so you are confused
mb
p and not q
reef dirge
i see
sudden minnow
if you know how to work with quantifiers, basically (b) is a statement about 4-tuples of natural numbers
,,\forall (a,b,m,n) \in \mathbb{N}^4 P(a,b,m,n) \implies Q(a,b,m,n)
vital dewBOT
lems
sudden minnow
the converse would be equivalent to
,,\exists (a,b,m,n) \in \mathbb{N}^4 \neg(P(a,b,m,n) \implies Q(a,b,m,n))
vital dewBOT
lems
sudden minnow
if you know $\neg \exists \neg$ is equivalent to $\forall$
vital dewBOT
lems
reef dirge
is there a way to prove that the converse is true?
if the converse is true it means the original statement is false right?
sudden minnow
wait mb
I'm using converse incorrectly
I mean the negation
and yes
if the negation is true the original statement is false
sudden minnow
**lems**
and the negation is this
how do you show this is true
of course, by finding a 4-tuple that satisfies this
aka a counterexample
sudden minnow
yeah, so that is sufficient
to be super clear, if someone makes a statement such as "all apples are red"
to show this is false it suffices to exhibit an apple that is indeed not red
sudden minnow
the problem is that expression could be divisible by ab
to see a concrete example, write this out in terms of your counterexample
like 3 = 2*1 + 1 and 8 = 6*1 + 2
reef dirge
Ok thanks
spare axle
please help me
warm ferry
cloud compass
@weary tiger how are U and R defined ?
ember obsidian
@warm ferry yes
spark silo
im going through past exams but they dont give solutions :/ what are the T/F values for these? (and how)
coral parcel
Can you show a concrete Hamiltonian cycle in (c)?
spark silo
hamiltonian means it just reaches every vertex, right? unless my understand is incorrect
coral parcel
A graph is "Hamiltonian" if it has a Hamiltonian cycle. What you show is just a Hamiltonian path -- it has ends that don't connect to anything.
spark silo
ah so it would be a hamiltonian cycle if it could do this illegal move and it ended on htat adjacent vertice?
coral parcel
Yeah.
dense granite
Can someone describe a graph with radius 4 and diameter 6
I am trying to generalize to graphs with certain kinds of radii and diameters but cannot think of a such a graph to get started
half dock
Can someone describe a graph with radius 4 and diameter 6
The circle with a radius of 4, has a diameter of 8
Can you explicitly state what you don't understand
hazy sand
Can a graph be labelled as both irreflexive and complete, or do i need to refer to it with a different term
An example may be "is not equal to" over the set of reals.
umbral blade
Is primality testing NP hard true? Or is it open?
brave rock
Is primality testing NP hard true? Or is it open?
You might want to see this article: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/primality_journal.pdf
This is known as the AKS primality test.
hollow nacelle
,,\exists (a,b,m,n) \in \mathbb{N}^4 \neg(P(a,b,m,n) \implies Q(a,b,m,n))
vital dewBOT
blank.....
mighty ivy
Minimal Elements: {6,7}
Maximal Elements: {1,2,4,7}
Minima = Empty Set
Maxima = Empty Set
mighty ivy
Minimal Elements: {6,7}
Maximal Elements: {1,2,4,7}
Minima = Empty Set
Maxima = ...
Is this correct for this hassediagram?
stray reef
seems so!
cold mesa
hollow tartan
how would I start proving this
elder berry
how would I start proving this
You could show it with simple algebra, noting that n Choose m = n!/[(m!)(n-m)!] and using that for all binomial coefficients, or you could give a combinatorial proof showing why both sides count the same thing with different approaches
if there is no restriction on the method you need to use, go with the algebraic way
(even though the combinatorial one is briefer)
indigo ferry
combinatorial one is more fun to write imo
hollow tartan
combinatorial one is more fun to write imo
you are a mad man then lol
indigo ferry
you are a mad man then lol
well it's more fun than swapping around n's and m's
indigo ferry
did you get the algebraic one?
indigo ferry
For the algebraic proof, expand one side into factorial form
vital dewBOT
Franz
hollow tartan
yea
indigo ferry
Think about how the right hand side of the equation looks like, in expanded form
indigo ferry
I just mean factorials, like this one
hollow tartan
???
hollow tartan
Like this????
indigo ferry
uhhh
hollow tartan
I'm trying my best
indigo ferry
._.
indigo ferry
You can't write n! 3 times like that
1 sec I have to google how to latex the combination thing
hollow tartan
oh ik how its like matrix n\k or something like that
$\begin{pmatrix} n \ k \end{pmatrix}$
vital dewBOT
arrow891
indigo ferry
Like this????
btw you're required to add parentheses for the factorial, so the first line isn't notationally correct
2nd line is fine
indigo ferry
3rd line, could you explain what you did
hollow tartan
I broke up the fraction
indigo ferry
Like this????
I mean you can't write $\frac{n!}{n-m!m-k!k!}$ for $\frac{n!}{(n-m)!(m-k)!k!}$
vital dewBOT
Franz
indigo ferry
arrow math? o_o
hollow tartan
yea
hollow tartan
but what do i do after the second line
indigo ferry
first I think we really should talk about the 3rd line here
indigo ferry
So for proving equalities, you can try simplifying from both sides, and see if you can arrive at the same formula
hollow tartan
ur missing some \ i think
indigo ferry
You have ${n \choose m}{m \choose k} = \frac{n!}{(n-m)!(m-k)!k!}$
Try doing the same for ${n \choose k}{n-k \choose m-k}
vital dewBOT
Franz
Compile Error! Click the reaction for more information.
(You may edit your message to recompile.)
hollow tartan
how would one do that for n-k and m-k
indigo ferry
You know what ${a \choose b}$ is, so you plug in a = n - k and b = m - k
vital dewBOT
Franz
hollow tartan
indigo ferry
c'mon just expand the combination thing
hollow tartan
idk how to expand something with 3 letters
my professor didn't say how
wikihow doesn't teach it nor does youtube
quora can't even help me
and u best believe wikipedia didn't help at all
indigo ferry
you assume both letters are like one single letter
hollow tartan
heh
indigo ferry
You can do that!
indigo ferry
You're basically expanding two letters as usual and saying "oh, but this one letter I actually mean these two letters"
hollow tartan
so like n is n and m is both m and k?
indigo ferry
n is n-k and m is m-k
indigo ferry
it's not a theorem
you just take ${n \choose m}$, then substitute n-k for n and m-k for m
vital dewBOT
Franz
indigo ferry
okay let's rewind a bit, do you know what you're doing with ${n \choose m}$?
vital dewBOT
Franz
indigo ferry
like what it means
hollow tartan
yea
gray sun
How do you prove that two sets are equal?
indigo ferry
How do you prove that two sets are equal?
Two sets are equal if and only if they both contain the same elements
indigo ferry
How do you prove that two sets are equal?
The type of proof defends on the problem,
For instance you could suppose there exists an element unique to one of the sets and build a contradiction
Or, prove A is a subset of B, and B is a subset of A
gray sun
Two sets are equal if and only if they both contain the same elements
A ×(B ∪C) = (A ×B) ∪(A ×C)
These would equal right?
The first one would be like for example:
(A1,B1),(A1,C1)
And the second part would be:
(A1,B1), (A1,C1)
So they would be equal?
indigo ferry
A ×(B ∪C) = (A ×B) ∪(A ×C)
These would equal right?
The first one would be like...
okay these are clearly equal, proof tho....
gray sun
okay these are clearly equal, proof tho....
yeah so for proof i guess I would just do what?
indigo ferry
actually I'm not sure how to formally write a proof for this
I mean I could come up with some notational proof but that's probably not what your professor's expecting
@hollow tartan
gray sun
actually I'm not sure how to formally write a proof for this
I just need justification, so i could probably just go with an example or something right?>
indigo ferry
I just need justification, so i could probably just go with an example or someth...
I think the method you descibed would suffice
gray sun
I think the method you descibed would suffice
👍
indigo ferry
👍
wait I got it, If you want to prove this rigorously all you have to show (sentence by sentence) is
$x \in A × (B ∪C) \Rightarrow x \in (A ×B) ∪ (A ×C)$ and $x \in (A ×B) ∪ (A ×C) \Rightarrow x \in A × (B ∪C)$
vital dewBOT
Franz
gray sun
wait I got it, If you want to prove this rigorously all you have to show (senten...
ok
lemme look at my notes
gray sun
wait I got it, If you want to prove this rigorously all you have to show (senten...
Ok i think i understand now, tysm ur awesome
gray sun
Is the following relation reflexive?
R1 = {(a, b), (a, c), (a, a), (b, a), (c, a)}
And
A = {a,b,c,d}
its not right? because it's missing (b,b) and (c,c)?
brave rock
Indeed it isn't, for the precise reason you give
primal shore
yoo, i got an induction problem in a quiz can anyone help me?
id appreciate it a lot
primal shore
<@&286206848099549185>
spark silo
how do you find the maximum antichain for this?
little prism
just a bit of trial and error is enough
(and by dilworths theorem its easy to check whether thats the largest size. although you only need the easy direction, so you dont even need the full theorem)
spark silo
i dont actually know what antichain is so what is the tiral and error process
little prism
step 1: look up the definition of antichain
how do you expect to find something without knowing what it is
spark silo
mm yea i was looking at it in my uni notes and they never really explained it
so woukd {1, 2, 5, 7} be an antichain?
{2, 3, 5, 8, 9} is maximum antichain?
small atlas
Can someone help me solve this?
This is what I tried I dont know how to take this forward from here
little prism
mm yea i was looking at it in my uni notes and they never really explained it
s...
{1,2,5,7} is not an antichain because 1 < 7
{2,3,5,8,9} is not an antichain because 5 < 8
those diagrams are transitive. 5<6 and 6<8 implies 5<8
spark silo
those diagrams are transitive. 5<6 and 6<8 implies 5<8
so are you suggesting the maximum antichain would be {2, 3, 4, 5}
spark silo
hmmm, alright ill put the full question here because the students answer is different - most people are saying the max antichain is of size 5 (they could be incorrect), which makes it a bit more confusing, unless there's something i missed
little prism
there is a very obvious partition into 4 chains
and {2,3,4,6,7} is not an antichain cause 3<7
ah ok you drew the diagram wrong
spark silo
maybe that graph i sent was wrong
little prism
clearly 3 is not comparable to 7
spark silo
yeah look that was also taken from a different students notes i was trying to figure out. but then from this graph, a
max antichain could be {2, 3, 4, 5, 6} ?
little prism
5<6
spark silo
but 5 isnt connected to 6 is it
little prism
Should be