But notice this double counts f(n-7)
#discrete-math
last sigil
last sigil
Yes
f(n) = Number of solutions for 2x + 5y = n, n is some integer
So now we've derived it and you can solve
spare jolt
Yep, I see
last sigil
Alright cya
spare jolt
Aight thanks heaps!
halcyon ledge
its nested loops inside nested loops inside nested loops inside nested loops inside nested loops inside nested loops
and a little bit of addition
whole shard
I'm learning product rule, then should it be $k=n^{m}$
vital dewBOT
Yo Mama:
whole shard
since n kept on repeating?
halcyon ledge
best way to deal with something like that if you don't understand it, is to use pen and paper tbh
take a simple loop (no more than three or so)
halcyon ledge
let $n_1 = 2, n_2 = 3, n_3 = 1 \text{ and } k = 0$
$\text{for } i_1 := 1 \text{ to } n_1 \
\text{ for } i_2 := 1 \text{ to } n_2 \
\text{ for } i_3 := 1 \text{ to } n_3 \
\text{ } k = k+1
$
😦
vital dewBOT
deekaan:
vital dewBOT
deekaan:
halcyon ledge
because you run the $n_1$ loop $n_1$ times and the $n_2$ loop $n_2$ times and the $n_3$ loop $n_3$ times
vital dewBOT
deekaan:
whole shard
@halcyon ledge thank you
faint narwhal
It doesn't
It just happens to be that way because you choose 2 as your mod
I.e. consider x = 0 (mod 3) and x = 1 (mod 6)
This has no solutions
Yeah
Vaguely the same idea, but it's not even/odd
I mean, you only tried your idea on one case
whole shard
any feedback?
pale epoch
it's wrong
weary tiger
isn't this just a multiplication principle problem?
whole shard
im doing counting examples
pale epoch
i mean now it's correct
whole shard
but idk how to make it such that one is math, and one is cs
weary tiger
well, yes, it's right, just apply multiplication principle
pale epoch
at least probably, the question is asked badly
but you shouldn't be guessing solutions
whole shard
multiplication principle = product rule?
weary tiger
that might be another name for it yea
whole shard
thanks! i loked it up, they say if the keywords "and the(n)" comes up i just use the multiplication
weary tiger
you need to pick a math major
for that math major, any of the cs majors can be paired with that one
repeat that 18 times for each math major
pale epoch
you are counting the tuples (x,y) where x is a number between 1 and 18 and y is a number between 1 and 325
for the first coordinate you have 18 choices
and once you made that choice, you still have 325 choices for the second coordinate
so for every fixed first choice, you have 325 second choices
if that makes sense 🤷
pale epoch
(this question also assumes that math and computer science people are disjoint)
whole shard
on this one im assuming if there were only math majors, there are 18 ways. so I just added those values
pale epoch
i dont think i get your argument, but the answer is correct
whole shard
like there are only 18 people to choose from, thats 18 ways
but now u have 325+18 people
weary tiger
it's just addition principle
pale epoch
ok, that makes sense
weary tiger
if I'm reading the question correctly then that's not right
is the committee size 50?
whole shard
my reason is if there's 2 ways for 1 state, then there's 100 ways for 50 states.
Yes
weary tiger
ok, there are definitely way more ways than 100 then
vital dewBOT
Yo Mama:
weary tiger
did you write this question yourself?
weary tiger
why do you think 2^50?
whole shard
$50^2$
vital dewBOT
Yo Mama:
whole shard
no 2^50 is too big.
weary tiger
50^2 is way too small
whole shard
I cant think of anything else
weary tiger
the numbers involved in this question are like, way too big to imagine in your head
so "seems too small or too big" is not very useful
I can pick one of three things from state one, then one of three things from state two, and so on, until state 50
what does that sound like?
whole shard
sounds like (3) (50)
weary tiger
3*50?
stray reef
sounds like adding fifty copies of 3?
stray reef
what if it was just two states? that logic would've led you to only 4 possible committees and not 9
whole shard
3 states
stray reef
ok first off
we have three choices and not two
governor, senator 1, senator 2
and second
there is nothing forbidding a committee consisting of a governor from one state and a senator from another
whole shard
wait i think i got his question
3^50
i have 3 ways per state
now I just need to multiply it by how many states
am I close?
weary tiger
aren't you done?
whole shard
oh so its okay to leave it as is?
stray reef
no obviously you're expected to know the value of 3^50 by heart /s
sour arrow
@neon thorn
I don't follow what Ann was saying earlier. Line 2 to line 3 was replacing 5 with -1, which is true in mod 6
C(5,3) (1/6)³ (5/6)²
Is the probability that you roll a specific number 3 times
But you don't want a specific number - any of the 5 numbers will do. So there's 5 ways to accomplish this.
Oops I mixed up the number of sides and the number of dice for a sec haha
You're correct
I think you tried to divide by 6^5 in order to divide by the total number of cases.
That would be reasonable if the numerator counted a number of cases, but it doesn't, the numerator is already a probability.
atomic steeple
i know not
stray reef
what's giving you trouble here
sour arrow
It's worth asking first - do you understand the general layout of an induction argument?
jaunty carbon
Are all finite groups cyclic?
weary tiger
no, maybe you are thinking of finitely generated
stray reef
S3 is not cyclic
stray reef
why me
hnng this is not immediately obvious to me
don't ping individual ppl randomly
last timber
@balmy jackal as i remember Knuth derived this in his art of computer programming
vol.1
look there
whole shard
okay I realized something, its better to watch a video rather than reading a chapter of the book
spark crypt
Why?
whole shard
i just found a playlist on youtube and watching previous topics was easily explained
coral totem
Some of that might be because you already had a slight understanding from the reading
whole shard
good point
pale epoch
how is x always greater or equal than x^2
or a constant multiple of x
but g(x) = x^2 and C*x*f(x) = Cx
with your examples
and how is $x^2 \leq Cx$
vital dewBOT
Lochverstärker:
bitter moss
0! Is 1
near prawn
whole shard
ok i get it now
lyric pumice
@balmy jackal I believe that a straightforward algebraic proof is quite involved. You might need to apply various smaller identities along with telescoping.
stray reef
all of these are wrong
stray reef
for (a): what happens if n=3?
for (b): in constructing a function fitting the requirement, two of the values are fixed, while the other n-2 are free to choose, with 2 options for each
for (c): assigning 1 to exactly one number means sending everything else to zero, so your function is completely determined by which integer between 1 and n-1 it sends to 1 (and also whether it sends n itself to 1 or to 0)
whole shard
For (a) it looks like its 2 ways, for every element in the first set
stray reef
no
the number of ONE-TO-ONE functions from {1, 2, ..., n} to {0,1} is 2 if n=1 or n=2, and ZERO if n ≥ 3.
a function from {1,2,3} to {0,1} is never one to one.
whole shard
AH I remember now
Thank you
so basically, only 2
@stray reef for (b) you mentioned that (n-2), does "2" mean 2 elements which are 1 and n?
stray reef
yes
mellow girder
Hi guys, heres my question, its only part c im stuck on
my guess is that this is impossible right? because 10>8
and it says there must only be 8 questions
pale epoch
is the question on strong induction also a question on induction?
mellow girder
btw this topic is on the pigeonhole principle
yeah this question is annoying.....
is there a theorem related to the pigeon hole principle that allows this?
mellow girder
like allows the question part c to be true
that its possible
im guessing not, my answer will then be "this is a trick question" ig
halcyon ledge
well you could combine questions
so you have a graph question thats proven using induction
so you have 2 questions in 1
mellow girder
thats true
um for this quesiton
is the first question, n?
the number of different rooted trees is n? the number of vertices in G
and for the second question, the answer is no? its not a tree anymore because its not connected
actually no, the edge removed can be a leaf so its stil a tree i gues
wait no, it wouldnt be a tree because G' has the same number of vertices, but one less edge so its not connected , theres an isolated vertice
hearty stag
a doesnt ask for an actual value I think'
mellow girder
i understand that, i think its n
where |V| =n
the number of distinct rooted trees is just the number of vertices
by the definiton of a rooted tree
whole shard
@mellow girder what topic is this? Trees?
mellow girder
yes
whole shard
Hello, is there anyway I can distinguish, whether the problem have to solved by (product/sum/substract/divide) and (counting/permutation/repetition)?
mellow girder
it depends on the context
whole shard
Yes, I'm just trying to find a way because I'm doing some exercises and I dont know which one to use
Like for this example
C(12,8) x C(12,4) or P(12,8) x P(12,4).
Or I do 2^12..
its really confusing
whole shard
yes because it doesnt want women to be partnered with another women.
if order matters I need to use combination
sour arrow
If we swap two men, or two women, that counts as a different "way" to order everybody. So, we say that order matters, and would start thinking permutations
This question is an exception though, lol. You need a good method to count first
hasty glade
$$a \equiv b \quad mod(n) \rightarrow |a| \equiv |b| \quad mod(n)$$
vital dewBOT
AfterJack:
hasty glade
Is this true ?
clever patrol
if the domain of discourse is positive integers, this predicate would be false right? since y=-1 is a solution?
clever patrol
the predicate would be false right? since domain of discourse is positive integers
clever patrol
ye
halcyon ledge
2 = 0 + 2 and 0 = 2 * 0
halcyon ledge
looks like it
clever patrol
ty dud
halcyon ledge
no worries
hasty glade
Two distinct integers r and s tales that 0 ≤ r ≤ n - 1 and 0 ≤ s ≤ n - 1 are not
congruent n module, because they cannot differ by a multiple of n. Therefore, everything
number is congruent n module, with a single element of the set
Someonle ?
I translated that sorry if there are grammar mistakes
I understood sorry
sour arrow
@whole shard
The trick is this:
First, order the men. There's 8! ways to do this.
Then, there's 9 "slots" for the women to go between the men. Choose the order you'll place the women (5!) and choose which slots they'll go in (5C9)
I think this is a way to get a unique order, and it's easy to count the number of ways to do this. 8!5!(5C9)
whole shard
Permutation = ordered, and Combination = no ordered right?
I thought I would use permutation because men1,women1 is the same as women1,men1
is not the same*****
sour arrow
nCr is the number of ways to pick r objects from a pool of n objects where we ignore the order they're picked.
nPr is the number of ways to pick r objects from a pool of n objects, where the order you pick them is a different "way of picking"
whole shard
@sour arrow so if I break down ur answer that means (5C9) is the number of ways to pick the position for women
shouldnt it just be 8!(5C9)?
because I already used the women in (5C9)
sour arrow
5C9 is the number of ways to pick which positions get a woman. But, it doesn't say anything about which women go to which positions
In my mind, I put the women in a row (5!), then put them in that order into their positions (5C9)
whole shard
Because I see the problem ask the possibilities of losing and winning
should it have been +?
13C5 + 13C8
weary tiger
For c would it be correct to say that it contains no elements?
sour arrow
@whole shard
Make sure you identify what it is that you're counting
I'm choosing 5 games to be wins. There's 13C5 ways to do that.
Note that when I've done this, I'm finished. The games I didn't choose are the losses
.
Alternatively, you could choose 8 games to be losses. That would be 13C8 which is the same as 13C5
white sundial
How do I solve this problem?
analog sonnet
There are a number of algorithms to calculate the minimum weighted spanning tree, pick your favorite one I'd say
fathom warren
I need helop
now i consider the case as 2(x_1+x_2+x_3+x_4+x_5+x_6)=50
but now i have x_i
is x_i greater than or equal what ?
0 or 1
@analog sonnet
analog sonnet
sounds like stars and bars to me
clever patrol
What's the formula to change decimal into excess form representation and vice versa? if I'm given Decimal value, number of bits and the bias?
I think it's decimal value+2^(n-1) where n=number of bits, but where does the bias come into play? thank you. Below is the type of question i'm asked
halcyon ledge
a bias shifts the value of the bitstring by a certain amount
so say you have a 4 bit string 0101
normally that would be 5
but now we introduce a bias of -3
so it's actually 5 - 3 = 2
the ieee standard uses a bias in it's exponent 🤔
clever patrol
thanks, so 0101 would be 2 if the bias is 3?
halcyon ledge
yes
clever patrol
ahh ok ty man 😄
halcyon ledge
yes
clever patrol
alright cheers 😄
bitter moss
does anyone know a good book about discrete maths
on the larger side
need help wit this shit 😒
bitter moss
combinatorics, partitions
halcyon ledge
Introductory Combinatorics by Richard Brualdi
its pretty solid and has a lot of exercises
bitter moss
i appreciate it 🙂
vivid kindle
is there an obvious reason why the longest distance from 4->6 is 4 (4->6) here and not 5 (4->3->0->5->6)? Is it possible that the vertices must be ordered in some way for the paths to be considered?
reef thistle
yeah, probably a typo
jaunty carbon
If I have a polynomial: x^6 + x + 1. How can I then prove that it is irreducible over the ring F2[x]
jaunty carbon
ow damn, I meant a ring
stray reef
you could probably go through all the irreducible polynomials in F2[x] up to degree 3 and check that yours isn't divisible by any of them
jaunty carbon
Tnx
vivid kindle
@last timber I'm not sure if they miswrote because other distances have a similar issue, e.g. 3->5 has a maximum distance of 2 (3->5) in the table, but a distance of 7 seems possible with 3->0->5
jaunty carbon
In my book they tried to reduce the polynomial x^6+x+1 to a polynomial of degree 4 and one of degree 2 and then two polynomials of degree 3. Reducing this polynomial like this, didn't work so that proved the polynomial was irreducible. But why didn't they try reducing it to a polynomial of degree 1 and one of degree 5
vivid kindle
same with 3->6, the table lists 6 (3->4->6) but 9 seems possible (3->0->5->6)
vivid kindle
yeah, n should be pretty small here hopefully 🙂 mostly just trying to reproduce the results in this book because it's reused in another paper that I'm trying to implement
last timber
i have not worked with longest path problem yet, but for shortest path problem dijkstra is the best if no negative weighted edges occur
for negative - ford algo
halcyon ledge
its a greedy algorithm
it just picks the path that's immediately the most expensive
it doesn't consider overall results
or I guess it picks the most expensive node everytime would be a better way to explain it🤔
last timber
its a greedy algorithm
and it has n^2 complexity
in some implementations even nlogn
(i omitted big-oh notation)
coral totem
If it’s a well planned book, it might say something like “it might seem like we could just pick the largest valued path from each node, giving us these results”
And then later on say, but notice these counter examples, which mean we need to find a more sophisticated algorithm to yield the correct solution
last timber
btw, i suppose longest path problem can be solved by ford (or even dijkstra algo since it "works" for negative weighted graphs) for graph with opposite-signed vertices
so it would be still in O(n^2) range
vivid kindle
The book uses Floyd-Warshall so that's what I've been using to try to reproduce their results, but I'm getting different results for those paths (4->6, 3->5, 3->6)
halcyon ledge
you can run through it
it just picks the most expensive node every time
if it has visited a path already it will pick a new one
but only then
vivid kindle
I thought floyd-warshall finds all pairs shortest paths, e.g. determining the overall shortest path between a pair
I thought it would check all possible paths based on the description:
The Floyd–Warshall algorithm compares all possible paths through the graph between each pair of vertices.
halcyon ledge
it does
but the algorithm here isn't that smart
it doesn't do comparisons it just runs through the graph looking for the most expensive route
vivid kindle
which algorithm?
vivid kindle
oh, that one is supposed to be using floyd-warshall too
halcyon ledge
I don't think it does
I mean you can try this, rebuilt the graph in the tool and reverse the weights
look how it behaves
but I honestly think you're dealing with a dumber (more time efficient) algorithm
vivid kindle
alright, I'll try that link, thanks!
This is the description from the book (referencing the diagram)
last timber
well it is not sufficient description
they just refer to algo without showing it steps
meh
vivid kindle
@halcyon ledge alright yeah this gives me the results I was seeing in my implementation (for -G)
last timber
you've taken opposite signed edges?
@vivid kindle btw how is software called or what is the site
or it is you project?
vivid kindle
@last timber yeah to find the longest path (instead of shortest path) we transform G to -G. This screenshot is from the link @halcyon ledge listed above
last timber
thx
halcyon ledge
solid
ornate orbit
Anyone good with first order logic and models?
sleek swallow
Just ask your question. If it’s too advanced, then I’ll redirect you to #foundations
ornate orbit
thanks got help
wooden kiln
thorny willow
@wooden kiln a bunch of us know logic I believe
vivid kindle
@halcyon ledge @reef thistle @last timber we were right, I asked one of the book co-authors and they confirmed it was a bug the authors noticed some years ago (the book was published in 2003)
halcyon ledge
rofl
clever patrol
unsure if this is the right place but how is this simplification done?
these were the rules for simplification but i'm still confused about how some terms are just gone
pale epoch
seems to just be the middle rule used twice
clever patrol
ohh r = notx Z?
pale epoch
$\bar{y}\bar{y}x$ is obviously just $\bar{y}x$ and then you use the rule to get rid of the other terms
vital dewBOT
Lochverstärker:
pale epoch
ye, in one case $r=\bar{x}z$
vital dewBOT
Lochverstärker:
clever patrol
alright sweet
pale epoch
and in the other its $x\bar{y}$
vital dewBOT
Lochverstärker:
clever patrol
tyvm ❤️
pale epoch
yw
clever patrol
For something like this, is there a way to find the DNF without constructing a truth table?
I need to find the DNF first to do a Karnaugh map afterwards
pale epoch
i dont think there is a faster way to do it by hand than constructing a truth table
unless you can just see it
pale epoch
i might be wrong though
but i would usually try to simplify as best as i could first
then do a truth table
clever patrol
ye
digital scroll
So I dont have too much knowledge on the basics of this but can I say that an iterative function/a recursive function is continuous?
As in if we were to draw it on a cobweb diagram that curve would be continuous, but the orbits are 'discrete'?
Is the terminology correct??
reef thistle
@digital scroll Continuity is about whether the limit at each point is the same as the function at each point
digital scroll
Right
but I think the complication (for me) is that it for iterative/recursive functions, they can be visualised as a cobweb diagram or a time series plot
so like x_t against x__(t+1) or x against t
sorry I dont think I am explaining this well
north jewel
Anyone know how I can prove this?
Let $n$ and $s$ be integers such that $s < 2n$ and $A$ be a multiset such that the sum of elements in $A$ is $s$ and $|A|$ = $n$. Show that $\forall t \in {1, 2, ..., S - 1, S}$, $\exists B \subseteq A$ s.t. the sum of the elements in $B$ is $t$.
vital dewBOT
Frank:
north jewel
i.e. there's no 4-element multiset A that sums to 7 and positive integer k <= 7 such that k is not a sum of a subset of A
clever patrol
does anyone know how the 2nd line is obtained?
clever patrol
is that possible when the signs are different? it's AND & OR
halcyon ledge
thats how distribution works
if you have similar signs you don't have to distribute you use associativity
$a \land (b \land c) = a\land b \land c$
vital dewBOT
deekaan:
vital dewBOT
deekaan:
clever patrol
ah ok. was just confused because it's 2 terms for the 'a' section now
halcyon ledge
no worries
static basalt
If multiple nodes in a graph share the same eccentricity, say 2, if 2 is also the lowest eccentricity value does that mean all of these nodes are center nodes?
hasty glade
Lets say you have an integrer, for example 148500 and you want to find all their positive divisors. You break it down to 2^2x3^3x5^3x11. So your divisors can be ANY combination between like 2, 2^2x11 etc etc.. How do you calculate them ?
faint narwhal
what do you mean how do you calculate them?
It seems like you realize how to find all the divisors
hasty glade
I know how to
I need the number of them
And I do not know how to permute them
Lest say you have an intergrer N you want to find the number of positive divisors D
faint narwhal
Ah okay
Well, going back to your example, how many different choices can you pick for the power of 2
in other words, if you're trying to come up with a divisor of 148500, what are the possible powers of 2 that can appear in the prime factorization of the divisors
faint narwhal
Right, so you have 3 choices for the power of 2, 4 choices for the power of 3, 4 choices for the power of 5 and 2 choices for the power of 11
Uh, there's no 7
hasty glade
You are right
faint narwhal
So how many choices do you have in total
faint narwhal
Well, I don't really mean to add the choices
I mean, so you're going to pick 1 of the 3 choices for the power of 2, then you're going to pick 1 of the 4 choices for the power of 3 and so on
So in total, you're going to have 3 * 4 * 4 * 2 total ways to make these choices
weary tiger
if you have 22 distinct members in a club, and you want to pick 3 people for 3 distinct roles, then what does 22 * 21 * 20 - 20 * 19 * 18 calculate?
the first is ways to pick any 3 people for any 3 roles if one person cannot serve the same role
and the second is to not pick 2 distinct people
but what does the subtraction mean
lyric pumice
It calculates the number of picks of 3 people that have one or both of the two distinct individuals in a role.
weary tiger
that's what i thought, but it doesn't do that. if you calculate the number of ways that two people must be in the roles at the same time, or neither are, then that's 20 * 19 * 18 ways neither are, and 3 * 2 * 20 = 120 both are
so 6840 + 120 = 6960
but
the number of picks that 3 people have one or both of the two distinct individuals in a role should be a number larger than only if they both are
not if they both might be, including one of them can be
<@&286206848099549185>
lyric pumice
@weary tiger You are wrong.
weary tiger
about what
lyric pumice
weary tiger
what are you counting in 3 * 2 * 20 + 2 * 3 * 20 * 19
lyric pumice
The right side of the equation expresses the consideration of the case of 1 of the individuals in a role and the case of both of the individuals in roles.
weary tiger
ah but you're forcing them in the roles, i mean they don't have to be
but thanks
now i get it
the subtraction forces at least one of them into a role
🙂
vale flame
if asked to decide "which of the following complexity classes contain the given function?" is this asking which of the complexity classes are larger or equal to the function?
this is a made up example, im not sure which answers would be correct:
f(n) = 3n^2
O(1/2 * n^2)
O(n^2)
O(3n^2)
O(4n^2)
last timber
ye
it could not be
because you cannot find constant k such that n^2<=kn for all sufficiently large n
in general, polynom is O(n^p) where p is its highest power
last timber
nw
vale flame
would O(n!) also contain that function, because it's larger?
stray reef
yes
vale flame
great, thank you ^^
vale flame
not sure where i should ask about graph theory but its part of my discrete maths course so im going to ask here
does a node with an edge to itself count as a strongly connected component?
assuming no other incoming edges
vale flame
perfect, thank you
if I'm traversing a graph that has a node with an edge to itself, can i traverse that edge and do +1 to my walk length?
wait nvm
vale flame
does anyone know what this symbol means? ≼ i can't find anything online or in my textbook
last timber
usually it means that a and b are just in some relation
but ye, it is dependent
in context of posets it means that a is "less or equal" than b roughly
pale epoch
what's the problem
rustic stratus
im confused on basically where to start with this
pale epoch
then write down the definitions
what is a relation? what is the intersection of two relations? what does anti-symmetric mean?
rustic stratus
i just dont understand why R intersection S HAS to be anti-symmetric
stray reef
write down the definitions.
rustic stratus
i know the definitions
stray reef
your hypotheses are "A is a set", "R is a relation on A", "S is a relation on A", and "R is antisymmetric"
pale epoch
what does it mean for $R\cap S$ to be anti-symmetric?
vital dewBOT
Lochverstärker:
rustic stratus
the ordered pairs arent reversible unless they are the same right? if (a,b) is a pair on R then S cant have (b,a) unless b = a
stray reef
no
this is your \textbf{goal}:
$(\forall a, b\in A)[(a,b) \in R \cap S \land (b,a) \in R \cap S \to a = b]$
vital dewBOT
Ann:
pale epoch
but that does not translate to "if (a,b) is a pair on R then S cant have (b,a) unless b = a"
at least not in the context of the question
stray reef
okay, fine
your goal is
"if (a,b) in R cap S, then (b,a) not in R cap S unless a = b"
if you insist on using the "unless" connective
do you understand why this is your goal
rustic stratus
not really
i really just dont get how to do this problem when you dont know if S is symmetric or not and have no information about it
pale epoch
what makes you think you need any info on S
pale epoch
can you write down how $R \cap S$ looks
vital dewBOT
Lochverstärker:
stray reef
i am rewriting the definition of antisymmetry you gave. but with R cap S as the relation.
what is there not to understand?
@rustic stratus?
bleak forum
can i also ask algorithm questions pertaining to data structures on here ?
stray reef
yes, but this channel is currently occupied.
bleak forum
how long does it take for it to be available ?
halcyon ledge
you can use the help channels as well
then you don't have to worry about waiting
#help-8 looks empty for example
bleak forum
ok thanks
rustic stratus
ah sorry im in a meeting rn
work at home life
im really new to this stuff i dont quite get it
im watching more videos to properly understand relations
i really appreciete the help but im having a hard to making sense of pretty much anything as my classes lectures dont cover this stuff and i have to learn it all from youtube orgoogle
halcyon ledge
starting with the definitions is generally the best way to go about it
write them down and then try to build small examples
rustic stratus
so i understand now what the terms mean
but i dont understand where i can start to prove it
stray reef
have you ever like... proved things before, in general
rustic stratus
either of them
stray reef
either of what
rustic stratus
a or b
stray reef
they are trying to prove R cap S is antisymmetric
i.e. they are trying to prove that for all a and b in A, if (a,b) and (b,a) are both in R cap S, then a = b.
have you proved "for all" statements before?
rustic stratus
yes but they were all more simple
stray reef
this is not fundamentally different
they take two arbitrary elements a, b ∈ A which satisfy the premise, i.e. (a,b), (b,a) ∈ R cap S
rustic stratus
last time i tried to prove with example i got a 0 because they said that you can only disprove with example
stray reef
this is not a proof by example.
rustic stratus
why did they just pick (a,b), (b,a) then? couldnt they say that R is (a,b)?
stray reef
they could not say that "R is (a,b)" because R is a relation, i.e. a set of ordered pairs, and not itself an ordered pair
they are trying to prove that FOR ALL a and b in A, IF (a,b) and (b,a) are both in R cap S, THEN a = b.
have you proved IF-THEN statements before?
rustic stratus
i dont think so
stray reef
so you don't even know that the standard proof strategy for an if-then statement is to make the premise one of your assumptions?
rustic stratus
this is the first time ive seen any of this set stuff
stray reef
this is logic
rustic stratus
no im really new at this
i have not done a IF-THen statement before
i understand what it is
stray reef
weird bc if-then statements should have been the first things you proved
ok w/e i'm out
sacred dune
Id suggest doing some programming if you have time
sacred dune
Ah
rustic stratus
and this is really the first time ive worked with sets
so both R and S are relations on A, so if R = (a,b),(b,a), must S contain the same elements?
if so the intersection would be the same?
sacred dune
Wait I actuzlly have to read up haha
rustic stratus
this is the original question
sacred dune
Alright lets see
Well first im not sure I understand your above question
If R = (a,b)(b,a)
That means it's symmetric, at least for a and b. Are you trying a proof by contradiction?
rustic stratus
that was a example answer, they said that because R = a,b)(b,a), a must equal b in order for it to be anti symetric
sacred dune
Oh yeah
Well i mean im pretty sure the proof for the original question is pretty simple (disclaimer i dont do this stuff often so id recommend also cross checking with someone else)
rustic stratus
im having a hard time this is the first time ive attempted this stuff and it wasnt covered in any lectures
sacred dune
For all elements (a,b) in R, (b,a) does not belong to R, and further (a,b) belongs to R intersection S while (b,a) does not belong to R intersection S
Since all elements in R intersection S also belong to R, you cannot ever have symmetry in R intersection S
So R intersection S is antisymmetric
rustic stratus
thanks i actually sorta understand that
sacred dune
From my experience, looking at the general elements of the sets given is usually a good way to go about the proofs
rustic stratus
so if R = (x,y), (y,x), given that R must be anti-symetric, x must equal y, therefore: S is anti symetric because (y,x),(x,y) x = y
sacred dune
You dont need to say that because that's specific to one example of R
rustic stratus
all elements in R must be shared by S right? because they are both relations of the same set?
sacred dune
No
rustic stratus
oh
sacred dune
Because they can be different relations
Take the set A = {1,2,3,4,5,6}
R defined as xRy <=> x<y<2
And S defined as xRy <=> x>y>3
Then R = {}
And S = {(6,5),(6,4),(5,4)}
You can see how they dont share elements
rustic stratus
yes
sacred dune
However
rustic stratus
is {} always oging to be asymetric?
rustic stratus
so the intersection is blank, therefor R cap S is asymetic
sacred dune
To be honest actually maybe you shouldnt quote me on that
For all I know asymmetry demands the non empty set
But i could come up with other examples
Which still work
Like instead of x<y<2 we had x<y<3
That would have (1,2) as an element in R
For the proof, S is honestly not that important
rustic stratus
i think for it to be anti symetric it needs 2 elements, so if the set {1,2}, {2,1} intersected with {(6,5),(6,4),(5,4)}, im pretty sure that would be symetric which is where im confused
or wait
sacred dune
No see
The intersection of those sets is the empty set
But anyways S doesnt matter
All that matters is that elements lf R intersection S must be elements of R
In other words
R intersection S is a subset of R
That's true of any intersection
So since R is antisymmetric, all its subsets must be too
So R intersection S is antisymmetric
rustic stratus
ty i understand that
feral mirage
In a survey of 200 students of a school, it was found that 120 study Mathematics, 90 study
Physics and 70 study Chemistry, 40 study Mathematics and Physics, 30 study Physics and
Chemistry, 50 study Chemistry and Mathematics and 20 study none of these subjects. Find
the number of students who study all three subjects.
How would I go about solving this?
sacred dune
Make a venn diagram
sleek swallow
Draw a venn diagram
sacred dune
That will greatly help
weary tiger
venn diagram
(youtube is blocked for me so had to put in that link)
of how to use venn diagrams
feral mirage
I am familiar with them but
not 3 way venn diagrams
i.e.
if the 2 intersections of chemistry = 80 but the total people taking chemistry equals 70
that would mean chemistry = {-10}
feral mirage
most of the examples I'm finding show examples where the number intersecting all three circles is known
I don't know how to begin without knowing A intersect B intersect C
halcyon ledge
write the numbers
down
like if you just add up the number of people that study math/chemistry and physics
you'll get a value that's higher than 180
then look if you can account for the difference by looking at the double majors
feral mirage
I found a nice video which goes through it algebraically https://www.youtube.com/watch?v=2IyprMaO8rU
weary tiger
You good @feral mirage
prisma arch
Can someone explain this to me? I'm not exactly sure why this is not just 24!/26!
weary tiger
I dont know probability but
Isnt it just asking how many 2 letter combinations can you have
robust mango
You need A and Z to be next to each other so put them in one block. Think of it as this: [AZ] [Rest of the letters(24)]
robust mango
The rest of the letters are 24 blocks, the block containing AZ is the 25th block.
weary tiger
Oh
robust mango
So that means 25!
weary tiger
Yeah still 2/26
robust mango
But then the internal arrangement of AZ is also considered
So you have 25! * 2! / 26!
prisma arch
wait so explain the internal arrangement for me because I dont get that part for the 2!
robust mango
AZ can also be ZA
you have two options
Z and A are different so there's 2! ways of arranging them
prisma arch
Well isnt A supposed to precede Z each time?
robust mango
No they just have to be next to each other
robust mango
And for the simplification part, you can write 26! as 26 * 25!
So you get 25! * 2! / 26 * 25!
prisma arch
Thank you this makes sense to me
flat hollow
Hi everyone. I hope you are well. I am doing this problem and I am really blocking. Anyone know how to solve this : Let k be a positive integer. Show that
faint narwhal
What have you tried?
flat hollow
It's the first time I see something like this, so I don't really know how to do it
vapid light
What's a conservative estimate for that sum
flat hollow
They did not provide any. The problem is really given in this form.
vapid light
Yeah, I know, but if you were to put a cap on this sum, what's something you could do that would make it easier to sum up?
flat hollow
By capping you mean finding an upper bound ?
vapid light
Yep
Hint: ||You should try to replace all the terms with something s.t. all the existing terms are <= to the new term||
flat hollow
I know that n square is written roughly in the same form in summation and its fractionnal form gives n(n+1)/2, should i exploit this side there?
vapid light
No, it's raised to arbitrary power
That formula only works for k=1
Hint: What's the relation between all of the terms. Can you rank their sizes?
Ah, screwed that up
flat hollow
Ok, I don't think I can find it myself. Could you give me your solution please?
vapid light
I don't really want to give it away, but try to replace the terms in the sum
Hint: All of the terms in the sum should be the same
It would be really easy to sum up if all of the terms were the same, right?
Also, we see that this is O(n^(k+1)), right? How can you rewrite n^(k+1)?
flat hollow
Can we say that all the terms are lower than n^(k) and replace them ?
flat hollow
Okay, I think I understand now. If I replace all the terms with something that is surely bigger than them. n ^ k in this case, their total complexity will be c * n ^ k which is always less than n ^ (k + 1) so O(n^k) will be a subset of O(n^(k+1))
@vapid light Thanks for your help !
vapid light
Technically, since you had n copies of n^k, it's n^(k+1)
And yes, that's a good takeaway you got from that problem
Nice job
flat hollow
It's thanks to you !
vapid light
Also, just to clarify, n would not play the role of a constant, it's not c*n^k because the number of terms you need to sum up increases linearly with respect to n.
Felt like I should clear that up
@flat hollow
flat hollow
Yes indeed. It's appreciated.
hardy remnant
hi i just need clarification, so normal 1+1=3 is a statement (false) but something like x-3=9 would not be a proposition then?
thats interesting
sacred dune
Yeah x+2 =11 isnt a proposition cause it offers no info on x
You cant assert whether or not it's true because we dont know if it is 9 or not
mystic bobcat
I draw three numbers with repetition from set (1-8). I multiply all three numbers. How many numbers do I get which are divisible by 4?
For example:
I can get 2,2,2. It's multiplication is 2 * 2 *2 = 8 and 8 is divisible by 4
I can get 1,1,2. It's multiplication is 1 * 1 * 2 = 2 but 2 is not divisible by 4
flat hollow
Could someone do that for me please. Using mathematical induction, show that:
rain stone
@mystic bobcat you need to draw at leat two 2's OR at least one 4, OR at least one 8 for the condition to hold. So it's basically asking how many triples meet those conditions
also 2 * 2 * 2 is not 16
it is 8
halcyon ledge
hmm joker have you tried anything?
flat hollow
Yes, I've been on it for an hour but now I have to go home. So I would like to have a solution to compare tomorrow
flat hollow
First i specify the value of the function in zero. Then I give the rule to find the value of the function for new integers at from the value of the function for more integers small. I really tried ..
mystic bobcat
@rain stone I know that that the probability of drawing 4 is 1 - (7/8)^3 But I want to know how many numbers I can draw that have at least one 4 or at least two 2's
How to count how many triplets meet these conditions.
static basalt
Need clarification on what C actually does.
Is it the minimum number of edges from node x to node Alvaro?
brazen tendon
can you guys tell me if my logic is correct please
I am asking about the stuff i did on the bottom half of the page
my friend made a truth table and sait there is one false so it ruins the whole thing but
I made it this way and im unsure about what to do now
sour arrow
Possible to see the truth table?
vapid light
I recommend for inductive questions that have a plus one somewhere to start the inductive hypothesis at k-1
keeps things cleaner
brazen tendon
What?
vapid light
For this
there's an n+1
its more convenient to use n = var - 1 rather than n = var
brazen tendon
Oh you are not talking about my question I guess, sorry
If you could help about my question that would be amazing
vapid light
What's your question
median mulch
Hey just wondering if anyone could help get me started on this question.
stray reef
have you done part (i)?
median mulch
Nah, still stuck on the initial information, mainly struggling to understand this
median mulch
okay, thanks. so for the cartesian product of Z x Z, how do i create equivalence classes since the set Z is infinite. I've done questions like this with finite sets with no issue but kinda hard to wrap my head around how to do the same with infinite sets like Z
sacred dune
well that depends on your relation
oh didnt see the original picture
have you already done i)?
median mulch
nah haven't be able to do it because i dont really have a grasp on the inital information yet. Mainly just don't understand what the set Z x Z would look like since it is infinite
sacred dune
it's simply all pairs of integers
you could kind of think of an integer plane if that helps
You dont really have to think about ZxZ
median mulch
ohh okay, makes sense. so the pairs would be like: {(1,1),(2,2)(3,3)....}?
sacred dune
That's just because the Relation is a subset of it, but a relation R on A is always a subset of AxA
not exactly
are you familiar with congruence mod n notation?
median mulch
a little bit, but not super in depth yet
sacred dune
okay
well the relation R can be reformulated
i cant find the latex equivalence sign XD
well anyways a = b + kn is the same as saying a is congruent to b mod n
median mulch
haha, all good. So for the pair (a,b) here would values should i be plugging in, any example would help
ahh yeah makes sense
median mulch
okay cool, thanks for all that. i'll give the questions another crack now 🙂
sacred dune
alright lmk if you run into problems
median mulch
okay i think i understand this now. So when n = 4, and a = 1 and b = 2, the equivalence class [a] would be {1,5,9,13,17...} and the equivalence class [b] would be {2,6,10,14,18,22..}. So from my understanding the intersection of both equivalence would be the empty set. Have i understood this correctly or nah?
median mulch
yeah i get that, thanks!
sacred dune
try and generalize conditions for b and a and how they relate to eachother and n so that the intersection is the empty set
median mulch
okay thankyou
brazen tendon
last timber
@brazen tendon looks alright
last timber
@brazen tendon actually
you should rewrite (p or q) -> not s
in terms of not (p or q) or not s
then by De Morgan it becomes not ((p or q) and s)
and since p or q is true
ah
nvm
but its alright how you did
brazen tendon
btw
the thing is
when you make a truth table
there are 2 Falses
its not a tautology but
I proved that you get S
so it should be correct?
last timber
i think so
brazen tendon
What about those falses though 😄
sleek swallow
wut what are you asking?
last timber
lol i now really doubt
sleek swallow
like, i don't understand the fking question they're asking lmao
brazen tendon
last timber
@brazen tendon how you come to 6 by modus ponens?
last timber
i mean by cotrapositive you can get
s -> not (p or q)
sleek swallow
that doesn't look correct by modus ponens
last timber
modus ponens is that p -> q, p = T hence q = T
by contrapositive
you can do s -> !(p or q) [here 5 can be used]
s -> T
but it does not give
anything
so s is undefined
the first sentence of the task is strange
i cannot get whether there is "IF" or "IF AND ONLY IF"
brazen tendon
wait
so using 4 and 5
modus tollens?
actually no it gives you s again I tihnk
maybe I should just make a truth table
last timber
yoy get s -> !(p or q) by contrapositive and 5
but modus tollens is not appliable here
since !(p or q) is true
and s -> T is always true
brazen tendon
so should I just make a truth table
or show it this kind of way
here is the table
last timber
so should I just make a truth table
no you just show that it is impossible to make a concluison
last timber
no, i say s -> T is always true
brazen tendon
Ok it is yes
oh so you are saying
s-> T therefore s
so
(s->T) -> s
but if s is false
its false
last timber
it does not follow
brazen tendon
man my brain is all messed up
I think I will just write the truth table
its correct anyways
to show that there is one false that way
last timber
ah do as you wish but i warned you huh
brazen tendon
I think I don't know how this notation works
like when you say
!(p or q)
in a line like that
do you say that that whole thing is true
brazen tendon
ohhh
I understand now
thats weird
the problem is I started learning this subject just when corona virus came out
so classes got cut halfway
and I tried to learn some stuff from the internet but couldn't really learn nicely
last timber
there are a lot of nice books on logic
last timber
@brazen tendon there is two combinations of t = T and q = F which give true impl
last timber
nvm
alright why you have (p or q) -> !s
you wrongly made the whole statement btw
anyway, you do not need truth table here
just reread discussion and you ll see that argument is not valid because it is impossible to draw up a conlcusion
vital dewBOT
suck2015:
fading abyss
just to check, if we have flavors A and B, that's not the same as B and A? because then combs works and that answer is correct
pale epoch
this works if (A, B) and (B, A) are considered the same
woeful kraken
In a grid NxN I want to place x amount of objects, where the sum of the distance between them is maximized. Distance is calculated using Euclidean distance. Is there a way to calculate the maximum sum of distance possible?
blazing night
I have a couple of questions
So in this thing... the P and Not P dissapear. and the disjunction between the not q and not q basically form not q right?
So that is a correct statement?
vapid light
Question, what's the comma and the "division bar" supposed to mean
I never saw this in my discrete math class
blazing night
I wasn't really told in my classes, it was just done like that
I can show an example
vapid light
Ok
weary tiger
Probably means that the first one is logically equivalent to the bottom one.
vapid light
That's what I was thinking
weary tiger
You can reduce the first one to (not q).
vapid light
But I usually use the congruence sign
blazing night
Oh my god I did it the other way around
weary tiger
Ye, math and its many notations
vapid light
And what's the comma
weary tiger
Probably "and"
blazing night
And it would be P and not P .. and under it I guess it's like
Is it equivalent
Let me check
That raised me a question
vapid light
So you can "factor"out the not q and you get (p or not p) and not q
So this statement does not depend on p at all
weary tiger
p and not p, right?
blazing night
p disjuction with not p...
Not similar to not q
If I recall
So the statement is wrong
vapid light
P and not p would always be false
blazing night
For some reason I removed the P instead of the Q
Welp that's one question out of the way xD thanks
weary tiger
(p + q')(p' + q')
(pp' + pq' + q'p' + q'q')
(0 + pq' + q'p' + q')
pq' + q'p' + q'
q'(p + p' + 1)
q'(1)
q'
vapid light
I'm gonna have to brush up on boolean logic
blazing night
Alright another question:
Consider the domains D1 = {a, b, c}, D2 = {1,2,3,4}, D3 = {x, y}, D4 = {John, Alex}. r1 = D1 * D2, r2 = D2 * D3 * D4
What is the number of combinations of r1?
Now this one..
I just do not know what it means
r1 is made from D1 with D2...
Does it mean to get every element from D1 into D2 and it would just make 12 combinations?
I don't think it's that simple in my head
weary tiger
Is * a symbol for the cartesian product between the two sets?