an is a sequence of real numbers
#discrete-math
coral raven
no
candid hollow
hi, i've got this question and im stuck on it: let A and B be subsets of a set E, and X a subset of E be the solution to the equation (A\X)U(X\A)=B , i've proved that XUA=BUA and that XU(~A)=(~B)U(~A), now im asked to deduce that X is a solution iff B=~A
i proved that B is a subset of ~A and now im stuck :(
worthy sky
Yes thank you! And then I can use the sphere packing bound.
sonic sky
can anyone help me with this question i'm compeletly lost on it
pale epoch
use the pigeonhole principle
sonic sky
ohh okay! thanks
stiff bloom
(a) When L(u) is equal to infinity
(b) When w(v,u) is equal to infinity
(c) When {u,v} ∉ E
(d) When L(u) + w(u,v) < L(v) ```
glacial flame
@stiff bloom What is a weighted graph? What are u and v? What is w?
glacial flame
Ok, but have you made a research?
worthy sky
u and v are vertices on a graph
w is the weight of the walk between u and v
(I think that is what w is)
stiff bloom
(I think that is what w is)
yes
glacial flame
what do you mean by research ?
You need to make a research about the terms and statements in the problem if you don't know them from your head.
That's what I meant.
worthy sky
How can a walk be infinity??
glacial flame
If two nodes are not connected
stiff bloom
If two nodes are not connected
right
glacial flame
Or if the weights between them are infinite 🙂
And what is L...
I mean what a question is this...
stiff bloom
initial path
glacial flame
What is the initial path?
stiff bloom
L(u) + w(u,v) < L(v) then L(v) := L(u) + w(u,v)
mystic moss
Fairly certain w is weight of the edge
stiff bloom
yeah w is the wegiht
glacial flame
w(u,v) is infinite, if w(v,u) is infinite
worthy sky
Yeah
glacial flame
Fairly certain w is weight of the edge
But w can be between any (u,v), Not just adjancent ones.
sonic sky
for 1b its 26 right because the minimum students to have 2 students b-day in one month is 24 and given if the mini for 3 b day for one month is 25 so wouldnt the mini for 4 b-days for one month be 26?
mystic moss
But w can be between any (u,v), Not just adjancent ones.
Exactly that’s the point of the question.
glacial flame
Oh, perhaps w(uv) between non-adjacent is inifinite?
stiff bloom
yeah between non adjacent is infinite
glacial flame
I mean b is obviously the answer.
Whichever relation w is, it must be symetrical 😐
But you need to check your book @stiff bloom to find these symbols and definitions.
stiff bloom
ok mate i will ask my classmates
mystic moss
Whichever relation w is, it must be symetrical 😐
Directed graphs?
glacial flame
Yes, but it is not mentioned in the question 😐
I was thinking like, what can be an asymetric relation in graphs
And directed graph came to my mind also
mystic moss
Yes, but it is not mentioned in the question 😐
Either way, you can’t have a weight on a non-existent edge
glacial flame
If you define a weight as a relation between two vertices, you can define it as inf.
Nothing is defined in this question, so I don't know what to say.
Even in wolfram alpha it defines weighted graph where each "branch" is assigned a weight.
mystic moss
If you define a weight as a relation between two vertices, you can define it as ...
Exactly, this is done in shortest path
glacial flame
And when you check Graph article, to check what is the branch, they dont mention this term at all.
@mystic moss and what is L?
mystic moss
<@!494362718321639427> and what is L?
Probably the distance from s to the other vertex
(So far in the algorithm)
ocean coyote
@sonic sky did you figure it out? 1B is 37
upbeat trail
anyone awke right now?
mystic moss
no.
weary tiger
my professor wants me to expand the idea of d = b+1, but i don't quite see how that can be done
upbeat trail
obtuse lance
@upbeat trail what have you tried
upbeat trail
not ganna lie idk how to even approach
obtuse lance
well if I were you I'd try to write down the definition of a reflexive relation and what it means to be symmetric
does that give you anything to move around or play with?
upbeat trail
not really
clever sage
@upbeat trail prove that an equivalence relation divides a set into paritions
crystal dove
Given 2 generators for a finite symmetric group (such as transposition with n-cycle), is there always a Hamiltonian walk through the corresponding Cayley graph?
And is it easy to find?
safe scroll
hoary dock
can i do this
rich oasis
Is anyone able to help me figure out how to find the symmetric closure of this matrix I’m pretty lost
would this be right?
from what i understand from my book its just the relation of my matrix with all the edges made bidirectional
so that means i remove the 1,1 relation and the 3,2 relation
i labeled my matrix rows and columns 1-3 to make the arrow diagram first
daring beacon
can someone help me with c?
I already have the answer but Idk where the 2! came from
balmy ridge
2! is for 2 ways 3 and 6 can be arranged (i.e 36 or 63)
delicate ridge
i labeled my matrix rows and columns 1-3 to make the arrow diagram first
nah you keep the 1,1 relationship
basically, you need to find the smallest number of edges you can add such that for any edge (x, y), there is also an edge (y, x)
rich oasis
basically, you need to find the smallest number of edges you can add such that f...
So this?
delicate ridge
aye
basically, the fewest number of ones you can add such that the matrix is equal to its transpose
solemn dome
does anyone know how to do this?
delicate ridge
Reflexive closure just means for any node in the graph x, there has to be an edge (x,x)
rich oasis
right so I need a 1,1 2,2 3,3 and if they're missing in the original relation I just add them in while keeping original relations?
oh whoops i missed one
last row should be all 1s and so i believe thats correct
compact orbit
Using inference rules I have to conclude that can someone give me a head start into what to do here? We only have as a constant A.
compact orbit
<@&286206848099549185>
south marten
Would taking the gcd of a, b and using the Euclidean algorithm work
south marten
all right sweet @gilded urchin came up with a different solution then what was in the book
compact orbit
what could be a propositional equivalence to this argument?
lyric pumice
lyric pumice
You should try to prove it.
minor dagger
its just the negation
tacit plume
Hey guys is there a way to figure out how many X’s and O’s you need for a game of Tic Tac Toe? There are 20 games going on
How do I distribute the pieces among the each game so that they all have the minimal amount of pieces needed for any combination of a game’s outcome
lyric pumice
What do you mean? Can you give an example of a distribution?
tacit plume
assume I have an unlimited amount of X and O pieces. However, I want to give each game board the minimum amount of pieces so that they are able to complete a game in any way possible
I looked a some game sets give 5 X’s and 5 O’s but I’d like to know how this is determined and if this is the minimum needed
lyric pumice
What is the maximum number of Xs that can be put on a board?
tacit plume
There’s 9 spaces on a board. So I guess if each person takes their turn putting their piece down, then it’d be 6
*5
So did I just answer my own question
Shit
lyric pumice
That does not fully answer the question.
Is it legally possible to put 5 Xs on the board? If so, then show it by example.
lyric pumice
Alright, good.
tacit plume
Wait idk if that’s possible though because the game would stop before the last X is placed anyways
lyric pumice
A draw game would stop only after the board is filled.
tacit plume
Isn’t there a point reached when a draw game is inevitable
lyric pumice
Yes, there is a point of inevitability.
tacit plume
I guess that’s out of my question though isn’t it
Because it differs with every game
ocean coyote
the game can end without filling the board
there is no legal move after someone wins the game
whomever goes first can win in 3 moves with 5 pieces total on the game board
there are exactly (8*30)/2 examples of this
blazing forum
Hi! Does anyone know how to solve this problem?
Suppose G a graph where every node has degree 4. Proof that you can colour the edges with 2 colours, so that every node lays on 2 edges of one colour and 2 edges of the other one.
reef thistle
hmm...
looks like you need to find a 2-matching of one colour
@blazing forum If the graph is not connected, then work on each connected component. Do there exist bridges? Try removing maximum cycles?
What have you tried?
blazing forum
I was thinking about something with Euler cycles but I'm not sure
because every degree is even
And yes, it's a simple graph, so no parallels are allowed
I'll try with maximum cycles, good idea
reef thistle
wait, euler cycle works
you are a genius
@blazing forum
try colouring the euler cycle
reef thistle
nice
blazing forum
Assume G is a simple graph.
Start from a random node. Because every node has an even degree, it will be possible to find a partial graph of a Euler cycle in every connected component.
Because the sum of the edges will always be even, you must end up with the same colour in that edge, by walking over every edge just one time (Def Euler cycle). So now 2 edges are coloured in colour A. If you pick another edge of that same node that isn't coloured yet and do the same pattern with colour B, you'll end up in the same node with colour B. But because the other 2 edges are already coloured in colour A, the only possible solution to colour an edge of that node, is the last edge that isn't coloured yet. This can be repeated for every random node and so it's proven.
Do you think this would be right?
blazing forum
oh no forget the last sentence of not coloured yet haha, because you coloured it already in that eulerian walk, stupid me
but now I've got it, thank you very much @reef thistle !!
reef thistle
idk I don't really understand your proof.
I just alternate a, b, a, b on the euler circuit
@blazing forum
also, gotta sleep
crystal dove
Does anyone know if it's always possible to find a hamiltonian walk through the cayley graph of a 2-generated symmetric group?
And how hard would it be to find this path?
reef thistle
there's terminology spam here @crystal dove
firstly, what's a 2-generated symmetric group?
is it the symmetric group S_n with the generators (1 2) and (1 2 3 ... n)?
or is it any group with two generators?
ocean coyote
maybe this is relevant? https://groupprops.subwiki.org/wiki/Symmetric_group_on_a_finite_set_is_2-generated
@reef thistle @crystal dove
reef thistle
yeah I just mentioned it earlier
is it the symmetric group S_n with the generators (1 2) and (1 2 3 ... n)?
crystal dove
Yes, a transposition and n-cycle.
I should've been more specific
It's just that it's possible to choose different minimal generators
And if there were interesting answers there, I didn't want to restrict it
Sorry I didn't mean to vocab spam -_-a
Is there a better way to ask the question?
stray reef
what's giving you trouble here
stray reef
how awfully specific.
when you go to the doctor and she asks you what's wrong, do you just say "i feel ill"?
weary tiger
yep
stray reef
... they left.
obtuse lance
lol
vague quartz
oh Damn rip lol
lusty pelican
Can someone explain me this question: If a>1, and a | b, then 3b+1 mod a = ___, I don't understand the mod a part
lusty pelican
what's the remainder when you do (3ka + 1)/a
3k +1/a
lusty pelican
but what's the remainder when you divide
I'm not sure
compact orbit
I have Hoare logic homework and i dont really understand how to relate it to Propositional logic, any tips?
stray reef
god that typesetting AND wording is wack
anyway, if you have a hoare triplet {P} S {Q} and the program never terminates in its execution of S,
then Q never has to be satisfied
compact orbit
god that typesetting AND wording is wack
That's how it is on the homework tho 🤷🏼♂️
stray reef
not blaming you here
compact orbit
But how can you relate this to propositional logic
compact orbit
not blaming you here
aight
stray reef
prop logic is how you justify why while true x := x+1 end while never terminates
i mean, while(true) {whatever...} never terminates by construction
since the condition true never returns false
since, well
yknow
compact orbit
So it never ends because of the program itself, but it still proves to be valid becase the triple is stated alright?
stray reef
yes to the first part, no to the second
compact orbit
It is partly valid
compact orbit
Sorry?
stray reef
it's not because of "the triple being stated alright"
thats a necessary but not sufficient condition
the reason the hoare triplet is valid is because the post-condition ({Q}) has to be true after execution
but there IS no "after execution"
compact orbit
@stray reef So is there anyway I can use a propositional logic formula to prove it?
stray reef
i don't know what counts as "justify using propositional logic" to your professor/teacher/whoever
so i don't know how to answer that either
idk the exact sequence of symbols your prof wants you to say
compact orbit
Alright, thank you so much
worthy thistle
How does adding/removing a variable to a boolean function affect its minterms?
i'm trying to use induction to show that a function with n+1 variables can also be written as a sum but I don't know how to add a new variable to a previous minterm
worthy thistle
In boolean algebra, am I allowed to say a(x1, x2, x3) = a(1, x2, x3) + a(0, x2, x3) and = (x1+x1')(a(x2,x3))?
dawn moon
Can someone help me with this pls?
weary tiger
i would if i understood it
stiff bloom
3rd choice ?
stray reef
not even close
of all the graphs offered, you chose the one that has a clearly visible cycle
cycles are forbidden in a tree
stiff bloom
so first choice ?
stray reef
yes
stiff bloom
how do i identify if a graph is a cycle ?
stray reef
do you mean "is" or "has"
stiff bloom
has
reef thistle
@crystal dove hmm interesting, found this: https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.3240050209
So the answer is likely positive via heuristics.
Lovász conjecture: ouch this doesn't look resolved in the general case
@crystal dove Hey your answer is there on that wikipedia page
time to find a reference
Wikipedia ->
https://www.math.ucla.edu/~pak/papers/hamcayley9.pdf
[CW] R. C. Compton, S. G. Williamson, Doubly adjacent Gray codes for the symmetric group,
Linear and Multilinear Algebra 35 (1993), 237–293.
[I suspect]
https://doi.org/10.1080/03081089308818261
https://pdfslide.net/documents/doubly-adjacent-gray-codes-for-the-symmetric-group.html
I have a feeling the article might have mixed up their sources
hmm idk really
crystal dove
@reef thistle I was thinking a problem this shallow would be like ultra well-paved over ~_~
pale epoch
all the numbers on the left are finite and hence after some point you will have the digits be identically 0
if you now apply this argument, you don't end up with a new natural number
but an infinite string
while this is not on the list, it is also not a natural number
(also this is not discrete math, but it doesn't matter)
@tall pine
the numbers on the right might be finite, but they may also be not
the key point is that the new number you construct may be infinite
like
0.1111...
is still a real number
on the left all the representations are eventually zero
and the new number you create might not have this property
(and is thus not a natural number)
for the second question, this would probably be #proofs-and-logic not sure
it's a question of set theory, but rather basic
pale epoch
what have you tried
untold raptor
tbh im not really sure cuase from what i understand of abelian is that (mZ, +) is commutive but i dont really know how to prove that (Z, +). is too
pale epoch
you should know that (Z, +) is abelian
pale epoch
also it's not really important to the question
untold raptor
but my main question is how to i prove it is a sub group casue
cause rn im very lost
untold raptor
nope
coral raven
ohhhkay
so it's a subset of the underlying set of the group
which is a group under the same operation as the larger group
associativity is a given because the parent group is
it needs to have the identity
it needs to be closed in itself
each of its elements has to have an inverse in the subgroup
untold raptor
ah i see thanks
last timber
weary tiger
seems wrong tbh..
weary tiger
mod(a,b) = a-b(floor(a/b))
floor(mod(a,bc)/c) = floor( (a-(bc)floor(a/(bc)) / c)
= floor( a/c - b*floor(a/(bc))/c )
= floor( a/c - b/c * floor(a/(bc)) )
!= a/c - b * floor(a/(bc))
Got close to it, but the floor is always sitting there being a butt
last timber
a = xc -> mod (a, bc) =0 but mod(x, b) does not necesssarily equal 0
uh wait a = xc -> mod (a, bc) =0 this is not necessarily true
but it can be true tho
e.g let x and c be pairwise prime, then xc maybe divisible by bc if b is divisible by c
but x may fail to be so
and also
a/c can be not an integer
weary tiger
I forgot to floor it.
Division here is kinda ssumed integer div
mod(a,bc)/c = mod(a/c, b), (assuming integer division)
But I have a weird feeling it's true for positive cases
mystic moss
If we have a = bc * q + r, then we have a/c = b * q + r/c
last timber
,w mod (14,6)/2
vital dewBOT
last timber
ok nvm i am idiot
weary tiger
Though, it seems like it's true for positive
mod(a, b) = a - b*floor(a/b), since positive
mod(a,bc)/c = floor(mod(a,bc)/c)
= floor((a - (bc)floor(a/(bc)))/c)
= floor(a/c - b*floor(a/(bc)))
= floor(a/c) - b*floor(a/(bc))
mod(a/c, b) = mod(floor(a/c), b)
= floor(a/c) - b*floor(floor(a/c)/b)
= floor(a/c) - b*floor(a/(bc))
So mod(a/c, b) = mod(a,bc)/c
(for positive integer & integer division)
I think it's possible to prove that it also works as long as b is positive, but I'll think about that later.
mod(a/c, b) = mod(a,bc)/c, is true assuming integer division & b > 0
amber hill
Hi, I have a question. So, suppose I have a set $A={a,b,c}$, how do I find number of symmetric relation that contain ordered pair $(a,b), (c,c)$.
vital dewBOT
usernamephobic
amber hill
I know the answer to this but what do I do in general, for example for set with 20 elements. Is there a formula or method to do this?
amber hill
<@&286206848099549185>
abstract ravine
hey whats the point of 2's complement?
last timber
@abstract ravine it allows to store more values for int in programming e.g
abstract ravine
from what i understand, its supposed to represent a negative number?
also what does you mean with "allow to store more values for int"
last timber
well 1's complement where you in general use 1 bit for sign allows use e.g for 8-bit integer values from -127 to 127
but 2's complement allows store from -128 to 127
because in 2's complement you have 2^7 values for nonnegative and 2^7 for negative
but in 1's you have 2^7 for nonnegative and 2^7-1 for negative and one is lost
abstract ravine
ok but it says that if a number has a '1' as the leftmost digit, then it is a negative number?
is that always the case for binary numbers?
last timber
i do not know details but yes
because look
011111111 is 127
but 127 complement is 10000000
which is e.g -127 (or -1 or whatsoever)
and in general any number in binary representation in 0,..,127 would be of the form 0....
and its complement would be 1....
abstract ravine
ok thank you
amber hill
My problem is always shadowed. SAD LIFE. But I figured it out this time sso no problema
fast temple
but 127 complement is `10000000`
This is the reduced radix complement of 127 or 1's complement
10000000 is -128, -127 is the 2's complement of 01111111 which is 10000001
fast temple
Yeah gotchu
I just wanted to clarify
using 2's complement to code negative numbers is done by just taking the 2's complement of the corresponding positive number, the 1 in the beginning is a natural consequence of that because the numbers being coded only go up to 7 bits and are being stored in 8 bits
the cool thing about 2's complement form is that it allows us to do addition and subtraction while completely ignoring the sign and we still get the correct answer as long as there's no overflow
meanwhile with signed magnitude form we have to manually adjust for the sign and we have two zeros, 10000000 and 00000000, one negative and one positive.
fast temple
using 2's complement to code negative numbers is done by just taking the 2's com...
(the same applies for multiple-byte integers)
abstract ravine
i see
Find the 16 bit Computer representation of the integer 9843
First i need to convert the integer to binary correct?
so, i can do that by dividing the integer by repeatedly diving 9843 by 2
right?
last timber
not by 2, but by powers of two
abstract ravine
are you converting **9843** to binary?
Yes i am
ocean coyote
First i need to convert the integer to binary correct?
16 bit unsigned I guess
abstract ravine
what is your answer suupposed to be?
The question is:
find the 16 bit computer representation of the integer 9843
ocean coyote
that question is bullshit but ok
abstract ravine
Its from a book tho 👀
ocean coyote
they should at least specify if they expect unsigned int
abstract ravine
Lemme check
ocean coyote
this can happen in very beginner friendly classes that skip important details
they just want it in base 2
but base 2 is not a specific encoding scheme for a 16 bit computer representation
abstract ravine
ocean coyote
they want base 2
abstract ravine
Have to do 2’s complement
ocean coyote
yeah you can do that
abstract ravine
But my answer is still wrong tho
ocean coyote
wait your division should be quotient remainder
you should not have 865385437.5
think of it as subtraction
subtract the largest power of 2
then note the index
abstract ravine
I know, if its .something then its 1
Otherwise its 0
My calculation still wrong tho
abstract ravine
Will do as soon as i get home
ocean coyote
we use computers to solve it but you also need to practice pencil and paper
abstract ravine
Ye ofc, the funny thing is i was solving most of them like that
Now suddenly it doesnt work
Whatever might be doing something wrong
ocean coyote
topaz tendon
@fast temple you there
zinc marsh
My course gives the following definition of a p-group: "A p-group is a group with order = a power of prime"
The wikipedia says: "A p-group is a group in which all elements has order prime power"
How do I show the 2 are equivalent ?
pale epoch
cauchy's theorem
topaz tendon
B'C' + A'B'D + AB'D' + A'BCD' + ABCD
can someone simplify it
@fast temple
@pale epoch
zinc marsh
Cauchy theorem gives the existence of a element with order prime power
but it doesn't show for all element in the group
pale epoch
for every prime dividing the group order
so if the group order is not a primepower, ...
the other direction is just lagrange
zinc marsh
oh you mean Cauchy for the element of order prime power => group order prime p power direction
So for the other direction: consider the subgroup generated by an arbitrary element g <g>, then <g> order has to be of order prime power according to lagrange, which also means g has order prime power, correct?
Ok I get it now thanks !
fast temple
@topaz tendon bruh it's the same one we did last time
molten hearth
Is a graph node with an edge connected to itself adjacent to itself?
pale epoch
sure
molten hearth
2 more graph theory questions:
- If trivial walks are a thing, what is the purpose of a loop?
- Does an x-y walk have to end on the first encounter of y?
pale epoch
what?
molten hearth
what is stupid about it?
pale epoch
they redacted their question
molten hearth
ah
weary tiger
for the second question, no a walk does not need to end on the first encounter of y if it is an x-y walk
i dont exactly understand what the first question is asking tho
molten hearth
i dont know what the point of a loop is
it would sort of make sense if trivial walks were not allowed - the loop would allow pseudo-trivial walks to exist but as they are now i dont see what the point of loops is
pale epoch
what do walks have to do with loops?
weary tiger
hey guys, dont mind me just a dumb question but
under what condition does sup(A) or inf(A) exist in A?
weary tiger
wdym-
stray reef
what else is known about this underlying ordered set
weary tiger
just that
if A is bounded above, are there any specific conditions where sup(A) is in A?
ikik dumb question i just wondered-
stray reef
well, if A happens to have a greatest element, then that element will also be its supremum
coral raven
i mean that's if not iff right
weary tiger
wait wdym "hhh"
molten hearth
what do walks have to do with loops?
what do loops have to do with anything?
pale epoch
they are important in topological graph theory
i don't see your problem
if you don't need them / don't care about them, consider simple graphs only
they're also important for cayley graphs
molten hearth
i dont see why introductions to graph theory introduce them
crystal dove
Wai
crystal dove
are we talking about redundancy codes?
abstract ravine
coral raven
ah i see
yeah so the 16th is used for the sign
which in this case is 0, ie. positive
abstract ravine
ok but in normal binary
lets say the sign was 1
it would just be a non negative number right?
how do i know if its a sign or not
coral raven
no?
crystal dove
It's based on the number type, and not all number types do it the same way
abstract ravine
ok what is this then 1111
coral raven
yeah
abstract ravine
wdym
pale epoch
you have to know beforehand how your computer encodes numbers
crystal dove
But for hwk there should be some basic assumptions so it's not so complicated
pale epoch
it's not like binary representation is unique
abstract ravine
ahh wait Binary is just for normal numbers right? Computers use binary differently?
coral raven
sure
coral raven
computers use binary for everything
coral raven
they use binary for like letters and things lol
abstract ravine
ik that
pale epoch
the thing is, you want to encode negative numbers too
abstract ravine
yes negative numbners
pale epoch
and if you have 16 bits you can encode 2^16 different values
now if you want to encode as many positive as negative numbers
you can only encode 2^15 positive and 2^15 negative numbers
so its natural to use 1 bit to denote sign and the other 15 bit to denote the actual number
pale epoch
what do you mean get?
coral raven
they're probs not gonna use a sign bit with 4 bits
abstract ravine
i mean as a question
crystal dove
NEVER
pale epoch
there is a difference between what binary numbers in math are and how computers encode numbers
coral raven
they'll tell you when they're using sign bits, it looks like? like they did here
abstract ravine
there is a difference between what binary numbers in math are and how computers ...
THIS
pale epoch
in a computer, you can't really store "1111"
because every number will have 16bit if that is what your computer works with
abstract ravine
ye thats why this chapter is called Computer representation?
its specifically for binarys in computers
in general
right?
pale epoch
yes, this is more practical
crystal dove
Well it's a peek at how number systems might work, but IRL it's much more complicated
pale epoch
as i said with 16 bits you can store 2^16 "things" at most
and if you want to store both positive and negative numbers, you have to think of some encoding
abstract ravine
i see
pale epoch
using a signed bit is one common way
abstract ravine
ok
pale epoch
but like in general
if you just read the info from a bit
you have no idea what was stored there originally
abstract ravine
unless you know how the computer uses binary?
pale epoch
sure, you get 16 bits of data, but it is impossible to decode it to a number (or anything) without knowing how the computer works
ye
abstract ravine
ye so they probably will specify that before asking a question in the exam i guess
pale epoch
yeah
or if you only talk about representation with signed bits, it can be assumed i guess
abstract ravine
ye but they probably will ask specifically
thanks i was confused, its clear now
:d
daring beacon
what does it mean for a graph to have multiple edges?
coral raven
there is more than one line
rugged pebble
weary tiger
How much do I need to pay for complete discretion
candid storm
compute the sum from zero, then take away the first two terms
untold raptor
does anyone know how to do this?
this is what i have rn
but not really sure
the equilvalance relation
ρ ∩ ρ−1is an equivalence relation
this part
not really sure
an equivalence relation is a binary relation that is reflexive, symmetric and transitive.
so do i need to do symmetric ?
ok i see
thanks
severe gazelle
Any discrete math masters have time to tutor? 25$ p/h
severe gazelle
lol
Okay, well I've got my discrete math final on thursday. I need to cram pretty hard
minor dagger
well good luck
severe gazelle
I'm kidding of course
minor dagger
ok ive been asked similar questions before so i dont know anymore
ocean coyote
can anyone point me to something I can read about stars and bars math in detail?
or a text book I may already have
unreal stump
I guess a combinatorics book
amber hill
or a text book I may already have
Brilliant has a great article on it
ocean coyote
looks like the notation is this https://en.wikipedia.org/wiki/Binomial_coefficient
there is a square symbol though. what is that?
weary tiger
would it be weird/wrong to say an undirected graph is a type of directed graph
ocean coyote
I answered my own question. they are just sticking QED squares after every statement in brilliant. weird flex but ok.
minor dagger
ocean coyote
even though I know what the square means, they end with a formula period square. it looks like multiplication square
ocean coyote
balls in boxes seems to be the popular example in old books. then it was balls and urns or stars and bars. they have $\lambda$ as the symbol for partition. not sure if this is a variable or a lambda function here.
vital dewBOT
galois
fluid summit
hi can anybody help me with this. How many ways are there to distribute N indistinguishable objects into k distinguishable bin where each bin was even number of objects?
So I've reached a conclusion that if the even condition is not present there are C(n+k-1, n) but how do I extend this for each bin to have even number of objects?
stray reef
well N itself has to be even otherwise its impossible
and if N is even you can consider this as distributing N/2 pairs of your objects into k bins
@fluid summit
fluid summit
Thank you so much @stray reef
reef thistle
@stray reef idk if that works, I mean, if you put the pairs AB and CD in the same bin, that's indistinguishable from putting AC and BD in the same bin @fluid summit
oh wait
indistinguishable objects
alright you got a point
reef thistle
ah yeah, that I gotten
abstract ravine
I have a question
So i just read something and had an "aha" moment
So in normal Math we can use " - " sign to show negative numbers
but computers dont do that, they have different methods of calculating negative numbers and those methods are:
- Sign-and-magnitude
- Two's complement
- Offset binary
is this correct? so all of these methods are just different ways for a computer could implement in order to calculate negative numbers?
reef thistle
only some negative numbers, but yes, these methods are all used in many programming languages
abstract ravine
yes but i mean like, Sign and magnitude is one method on how to calculate negative numbers and Two's complement is another right?
reef thistle
yeah they can be used to implement negative numbers with a bitstring
abstract ravine
ok i see
abstract ravine
what am i doing wrong here?
im getting different answers
<@&286206848099549185>
drifting sail
you seem to have written $1000_2$, i.e. $7_{10}$ in the substraction; just writing $101_2-011_2$ and carrying as with base $10$ numbers should give you the correct answer, i.e. $10_2$. I don't know the "shortcut method" so I can't say much about that
vital dewBOT
derivada.schwarziana
reef thistle
@abstract ravine you haven't did 5+(-3) yet?
abstract ravine
ye not yet
im just trying to do 2's complement on 0011
preferrebly without the shortcut method
pale epoch
stiff haven
?
abstract ravine
<:JustAsk:371662163489718273>
sorry for pinging you but do you have time to check my question
mint bane
these can all be proven with just contradiction right
my logic for all of them is just to show that if the conclusion were to be false, then that would imply that a doesnt divide b, which is contradiction so the conclusion must be true
but idk if that's too cheesy
ocean coyote
yes but i mean like, Sign and magnitude is one method on how to calculate negati...
you need much more correct definitions for everything. a negative number is atomic, without an operator it does not calculate or perform computation.
all you can do is load and store
if you want to perform an operation (computation) you need at least one field of data but probably you need two. the method depends on the computation and the data.
addition of non-negative numbers was at one time done in binary with cascaded full adders
addition of negative numbers may be implemented as subtraction. subtraction may be implemented as addition of negative numbers. sometime we use an xor mask. there has been a long evolution of VHDL to get to a modern computer. many things have changed.
ocean coyote
this paper gives you everything you want to know in detail in real world modern context
ocean coyote
ye but what about this one
if you know 5 > 3 you can xor to get 2
by xor
yeah ok this one you just xor it but only if the data is in 1's complement
don't listen to me. I guess I need to study more
abstract ravine
no problem bro
ocean coyote
this is it
I don't understand it though. he did addition both times and addition is commutative so he should get the same answer both times
overflow = pos result, no overflow = neg signed resulted????
drifting sail
my logic for all of them is just to show that if the conclusion were to be false...
if the conclusion were to be false that doesn't mean that for all numbers the property is false. It just means that there exists some number or a tuple of numbers that doesn't verify the property
in this case a direct proof is easy for all of these
pale epoch
the k's in each expression might be different
did you cover the chinese remainder theorem?
opal cedar
yes
pale epoch
then use that
pale epoch
what makes you question yourself?
opal cedar
my ability in this class lol
opal cedar
it's okay, thank you for the help 🙂
opal cedar
If a function is onto, does it have to have an inverse?
pale epoch
no
opal cedar
is that true if it's bijective?
mint bane
in this case a direct proof is easy for all of these
how so, at this point my mind defaults to contradiction
opal cedar
I have a function diagram, and the set of its inputs, when they ask what subset corresponds to the function, is that the set of outputs?
drifting sail
how so, at this point my mind defaults to contradiction
use the definition; $a\mid b$ means that for some $k\in \bZ$ we have $b=ka$. All of these properties involve manipulating equalities of that sort by summing them or multiplying by constants, and then choosing another integer (which can e.g. be the sum or product of other integers) to play the role of $k$ in the definition
vital dewBOT
derivada.schwarziana
opal cedar
If I have two integers that aren't relatively prime, can their LCM be prime?
vital dewBOT
slimvesus
opal cedar
oh okay, so if it's any number, there at least exists some case of it
if a can = b
if your two non-relatively prime integers are a, b
or possibly relatively prime, I'm not sure if you proved that
yes
What is the cardinality of the set of all functions with domain B and range A, where both sets A comma B are finite?
is this one just |A|^(|B|)?
so the reverse
|B|^|A|
haughty garden
Try some explicit examples
opal cedar
In modulo 12, how many distinct multiples of 5 are there? Only 2 right?
5 mod 12 = 5, 10 mod 12 = 10?
and maybe 0 mod 12 if you include 0 as a multiple?
haughty garden
What’s 15 mod 12
opal cedar
3
haughty garden
25 mod 12
opal cedar
1
haughty garden
30 mod 12
opal cedar
6
haughty garden
35 mod 12
opal cedar
11
haughty garden
Basically just keep counting up like that
opal cedar
I'm confused
So, like 5 mod 12 = 5, 10 mod 12 = 10, 15 mod 12 = 3, 20 mod 12, = 8, 25 mod 12 = 1, 30 mod 12 = 6, 35 mod 12 = 11, 40 mod 12 = 4, and I keep going until I run out of numbers between 0-11?
haughty garden
Yep
opal cedar
so it'll be 60
haughty garden
It’ll be 12
haughty garden
Well once you hit 60, it becomes 0 mod 12 and so you start the cycle again
opal cedar
number 60
sour arrow
It won't be 12 though, as that would imply 0 is a multiple which it isn't
opal cedar
I thought 0 was a multiple of every number?
haughty garden
5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60 should all be distinct
sour arrow
Oh. Huh. I think I'm a bit lost on the definition here. Don't mind me then.
haughty garden
0 mod 12 is equivalent to 60 mod 12 anyways
haughty garden
So whether you start from 0 or 5, it shouldn’t make a difference
opal cedar
you'd either include 0 or 60 either way
haughty garden
Yep
opal cedar
thanks, that makes a lot more sense
haughty garden
👍
lilac kindle
Hey guys I have a pretty hard (to me) question, I'm translating it to English so I might not get some of the words right. I am not sure if it is the same everywhere but the set (0,1) is this set {x|0<x<1 and x in R}. So I have to find the cardinal of the following set: All the real numbers in the set (0,1) which in their infinite decimal expansion there are only odd digits after the decimal point
minor dagger
what do you think is the correct answer?
try to compose a bijection between the two
and show they have the same caradinality
rough shard
I'm trying to reduce the expresssion (B'+AC)' but I can't work it out. I thought demorgans would make it BA'C' but I did the truth table and they don't work. I've also tried just reasoning about how it could be expressed but none of my ideas worked out.
Oh wait maybe it becomes B(A+C)'
no because B(A+C)' = BA'C'
rough shard
wow BA'C' worked the whole time
rancid stone
So I’m working on recurrence relations, and I’m not sure really to start with this problem, I’m just kind of confused cus of the multiple n’s, can someone explain to start it up, then I could probably figure it out
Here’s a pic
its problem e
opaque fern
I need help solving this
opaque fern
@crimson jetty I asked you for some assistance with bezout theorem a few weeks ago
Can you assist me for a sec
It’s with my calc
olive hamlet
taco usually has this server muted, you should DM her
rancid stone
I still need some help with recurrence relations, is anyone able to?
gusty crag
I still need some help with recurrence relations, is anyone able to?
it looks like to solve e you would just need to find a_{n-1} and a_{n-2} and check if an = 8a_{n-1}-16a_{n-2}
for example, with c, a(n-1) = 2^(n-1), a(n-2)=2^(n-2), so if that's a solution to the recurrence, we would have 2^n=8x2^(n-1)-16x2^(n-2)
the right side is equal to 2^(n+2)-2^(n+2)=0 so that is not a solution to the recurrence
so you can do the same thing with e
haughty garden
If you've ever touched ODEs, the approach is identical
haughty garden
You can explicitly find your solutions; this is a homogeneous recurrence relation
rancid stone
So e would be a solution right?
haughty garden
Yep
rancid stone
And I kind of learned it but that’s for the next part
rancid stone
I’m still a little confused by it
But
If u can help, I do need help with a harder problme
haughty garden
So the form of any solution of a recurrence relation will be of the form a[n] = A x^n
If we directly substitute that into our recurrence relation, we get:
rancid stone
And I believe I did that in my work that I posted above
But this one has really got me
And I am totally stuck
I just don’t know exactly to set it up
It’s part c
The roots are really long and annoying
So I’m not sure
haughty garden
Yeah it looks a bit tedious
The process is the same I believe (never dealt with n - 3 lmao)
You end up with something like x^3 - 2x^2 - 5x + 6 = 0.
A trick with solving roots of cubics is probably using product / sum of roots
Factoring 6, we test out x = 1, -1, 2, -2, 3, -3, 6, -6 and realise that x = 3, x = 1, x = -2 give you the roots
So then you have a[n] = A 3^n + B 1^n + C (-2)^n and then finally just plug in initial values to get A, B, and C
rancid stone
Okay hold on I’ll try it rn
Do you have a way of showing it out or a video explaining it, I need some sort of visual representation
@haughty garden
haughty garden
you can probably look up 'solving recurrence relations' on YouTube and there should be a few videos lying somewhere
gusty crag
Do you have a way of showing it out or a video explaining it, I need some sort o...
if you're cool with a book's explanation, kenneth rosen's discrete mathematics and its applications covers the general case of solving linear recurrences in section 8.2
it covers the general case and provides some decent worked examples
abstract ravine
-1873.42
if i convert the .42 to binary
will it just keep repeating?
can someone try this?
stray reef
0.42 will have an infinite binary expansion, yes.
are you converting this to floating point or sth
abstract ravine
yes i am
stray reef
how many bits of exponent and how many bits of mantissa
stray reef
lemme doublecheck that
ok
so the exponent is (decimal)10
your mantissa will be 1101010001.............
the dots are the binary expansion of 0.42
truncated obv
stray reef
??
you wouldnt treat dyadic vs non-dyadic fractions any different
convert to binary regardless, and truncate if necessary
abstract ravine
yes but the "truncate if necessary" means if it isnt repeating i have to show them on the mantissa
no?
stray reef
if your binary expansion terminates you fill the rest with 0s
stray reef
do you not know how to convert a decimal to binary
hrrgh
i have no idea how to explain this coherently
elfin flume
How can I count the faces on this accurately
(I’m trying to figure out if it’s planar)
elfin flume
Sorry but what about this graph? For this one does rearranging the vertices work best?
stray reef
pulling blizzard and google up and andrei down should untangle it
elfin flume
Do these seem alright?
Also just wondering, is it always the case that the highest degree in a graph's vertices is the chromatic index or not always?
mystic moss
@elfin flume https://en.wikipedia.org/wiki/Vizing's_theorem
stray reef
wrong channel, and also who the hell are you and why are you pinging me
ocean coyote
convert to binary regardless, and truncate if necessary
you can predict that by checking if it is in some set
remote dock
what function this gives you?
ocean coyote
@remote dock this is really easy if you use the truth tables
start with each block as one truth table
remote dock
yea I calculated it just not sure about my ans
ocean coyote
when you get the table for F look at a dictionary of truth tables to find what logic does that
super easy
remote dock
remind me how this system is called?
ocean coyote
does that help?
you take the Q1 and Q2 outs then relabel them as A, B
then find the truth table for Q3
then compare to existing truth tables on this website
compared to A,B,Q3
remote dock
thanks a lot
ocean coyote
you can also do it by composition of boolean algebra
floral widget
Hi guys how much is this ? 1260 or 35 ?
7!/4!*(7-4)!
ocean coyote
obtuse lance
you should be able to do 7!/(4!3!) by hand, take the largest factorial in the denominator and cancel out terms with the one in the numerator
7!/4! = 7*6*5 then divide by 3!
ocean coyote
@remote dock I worked it out on paper. the answer is that this entire circuit in total passes A to the output.
B is ignored
the state of input B does not have any affect on the output state.
coral raven
it's a trap, @obtuse lance
it's order of operations again
7!/(4! * 3!) = 35
(7!/4!)*3! = 1260
obtuse lance
whatever
obtuse lance
it's obvious the person who wrote it just is bad at putting parenthesis correctly on their binomial coefficient
anything else is bad faith and a waste of time
coral raven
i wasn't saying it was a deliberate trap
but it's a trap nonetheless
best to explain the weirdness in full as fast as possible and disarm it
coral raven
yeah ok
ocean coyote
its caught in a loop! its drawing more and more power from the system!
abstract ravine
Hey guys
so
im studying Euclidian algorithm
ngl, getting kinda confused it feels like everyone on youtube is implementing it in a different way
im trying to follow our book
since u never know
anyways
kinda having a hard time understanding this
abstract ravine
<@&286206848099549185>
quaint mirage
Can someone help me with this please ?
round geyser
Are there any connections betweenn topology and graph theory
or topology and and like combinatorics
sour arrow
Sure, many. You'll have to be more specific, haha
Mathematicians are very good at connecting all the structures together
weary tiger
I am in class 8 th class topper
sour arrow
Well, maybe not combinatorics idunno but topology is everywhere
weary tiger
:)
last sigil
Yes
I've been told topological combinatorics exists
And topology does have graph theory connections
north stone
fuck you
weary tiger
What the fuck?!
burnt escarp
when i am doing proofs, am i expected to write out the exact reason how i arrived at the "next line" for every single line?
Even if it's obvious what i did (aka rearrange, simplify (a+b)^2 to a^2 + 2ab + b^2, etc.)
minor dagger
you can write something like "By algebra"
depends on your professor
just try to be rigorous as possible
but you dont need to write like "by commutativity" every time lol
burnt escarp
Makes sense
minor dagger
im sure you see a lot of things like "obviously" in your textbooks
its best to stay away from that at first
vernal flame
foggy iron
randomly select a ball, see the color of it and put it back in the bag. You keep doing this
repeatedly.
a. What is the probability that you get the first red ball on the 5th turn?
b. How many turns are expected to get one non-white ball?
c. What is the variance of the number of turns required to get one blue ball?```B and C
help me
abstract ravine
This is Dophanite equation
im confused on where the (4) came from?
in the last step
last sigil
I'm confused what is the original problem
abstract ravine
ahh fk nvm im stupid
i understand where it came from
its a dophantine equation
last sigil
abstract ravine
ye
abstract ravine
got a question
k = a div b
lets say i have this equation: 70x +90y = 10
i know the answer but just to make sure
a is always the larger number
so in this case a = 90
?
last timber
you do not need to have a as larger number
but yes
i mean both cases should reduce to the same res
,w gcd(70,90)
vital dewBOT
last timber
,w gcd(90,70)
vital dewBOT
abstract ravine
you do not need to have a as larger number
if 90 is not a then K = a div b would end up being 0.77
last timber
how
in euclidean algo you do not use any div except integer one
90 = 70*1+20 and
70 = 0*90+20
crystal dove
const gcd2 = (a, b) => b === 0 ? a : gcd2(b, a % b)
Where % is the remainder operator
abstract ravine
ye lol that makes sense
ok but what does this mean
If c = gcd(a,b) then there exists x,y integers
c = gcd(a,b)
how will i be able to tell if a dophanite equation i solvable or not?
abstract ravine
??
ok as an example 70x + 90y = 10
is this equation solvable?
i am supposed to know beforehand
<@&286206848099549185>
bruh i should start asking my questions in the #help-1 channel lol :d
rain stone
@abstract ravine the equation ax + by = c has a solution over the integers iff the gcd of a and b divides c. In this case, the gcd of 70 and 90 is 10, so this will have a solution, because 10 divides 10
abstract ravine
ahh wait so if 70/10 and 90/10
then there is an integer solution?
if c|a & c|b
@rain stone
rain stone
nope, that's not enough. 1|70 and 1|90, but 70x + 90y = 1 has no solution
100 does not divide 70
100 does not divide 90
but 70x + 90y = 100 does have a solution
the condition I listed is the exact one
gcd(a, b)|c implies a solution exists
abstract ravine
but how can i tell beforehand without solving it first to know if there are any solutions?
raven python
gcd(a,b)|c <=> ax+by = c has at least one solution in x,y \in Z
abstract ravine
yes so its the solution of gcd
raven python
what do you mean?
abstract ravine
nvm i understand what you mean
aaaaaaaaaaaaaaaaaaaaaaaaah now i get it
so first i need to find the gcd of a and b
then i need to divide the gcd with c
to know
if the equation does have integer solutions?
raven python
You have to check if c is divisible by gcd(a,b). If it is, then the equation ax+by=c has at least one solution in integer numbers
abstract ravine
ok wait lets say 10x + 15y = 25
gcd(10,15) = 5
5|25
= 5
so yes, the equation does have a solution
right?
raven python
yeah
You can prove that it always works analysing the equation
ax + by = c
where a and b are coprime numbers
raven python
Just keep in mind it doesn't guarantee the solution (x, y) will be a pair of natural numbers. They'll be just integers
abstract ravine
yes