discrete-math

[ember obsidian]

can u first answer what the size of AUB is?

[misty elk]

AUB has size n+m

i dont know where to begin

[silent hinge]

Hello Troposhere, can you give me a hint for this problem "There exists a set that contains {a,b,c} as a subset but is not equal to {a, b, c}."

@coral parcel

thank you in advance

is it like saying

{{a,b,c},1,6,<>} != {a,b,c}

[gritty crescent]

This is correct.

<> is a weird choice for an element though

Oh wait

You shouldn't have {a,b,c} as an element in your given set

Rather, you should have a, b, c as elements in your set

So that {a,b,c} becomes a subset of your given set

[silent hinge]

i see where you going but its saying that theres a set already with set {a,b,c} inside of it

but is not equal

askdklds haaahh im confused, ill have to take a look at my notes and see

[coral parcel]

For example, {a,b,c,7,8,9,10} contains {a,b,c} as a subset but doesn't equal {a,b,c}.

[loud carbon]

not gonna bother retyping

[weary tiger]

How did that step turn into that

[stray reef]

this is a well-known formula

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

look up triangular numbers if you want to get more info about it

[tidal tulip]

why can’t Z (which i assume here is a set of integers) be an element of Z?

[stray reef]

no set is an element of itself

[tidal tulip]

k

[coral parcel]

Even more fundamentally, Z is by definition the set whose elements are every integer but nothing that isn't an integer is an element of Z. Since Z itself is not an integer (a set containing integers is not the same as an integer), it doesn't satisfy the condition for being an element of Z.

[tidal tulip]

ahhh i see

that helps ty

[valid wave]

idk if this is out of realm

but

what is Q x E referring to

the range of Q x E is Q?

[ember obsidian]

@valid wave its a function delta with domain QxE and codomain Q

QxE likely means the cartesian product of Q & E

[stray reef]

that's not an E

[ember obsidian]

'lazy' sigma

[valid wave]

We are aware 😭

[valid wave]

Codomain = range?

[ember obsidian]

no

codomain=set of possible outputs, range (image)=set of outputs

[coral parcel]

So it's a function that takes a state and an input symbol, and produces a new state.

[valid wave]

hm ok i rgink im following

so codomain in this case is the cartesian product of QxE

the possible outputs we get from QxE

[coral parcel]

No, Q×Sigma is the domain: the set of possible inputs to the function.

[valid wave]

inputs to the function Q

[coral parcel]

Q is not a function/

[valid wave]

so what is this portion denoting

[coral parcel]

The function is called delta.

You can give an element of Q×Sigma (that is a pair of a state and a symbol) as input to the function.

It will then spit out an element of Q (that is, a new state).

[valid wave]

ahhhhhhhhhhhhhhh

gotcha

so like delta(QxSigma) = Q

also how did you know Q referred to a state 😳

[coral parcel]

well almost but not quite.

[valid wave]

previous experience?

[coral parcel]

The word "transition function" plus the location in #discrete-math made me guess you're reading about finite automata.

Q is the name of the set of all possible states.

Sigma is the name of the set of all possible input symbols.

Each time you apply the function delta, you give it one state and one input symbol, and it then tells you the one state the automaton will be in after reading the symbol.

[ember obsidian]

it seems mary is unfamiliar with the formal def of function, maybe itd be good to cover that

[valid wave]

ok 🙏

will recheck

[valid wave]

i wanna be at this level of understanding of math

big brained like you 😦

[coral parcel]

That is just an effect of having seen the particular topic before.

[valid wave]

got it, this makes alot of sense

[ember obsidian]

the formal def relies on knowing what a cartesian product is, so see that too

[valid wave]

do you have a career in math?

this makes alot more sense now thank you!

[coral parcel]

Math is just a hobby. But I am a computer scientist, and automata theory belongs to us too ...

[valid wave]

knew it

ok because i was wondering in what realm someone would be reading up in finite automata without being CS

[valid wave]

i wanna be a computer scientist, but theres so much money in just software engineering 😦

do you mind if i DM you a couple questions @coral parcel

[coral parcel]

Please stick to the channels.

[valid wave]

no like about careers

but thanks for the help 🙏

[stray reef]

just curious

is this sipser

[valid wave]

yes

😳

[vale panther]

Can anyone help?

[coral parcel]

https://dontasktoask.com/

[floral cliff]

Question: For every (x, y) ∈ R ✕ R, (x, y) ∈ S means that x ≥ y. Is (-1) S (-2) ? What does the S mean, what is the question Is (-1) S (-2) asking in this case ?

[cerulean wind]

aRb is another way of saying (a,b) in R

[floral cliff]

can someone help me with logical form and logical equivalence hw ?

I have no clue whats going on

[weary tiger]

Why is the well-ordering principle the same thing as induction?

I thought that you used the well-ordering principle in induction, but it wasn't the same thing

[shell lagoon]

do I start with

ths

[weary tiger]

Would someone be able to help me with a strong induction exmaple in voice

because I'm really confused about the intuition behind picking the number of base cases

this the example!

[coral parcel]

Suppose we want to prove forall n: p(n) by induction, but after we've proved the base case an inductions step we change our minds and want to use well-ordering instead. We can then do an indirect proof: Suppose for a contradiction that there are one or more n that p(n) doesn't hold for -- that is, {n in N | ~p(n)} is not empty. By the well-ordering principle it must have a smallest element m. But m cannot be 0, because we know p(0) already. On the other hand, if m is not 0, then p(m-1) is true, because m is the smallest number it is not true. But then the induction step we have already proved tells us that p(m) is true too, which is a contradiction.

On the other hand, we can also get well-ordering from induction:
To prove: If A is a non-empty set of natural numbers, then A has a smallest element.
Lemma: Let k be a natural number and assume k in A. Then A has a smallest element.
Proof by long induction on k. We assume that the lemma is already true for all numbers smaller than k, and we're further assuming k in A. Now either A has an element smaller than k or it doesn't. If A has some element that is smaller than k, then the induction hypothesis tells us that there's a smallest element and we're done. On the other hand if A doesn't have an element smaller than k, then by definition k is a smallest element in A, and we're done again.
Proof of the main statement. Since A is non-empty, it has some element which we can call k. The Lemma then tells us that A has a smallest element.

So the principles are "the same" in the sense that they can be proved from each other, and they really express the same underlying property of the natural numbers just viewed from slightly different perspectives.

[stray reef]

@coral parcel don't you need LEM to say induction and WOP are equivalent?

[coral parcel]

Possibly, but in #discrete-math I think we can safely assume we're working in mainstream math, with classical logic and choice and all the usual bells and whistles.

[stray reef]

n/c does not strike me as the type of person who would take LEM for granted.

[tired moat]

Noob to combinatorics here. Does this look correct?

[stray reef]

(b) should be $\binom{20}{1,2,3,4,10}$

[vital dew]

Ann

[tired moat]

You're right thanks. I had the wrong definition of multinomial symbol in my mind. Thought the ((20-1-2-3-4)!) term appears in denominator automatically

[coral parcel]

That would be more consistent with the binomial coefficient notation, yes. Perhaps leaving a term out of the multinomial coefficient feels like there's a larger risk of misunderstandings, since it's not unambiguous how many there should be.

[tired moat]

One more from combinatorics: Would you say this recurrence relation is good enough or is it possible to make it easier?

And is there a way to solve these recurrences nicely? I know there is a power law ansatz if you have just one variable.

The way I solved this recurrence is to write $(a_n,b_n)^T = A (a_{n-1}, b_{n-1})^T$, where A is a suitable matrix and then calculating n-th power of the matrix by diagonalizing it. Which works but maybe it can be done simpler/with less work?

[vital dew]

Faputa

[muted socket]

Gentlemen, if we have $A \subset B \subset X$, then is it always true that $A \cap X \subset B \cap X$?

[vital dew]

strad

[pale epoch]

A \cap X is just A and B \cap X is just B

[muted socket]

Oh bad example then

Okay, I'll ask more specifically

If we have $G \subset X$, $Y \subset X$ and $B \subset G$, then is it true that $B \cap Y \subset G \cap Y$?

[vital dew]

strad

[muted socket]

Is it always* true?

[pale epoch]

yes

[muted socket]

Got it, thanks loch

[zenith oyster]

How do i calculate this effectively without calculator?

nvm found a way

[tranquil vector]

what is the output as a function of n?

[coral parcel]

Do you have a guess? A table of values for small n that could suggest patterns?

[tranquil vector]

I tried using python but it gave me a recursion limit error

and if I do n=3 wouldn't dividing by 2 give me 1.5

and then 0.75

[zenith oyster]

use // in python for integer division

[coral parcel]

I would guess n/2 is intended to be interpreted as integer division, ie rounding the quotient down to an integer.

[tranquil vector]

ah i misread the question

[valid wave]

Hello

[severe swan]

can someone explain how to do this?

Give a counterexample which proves the statement is false over the domain of real numbers.

∀x((x+2)2 ≠(x−8)2)

[coral parcel]

Are you sure the statement is not instead this: ∀x((x+2)² ≠(x−8)²)

[severe swan]

You are right. I wrote it wrong.

[coral parcel]

Do you understand what the idea of a counterexample means here?

[weary tiger]

Hello,
i have another question about sine.

https://math.stackexchange.com/questions/1339540/why-does-the-derivative-of-sine-only-work-for-radians

[valid wave]

anyone happen to know how all finite languages are regular?

[weary tiger]

If i say:
Radian = tau
What is the value of sine ?
So the value of sine depend on radian.
Radian which is for scientist a derrivated unit.

Houston we have problem

[pale epoch]

just build a DFA that accepts only one word and then show that the finite union of regular languages is regular

[pale epoch]

what does "radian = tau" mean

[valid wave]

so just making sure im understanding. If have some regular language A1 that is recognized by some M1

I can make some NDFA M2 that is the union of A1 and some A2 that represents the rest of this finite language

and since union is regular

it works?

[pale epoch]

the union of regular languages is regular

if you have some (N)DFA accepting language 1 and one accepting language 2, you can build one that accepts the union

i dont know the construction off the top of my head

anyways, then you only have to build finitely many (N)DFAS that each accept precisely a single word

and apply the union construction finitely many times

[valid wave]

gotcha

do you happen to have a formal proof / drawing of this

really interesting

[valid wave]

couldnt i just do it 2 times though

split the finite language by 2 string S1 S2

prove string 1 is regular, and srting 2 is regular

then union is regular so we are good

am i missing something?

[pale epoch]

huh?

a finite language consists of finitely many strings

how do you split that in a way that you can easily see that your "parts" are regular

[valid wave]

ig my thinking was that, if we take the finite language and split it. We can split it in anyway into some S1 and S2

if we make 2 DFAs for these machines that make

S1 and S2 regular

we can then do union of these DFAs

[pale epoch]

sure but you need a way to see that S1 and S2 are regular

i mean essentially this is induction

[valid wave]

ah gotcha

[pale epoch]

you show that the union of regular languages is regular

[valid wave]

it being induction makes me understand

[pale epoch]

and then by induction you immediately get that finite unions are regular

[valid wave]

gotta prove the first step (1 letter)

then the rest builds

[pale epoch]

the way you show that the union of regular languages is regular is quite iffy i think

also i dont have a source

[valid wave]

last thing, how does one prove that the single word is regular then

[pale epoch]

you will have to try google

[valid wave]

couldnt that same thinking just be extended

to some S1 and S2 of the finite

[valid wave]

appreciate the help though!

[pale epoch]

you can just write down a DFA that accepts a single word quite easily

states for each letter

then the end state is accepting

but any more letters, go into unleavable fail states

[valid wave]

wouldnt this be hard with a DFA? with a NDFA i can see this being very easy

[pale epoch]

i dont quite recall the difference

but i think you can have 'trap states' in a DFA

[haughty garden]

NFA is an automaton that allows the machine to “guess” which transition to use

[pale epoch]

and thats really all you need

[haughty garden]

So you can take multiple paths in an NFA and if any path ends in an accept state when read all of the input, the input string is accepted

[pale epoch]

oh right

the transition functions maps into powerset

i dont think you need this though

this accepts only a_1a_2\dotsa_n

[tidal tulip]

would proving that primes are infinite by contradiction be a special case of the proof for the following lemma: suppose M in N and M = n+1. if n | s and n != +/- 1, then n does not divide M

where n=p1 * p2 *… *pn (in the primes proof)

[sleek mural]

How to do part b????

[pale epoch]

what is s

[pale epoch]

this should be in like #prealg-and-algebra or a help channel

[sleek mural]

Ok thanks!

[tidal tulip]

let me rewrite i might have mixed up my variables

[pale epoch]

you just want to write down the fact that if n divides k, it does not divide k+1 unless n = +-1

[tidal tulip]

yeah

[pale epoch]

every nth number is divisible by n after all

[tidal tulip]

isn’t the proof of the primes are inf a special case of that proof though

[pale epoch]

i wouldnt say so

[tidal tulip]

because here n is the product of all the “finite primes”

[pale epoch]

its an ingredient of the proof

[tidal tulip]

ok

[pale epoch]

but the key part is euclid's lemma

if a prime divides a product, it divides one of the factors

[tidal tulip]

yeah

[pale epoch]

you need to pass what?

this isn't really how this server works

we do not help with graded tests

and i don't want to work under time pressure

generally you would spend some time with the question

and then share what you tried

[valid wave]

lol

[tidal tulip]

would the proof work for this lemma

lemma: suppose M in N, and M=n+1. then if s | n and s != +/- 1 then s does not divide M.

proof: by contradiction suppose M in Z and M=n+1 and suppose s != 1. if s|n then s | M,

then there there exist a k in N such that

n+1 = sk

since s | n there exist a j in Z such that

n = sj

then by substitution

sj + 1 = sk

1 = sk - sj

1 = s(k-j)

thus s | 1 but this is a contradiction since s != 1

therefore if s | n then s does not divide M

@pale epoch

[pale epoch]

seems to work, yes

[tidal tulip]

k

i’m kind of confused now to set up a contradiction proof do i just restate the if then statement where the conclusion is the thing i want to contradict

if s | n then s | M then this means ….

like i did above

like i go ahead and assume that if, then statement is true and see how i get a false conclusion?

[pale epoch]

you dont have to do this with contradiction at all

[tidal tulip]

how else can you do it

[pale epoch]

you can just do what you did assuming that s divides n and n+1

then you get to 1 = s(k-j)

this is only possible for s = +-1

[tidal tulip]

ok

cool

but let’s say in general i want to prove P -> Q is true by a contradiction

how do i do that

just the general form

[pale epoch]

you assume P and not Q

and derive a contradiction

[tidal tulip]

~(P -> Q) = ~(~P or Q) = ~~P and ~Q = P and ~ Q

is how you derived that?

[pale epoch]

yes

[tidal tulip]

k that makes sense

ty

[pale epoch]

and if you show that is false, then p -> q must be true

[tidal tulip]

k

[cunning girder]

Hey, does anyone know why this statement is true?

∀a∀b (∀c (a|bc) → a|b)

I found a counter-example but the given solution says that it's always true

If a = 2, b = 3 and c = 4

we have a|bc = true but a|b = false

[ember obsidian]

ur counterexample works, the solution is wrong

[cunning girder]

Thank you, I was so confused

This is their justification:

By the hypothesis, we know that for all integers c, a|bc. So we can take c = 1.
We get a|(b · 1), in other words a|b.

which works only if c = 1

[ember obsidian]

man ambiguous grouping of quantifiers

[cunning girder]

yeah

[ember obsidian]

i read the statement as forall a,b,c (..)

so this is actually true, and the solution's proof is valid

but "∀c (a|bc)" should be in brackets to emphasize that the 'scope' of c goes only as far as the statement a|bc

[coral parcel]

I think it makes sense as written, but the space between ∀c and the opening bracket throws off the eye.

Unfortunately punctuation and bracketing in connection with quantifiers is a mess.

[cunning girder]

Oh hang on

[coral parcel]

Even though each author usually manages to stay true to one convention in their own work, there are mutually incompatible conventions in active use.

[cunning girder]

I wrote it down as ∀a∀b∀c

so if it were ∀a∀b∀c, my couter-example would work, correct?

[coral parcel]

Correct.

[ember obsidian]

ye

[cunning girder]

Do you mind explaining what the difference between ∀a∀b∀c and ∀a∀b(∀c) is?

[coral parcel]

It was supposed to be read ∀a∀b ( [ ∀c (a|bc) ] → a|b)

So the ∀c is inside the left operand to the → rather than the → being inside the scope of ∀c.

[cunning girder]

Right but what's the difference between that and ∀a∀b∀c ( (a|bc) → a|b)

in terms of logic

[ember obsidian]

in the first version the scope of c includes "a|bc"

in the second it includes the implication "if a|bc then a|b"

[coral parcel]

The position of the ∀c determines who gets to choose the value of c: Either the person who is proving the claim or the opponent who tries to shoot down the proof.

If you're proving ∀a∀b∀c(.....) then your proof need to work with any random a,b,c your enemy chooses.

[cunning girder]

oh

That makes more sense, yeah

Perfect, thanks!

[coral parcel]

However when you're proving "[∀c(...)] -> something" then it's your enemy that is responsible for ∀c(...) being true, so then you get to choose one or more c's to throw at him.

[ember obsidian]

also just making sure, is the solution's proof clear?

[cunning girder]

yeah so they chose c = 1

so assuming that a|bc is true

a|b would be true by default

[ember obsidian]

true for all c, so in particular its true for c=1

[cunning girder]

right

but what if c wasn't 1

let's say c was 3

oh my

hang on

[ember obsidian]

in particular its also true for c=3

[cunning girder]

i think its much clearer now

yeah

so

[ember obsidian]

so a|3b is true

[cunning girder]

a | 3b

yep

[ember obsidian]

but thats not the conclusion we want

[cunning girder]

and since 3b is divisible by a, then so is b

hm

[ember obsidian]

we want a|b

[cunning girder]

thats true

[ember obsidian]

not necessarily

[cunning girder]

yeah scratch that lol

but you're right, we want a|b

and to get a|b we have to pick c = 1

[ember obsidian]

ye

[cunning girder]

awesome, thanks

i had never seen an instance of this specific type of problem before

so it kind of took me by surprise

[nocturne blade]

Has anyone here worked through “The DFT: An Owner’s Manual” By Briggs?

[valid wave]

couldnt i just make the formal definition for A and B

then union

then prove regularity under union?

if im thinking about this right, i feel so big brained rn 😳

[waxen spire]

what is the end of this equation saying, 3a^2 + 7b^2 is congruent to 0 mod 4? that makes no sense

is this just saying that (3a^2 + 7b^2) % 4 == 0?

[olive condor]

Ya, 0 mod 4 is the mathematical way of saying that…

[waxen spire]

i was raised in cs

[olive condor]

Cause this is not programming though 🤷‍♂️

[iron hearth]

What is this question asking me to do

[stray reef]

@iron hearth are you still here and do you still need help with this?

[minor zephyr]

im confused. In what sense is the "class of regular languages closed under complement?" What this problem seems to show instead is that: given a regular language L, X \ L is a regular language where X is the set of all strings on a fixed alphabet. But X is not the same thing as the class of all languages, right?

[stray reef]

yes

the class of regular languages is closed under complement, meaning that the complement of a regular language is also a regular language.

$L \in \mathrm{REG} \implies \Sigma^* \setminus L \in \mathrm{REG}$

[vital dew]

Ann

[minor zephyr]

wait yea, okay it makes sense now. I thought maybe they were using closure in a way im not used to

[wide vine]

Just want to make sure I did this correct. The trip was neither cancelled or delayed.
p : The weather is bad.
q : The trip is cancelled.
r: The trip is delayed

$\lnot (q \lor r)$

[vital dew]

Brandon7716

[wide vine]

This is logically correct, right?

[coral parcel]

Yeah.

[wide vine]

is it good practice to split up your truth tables

like um

$p \land (\lnot p \lor q)$

[vital dew]

Brandon7716

[wide vine]

should I do

$p$ ,$q$, $(\lnot p \lor q)$, $p \land (\lnot p \lor q)$

[vital dew]

Brandon7716

[craggy juniper]

yeah

i think people would add a column for not p

[wide vine]

latex tables struggle

[wide vine]

well that is NOT happening .....

i think they can figure that one out

[craggy juniper]

grrrrrrrrrrrrrrrrrrrrr

[wide vine]

😭

[craggy juniper]

yeah

that’s fine

[wide vine]

this is messy 😦

[inner beacon]

Trying to express a compound statement, how do I deal with "but"? i.e "John is healthy and wealthy but not wise" h = john is healthy, w= john is wealthy s = john is wise

(h^w)~s?

[coral parcel]

"but" is just an opinionated way of saying "and".

[inner beacon]

ah okay, so (h^w)V~s ?

idk latex

[coral parcel]

No, that's an "or".

[inner beacon]

^*

(h^w)^~s

[coral parcel]

Yeah.

[inner beacon]

I get them mixed up haha

sweet thanks

[weary tiger]

How to calculate the logarithm of numbers quickly?

[inner beacon]

"n is odd" and ''n is not even' are logically equivalent, but what is the justification for that?

it feels like negation but is changing odd/even okay?

or how about "n is odd" and "n is even". These are different statements but what would you call that?

[coral parcel]

Use a calculator. If you don't have a calculator, hope you have a book of logarithm tables.

[coral parcel]

Depends on your definitions of "odd" and "even", but if they are not too bizarre, it should be simple to prove "n is either odd and not even, or it is even and not odd" by induction on n.

[inner beacon]

interesting, is there a definition of odd/even that is not the traditional definition?

Mine would be n/2 = Z

n/2 is an element of Z

[coral parcel]

For one thing one could either define "n is odd" to mean "n is not even" (in which case there's almost nothing to prove), or define "n is odd" as "there exists k such that n = k+k+1", and I would say both of these are fairly tranditional.

These definitions are not necessarily the same if interpreted in a different domain than the natural numbers. For example if the domain is the real numbers, then nothing would be odd by the first definition, but everything would be odd by the second. And if the domain is all polynomials with integer coefficients, then by the second definition there would be elements that are neither odd nor even, such as 3X+1.

[tranquil vector]

Determine the output of Bar as a function of n

does n^2-1 count as a function of n

$n^2-1$

[vital dew]

arcuzie

[inner beacon]

That's pretty cool. Thanks👍

[coral parcel]

n²-1 is definitely a function of n.

It's not the function computed by your Bar, though -- they differ even for n=1.

[tranquil vector]

is it not

in our case n is a factor of 2

[coral parcel]

Your function returns 1 when n=1, but 1²-1=0.

[tranquil vector]

oh you're right

[coral parcel]

I could easier believe in 2n-1

[tranquil vector]

That's what I had before I changed it for some reason

okay thanks

[coral parcel]

But I'm not convinced of that either.

Hey, where did the mystery function go? 😵‍💫

Don't randomly delete posts, please.

[ember obsidian]

Bar(n):
  if n = 1 then return 1
  x = Bar(n/2)
  return n+x

@tranquil vector pls dont delete posts

[iron hearth]

Yea i do sorry for the late reply

[inner beacon]

∃ a movie m such that m is over 6 hours long negated is ∀ movie m, m is less than 6 hours long ?

Trying to wrap my head around negation and it's giving me mush brain

[ember obsidian]

almost

the negation of $x>6$ is $x\le6$

[vital dew]

RokabeJintaro

[inner beacon]

ahh of course thanks

∀ movie m, m is less than or equal to 6 hours long then

[ember obsidian]

yes

[weary tiger]

how do you find the total number of nodes given that each internal node must have 9 children and there are 11 leaves?

[severe swan]

How can I find out which are true over real numbers? A = upside down A and E = flipped E

P(x) = x > 20

Q(x) = x < 70

I tested it with 1/2 and -1/2

Ax P(x) V Ax ~P(x)

(1/2) > 20 False
(-1/2) > 20 False

Ax P(x) V ~ExQ(x)

(1/2) > 20 V ~(1/2) < 70
1/2>20 F and ~1/2<70 T

Ax(p(x) V Q(x))

(1/2) > 10 V (1/2) < 70
F and T

[weak sierra]

The Food court plan of a multi-national company shown below here. Construct a graph model defining suitable vertex set and edge set. Is it possible to walk through and around this building passing through each doorway exactly once?
Image below

Can someone please help with this?

I've been stuck with it

[cunning locust]

Can somebody help me with this?

[gritty crescent]

What's the question?

[cunning locust]

If the whole proposition is true or false. I think its false because one of the roots could be negative. The domain of discourse is R.

$y= \sqrt{9 - x^2}$

[vital dew]

Sisyphus

[gritty crescent]

Well, that still gives you a root

But the statement is nevertheless false for a reason.
Hint: ||what happens when x>3?||

[hoary cloak]

what are you finding difficult about it?

intuitively you can make the rooms vertices and the doors edges

the rest is basically solving an eulerian trail problem

[weary tiger]

In how many ways can the tiles be drawn so that they spell Mississippi in the order they are pulled from the bag?

the bag only contains tiles that make up the word Mississippi

im not sure how to go about this problem

[coral parcel]

You need to choose an order to draw the four I's in, an order to draw the four S's in, an an order to draw the two P's in.

[weary tiger]

“1 * 4 * 4 *2”

?

@coral parcel

1+ 4 * 4 *2

[coral parcel]

Are there just 4 orders you can draw the four I tiles in?

[weary tiger]

No

[weary tiger]

Factorial 4

[coral parcel]

Yes.

[weary tiger]

1! 4! 4! 2!

?

[coral parcel]

Yes.

[weary tiger]

Thank you!

🙏

[weary tiger]

https://gyazo.com/80af0efe127b8e0ccd84c98c5c4cdb11

how does the 2nd line of base case go to the 3rd line?

[coral parcel]

It looks like the hat-delta there might be part of a detailed formalism about defining the meaning of finite automata. However, the details of those formalism are specific from book to book, so you can't assume people reading here knows the precise definitions you're working with well enough to answer that question.

[weary tiger]

nvm I got it, it was from the defn

I get the first defn from my prof but the 2nd one is from the internet. Which one is correct?

[coral parcel]

They are equivalent.

[weary tiger]

So I can use either one yea?

[coral parcel]

They give the same results, but if you're writing concrete proofs that's supposed to be based on one of them, you should use that (or make sure you have proof of the equivalence).

[weary tiger]

,rotate

[weary tiger]

https://gyazo.com/097f5e9c4012a8325121624ee54b5b56

Is my dfa correct?

[weary tiger]

thx

https://gyazo.com/47198e0c68b7684bd90952f5e250362c

[coral parcel]

Looks fair, though an alternative interpretation of (a) might be that whenever you see an a there just have to be a b somewhere later in the string.

[weary tiger]

I added a route for a in q1

[coral parcel]

(And between your various photos you now have both interpretations covered :-p)

[weary tiger]

Is this how I do product machine for C?

Should have a different letter for the states lol

[coral parcel]

Looks good too, except you've forgotten to mark the accepting state(s).

[weary tiger]

Right, I'm still figuring out how to figure out the final states

[coral parcel]

You want to accept iff both of the two original machines like the string they've seen.

[weary tiger]

Circled all states with q0

and q2

q0 for a)

q2 for b)

[coral parcel]

That sounds like you're getting a union, not an intersection of the languages.

[weary tiger]

Yes

product machine is union

no?

[coral parcel]

The construction can be used either for union or for intersection, but here you're asked to accept only strings that satisfy both of the conditions.

[weary tiger]

oh

so only

q0q2

yes?

[coral parcel]

Right.

[weary tiger]

gotcha

https://gyazo.com/de53b9abec40119d5bae4cd1dacfe40b

how should I approach question d?

[coral parcel]

Hey look, there's the union variant.

[weary tiger]

right

so this one

should have been my initial ans right?

[coral parcel]

Yes.

[weary tiger]

Thanks

[heavy tinsel]

If A and B are finite sets, are there more relations than functions from A to B?

the number of relation is just |A| x |B| right

Ahh ok, i think the number of functions should be |A|^|B|

so its false.

[coral parcel]

The number of relations is 2^(|A|×|B|)

[heavy tinsel]

Why's that?

This was how my txtbook defines it

So if S ={1,2}, T = {3,4,5}, S x T would have 6 elements?

[north pulsar]

anyone help me make sure that this is false

For any two sets A and B, A x B = B x A

[heavy tinsel]

false

[north pulsar]

alright just making sure

[smoky mantle]

So I'm looking at a variant of dijkstra's algorithm that works for negative edges (but no negative cycles). It's basically lazy deletion. Essentially, after the normal stuff, you delete a node off the visited array if you find a path with a negative length that reduces its distance after you've already visited it (so that you can consider its neighbors again with the newly reduced distance to it).

I understand these things intuitively, but how do I do them rigorously?:
How do I prove it terminates (perhaps an upper bound in terms of the values of the integer lengths?) and gives the correct answer?

How do I prove that there are graphs where the runtime of this algorithm is exponential?

[coral parcel]

Yes, but a relation is a subset of S×T, not an element of S×T.

[heavy tinsel]

ahh gotcha

[north pulsar]

this math is cringe

cant stand it

[hoary cloak]

ok so trying to answer all your questions here

proving that algorithms like this one are correct is usually done by induction or contradiction. i personally don't know about this algorithm you're talking about (in fact if you just wanna solve shortest path with negative edges i suggest you search for bellman-ford), but think about dijkstra's: you prove that you have an optimal substructure (you can use contradiction for that) and that the greedy choice will give you the correct answer (if there are no negative weights of course)

proving that it terminates is also necessary. it's not a fully decidable problem BUT if it depends on a set of elements that is finite and becomes smaller for each iteration, it halts. so kinda like the priority queue in dijkstra's works

proving that there are exponential instances could be a constructive proof (find a single problematic instance and you're done). if there's a non-constructive way to prove it, i personally don't know

[smoky mantle]

Yeah, I know there is bellman ford, but just for the sake of this, I'm considering a modififed form of dijkstra

[heavy tinsel]

Whats an example of equivalence relation on integers with infinitely many equivalence classes?

[weary tiger]

Defining the relation with just “=“ should do it, right?

[heavy tinsel]

hmm ok, so something like {(x,y) in Z^2 s.t. |x|=|y|}

[weary tiger]

Sure but I think without absolute value works too

[heavy tinsel]

Right. That makes sense

thank u

[weary tiger]

Np!

[weak sierra]

I'll try this, Thanks

[iron hearth]

can someone explain why that works for the problem above

[olive condor]

Huh? Not always false. It is true iff A=B, B={}, or A={}.

Cause A x {} = {} x A = {}.

[night heath]

Is not rational here mean that x is irrational

Also, irrational * 2 is always irrational right?

[stray reef]

yes, "not rational" and "irrational" by definition mean the same thing

yes, two times an irrational number is always irrational.

[night heath]

I have to prove that f(x) is one to one or not, i proved that for 3x+2, the fx is rational and one to one , but I am trying to prove the other one, i can't how can I prove that x^3 is irrational for all irrational numbers and is one to one

[gritty crescent]

x^3 need not be irrational if x is irrational (consider x=cuberoot(3))

[snow crown]

hi can someone help with parts c d and h? im not sure how to do them

i know how to do the rest but these confused me

[gritty crescent]

What about (c) and (d) is confusing you?

It's similar in spirit to (a) or (b)

[snow crown]

is it just pi pi, pi e, pi 0?

and onwards?

[gritty crescent]

The Cartesian product should give you pairs of elements

So one of the elements in AxA for instance would be (pi,pi)

[vital dew]

Manan.

[gritty crescent]

Your product consists of all possible pairs of elements, where the first entry comes from the first set in the product, whereas the second entry comes from the second set.

[snow crown]

ohhhh i see, okay thank you very much for explaining

[gritty crescent]

Can you show me what you've done for (a), just to be clear?

[snow crown]

yea sure

[gritty crescent]

,ccw

,rccw

[gritty crescent]

Looks good!

Now for AxA you just consider pairs where both elements come from A

Similarly for BxB

For the three-fold product, by convention, we consider triples instead of pairs (and generally for the n-fold product, n-tuples).

So PxQxR for instead would consist of all triples (p,q,r) where p is in P, q is in Q, r is in R

[stray reef]

don't forget the closing braces at the end }

[snow crown]

apologies for the late reply, but yea thanks, I was just unsure, it felt a little bit off

[snow crown]

will fix!

[weary tiger]

A bag contains marbles that have blue on them, red on them,
or blue and red on them. If your friend tells you that the probability of drawing a
marble with blue on it s .47, the probablility of drawing of drawing a marble with red
on it is .59, and the probability of drawing a marble with blue and red on it is .05.
Explain whether this situation can or cannot happen.

not sure how to start this problem

[coral parcel]

Are marbles with neither color possible?

[weary tiger]

hmm im assuming not

[coral parcel]

Hmm, actually that turns out to be irrelevant.

[weary tiger]

yea just testing if it is possible

[coral parcel]

It can be true without any uncolored marbles if we assume the friend rounded the probabilities to 2 digits after the decimal point. Suppose there are 1000 marbles in total, of which 413 are pure blue, 533 are pure red, and 54 are bicolored.

[weary tiger]

how did you come up with these numbers

[coral parcel]

Partially by trial and error.

First step is using inclusion-exclusion to find that if the probabilities are exact, the probability of getting red OR blue would be .47+.59-.05 = 1.01, which is absurd.

But close enough to possible that it could be caused by rounding.

So I tried to make .47+.59-0.05 a bit smaller by adjusting each of the terms up or down by strictly less than 0.005, because such an adjustment would be hidden by rounding.

[weary tiger]

wow thank you

would just saying .47 + .59 + .05 = 1.11 make it not work

@coral parcel

[coral parcel]

.47 + .59 + .05 counts each of the bicolored marbles three times.

[weary tiger]

i thought the red and blue marble was its own marble

[coral parcel]

The question said "the probability of drawing a marble with blue on it" is .47, which sounds to me like it means either a pure blue or a bicolored one.

[weary tiger]

hmm ok thank you for the help

i get it now

[thick nacelle]

how should I compute the cartesian product with the empty set?

the answer differs from what I get

[tidal tulip]

what is the answer to the “why”’part of this proof:

i’m trying to understand this proof to do a similar one

specifically why does a/b need to be positive

[stray reef]

well log(2) > 0 isn't it

[tidal tulip]

ok i see yeah

ty

[coral parcel]

The empty set is not one of the operands to the × operation, just one of the elements of the sets. In this capacity it works like any other mathematical object with a name.

[thick nacelle]

oh

so it's a set containing an empty set

[coral parcel]

{0,Ø} in the question is a bit strange, however, because 0 and Ø are different kinds of things. (In some common formalizations, the number 0 and the set Ø are literally represented by the same mathematical object).

[thick nacelle]

hmm

so we would get

{(Ø,0),(Ø,Ø)} x {0,1}

[coral parcel]

You could just write {(Ø,0,0),(Ø,Ø,0),(Ø,0,1),(Ø,Ø,1)} and leave the same ambiguity for the consumer of that result to deal with ... :-)

[coral parcel]

Right.

[thick nacelle]

oh my god

I was treating the cartesian product as if it was commutative

A X B X C =! A X C X B

[coral parcel]

Ah, that will give trouble.

[thick nacelle]

thank you

I understand now

have a nice day ! 😄

[tranquil vector]

How would I prove by induction f(2^k )=k+1 for all k∈{0,1,2,3,…,∞)?
would this work as a proof? Or am I missing something
f(2^{k+1} )=(k+1)+1
f(2^{k+1})=f(2^k )+1
f(2^{k+1} )=k+1+1

or is that not what a proof by induction does

because im unsure about what the concept really means

[coral parcel]

What do you know about f to begin with?

[tranquil vector]

It’s a function where you input only powers of 2

It returns the (upper part of the power of 2) + 1

[coral parcel]

By the "upper part" I think you mean "exponent".

[tranquil vector]

Yes lol

[coral parcel]

But if that is the definition of f, then there's nothing to prove.

[tranquil vector]

oh

oh ok I get it

[coral parcel]

A proof by induction would be relevant if you had a recursive definition of your $f$, such as $$f(n) = \begin{cases} 1 &\text{when }n\le 1 \ f(\lfloor n/2\rfloor) + 1 & \text{otherwise} \end{cases}$$

[vital dew]

Troposphere

[tranquil vector]

ah okay thank you

[tidal tulip]

i want to prove log base 4 = 6 is irrational. can i get a proof check: proof by contradiction, assume log_4(6) is rational then there exist a,b in Z and b != 0 such that 4^(a/b) = 6. where a/b in Z+ since a positive integer raised by a positive integers is a positive integer and 6 is a positive integer. then we see 4^(a/b) =6, 4^a = 6^b, and the only way this equality holds is if a=b=0, but b!=0 and b must be positive thus contradiction and log_4(6) is irrational.

[gilded axle]

you're using a false implication there, you cannot conclude that a/b is a positive integer like that, integers can also be raised by fractions to still get positive integers like 4 can be raised by 1/2, which gives you 2. That argument is unnecessary, however you can just proceed without it and argue with the prime factors of 4^a and 6^b instead

[tidal tulip]

@gilded axle how should i justify a/b is positive then? and wouldn’t my original argument 4^a = 6^b is true only if a=b=0 and b doesn’t equal 0 work?

what do you mean prime factors of 4 and 6 not understanding what you mean

2^a(2^a) = 2^b(3^b) is what i’d see but don’t see what to say from there

[gilded axle]

well you can say if it was negative then the result would be smaller than 1 and that does the job.

[stray reef]

log base 4 = 6
what does this mean

are you trying to say log_4(6)

[tidal tulip]

yes

[stray reef]

then say log_4(6)

[gilded axle]

4^a is not divisible by 3, but 6^b is, just pick wlog a and b positive since you know a/b is positive

[stray reef]

= is not a replacement for "of"

[tidal tulip]

i am still not seeing how a/b is positive and also does my argument of 4^a = 6^b work since a=b=0 for that equality to hold

and b != 0

[stray reef]

log_4(6) is positive

[coral parcel]

Do you know the fundamental theorem of arithmetic?

[tidal tulip]

our class hasn’t covered it

so no

what does it say

can someone tell me if my original proof works i can do the more standard one but i wanted to see if my original thinking is correct contradicting b=0 but b!=0

[coral parcel]

Every positive integer can be written as a product of primes in exactly one way, other than changing the order of the factors.

[tidal tulip]

ok.

[coral parcel]

Since 4^a is the product of 2a copies of the prime 2, and 6^b is the product of b copies of the prime 2 and b copies of the prime 3, these products can only be the same (up to reorderings) if b=0 such that there are actually no threes in 6^b after all.

But then 6^b=1, and a has to be 0 too.

[tidal tulip]

ignoring the a/b is positive part is what you stated what i wrote

because i think it is but i need to factor 4,6 into their prime factors

[coral parcel]

Sorry, I might have missed some context, I'm not sure whether I disagree with anything you wrote.

[tidal tulip]

ok

i’m confused is there an error in my proof

i’m fine if there is i just want to understand what i am misunderstanding

[coral parcel]

I'm not sure where you get a/b in Z from.

[tidal tulip]

if so

let me reread

[coral parcel]

Perhaps you meant to say a in Z and b is also in Z?

[tidal tulip]

i’ll rewrite it

yes

i’ll rewrite it to say what i intended

[coral parcel]

That's not the same as saying that a/b is in Z, though.

You can get away with phrasing it as "a, b in Z", but the slash denotes a certain arithmetic operation and "a/b in Z" would claim that the result of that computation is in Z.

[tidal tulip]

i want to prove log base 4 = 6 is irrational.

by contradiction, assume log_4(6) is rational then there exist a,b in Z and b != 0 such that 4^(a/b) = 6.

then we see

4^(a/b) =6

4^a = 6^b

and the only way this equality holds is if a=b=0, but b!=0, this is contradiction and thus log_4(6) is irrational.

[coral parcel]

You still have not fixed the nonsense "log base 4 = 6" that Ann pointed out.

[tidal tulip]

i want to prove log_ 4 (6) is irrational.

by contradiction, assume log_4(6) is rational then there exist a,b in Z and b != 0 such that 4^(a/b) = 6.

then we see

4^(a/b) =6

4^a = 6^b

and the only way this equality holds is if a=b=0, but b!=0, this is contradiction and thus log_4(6) is irrational.

good catch

i’ll tex this up once i get it

does that look correct now

i see both your point and ann now

[coral parcel]

Yeah ... I actually think it would make sense to argue that because log_4(6) is certainly positive, you can choose both a and b to be positive. Then you can be sure that 4^a = 6^b is a statement about integers.

[tidal tulip]

how do i make the claim log_4(6) is positive

or rather prove that claim

how do i further justify only true if a=b=0

[coral parcel]

If x is zero or negative, then 4^x <= 1, and 6 does not satisfy that.

[tidal tulip]

that may not be obvious either

ok makes sense log_4(6) is positive.

[coral parcel]

a=b=0 comes out of the prime factorization argument I sketched.

[tidal tulip]

how did that go again?

4^a = 6^b

2^a(2^a) = 2^b(3^b)

then from there what do i need to say

[coral parcel]

But you can just say, since a and b can both be chosen to be positive, 6^b is a multiple of 3, but 4^a is not a multiple of 3, so they can't be equal to each other.

[tidal tulip]

ok let me rewrite it

i’ll show you what i understand it’ll be more wordy but this is more for me

i want to prove log_ 4 (6) is irrational.

by contradiction, assume log_4(6) is rational then there exist a,b in Z and b != 0 such that 4^(a/b) = 6.

log_4(6) is positive because if x < 1 then 4^x < 6 for x in R, thus this means a/b is a positive integer *** see if this is correct

then we see

4^(a/b) =6

4^a = 6^b

2^a(2^a) = 2^b(3^b)

which means 4^a is divisible by 3^b but this is a contradiction since the only prime factors of 4^a are: (2^a)(2^a), hence this is a contradiction

@coral parcel does that work

and can i delete the positive part of the proof since i don’t use it

ah i made the mistake again

a/b doesn’t have to be an int

just a and b are positive

[coral parcel]

Indeed.

[tidal tulip]

can i delete out the positive thing entirely since i don’t use it

[coral parcel]

You use it implicitly when you begin to speak about prime factors of 4^a.

If a were negative, then 4^a would not be an integer.

[tidal tulip]

ok let me fix the error

i want to prove log_ 4 (6) is irrational.

by contradiction, assume log_4(6) is rational then there exist a,b in Z and b != 0 such that 4^(a/b) = 6.

log_4(6) is positive because if x < 1 then 4^x < 6 for x in R, thus this means that a,b are positive integers

then we see

4^(a/b) =6

4^a = 6^b

2^a(2^a) = 2^b(3^b)

and we know the prime factors of 4^a and 6^b are positive integer because a,b are positive integers

which means 4^a is divisible by 3^b but this is a contradiction since the only prime factors of 4^a are: (2^a)(2^a), hence this is a contradiction @coral parcel

and why do i need the prime factors to be positive integers, illl need to look up that definition

or rather theorem

[coral parcel]

"if x < 1 then 4^x < 6" is true and does the job, but can feel a bit random.

"prime factors of 4^a and 6^b are positive integers" seems to be misunderstood. Prime factors are by definition always positive integers. The real point here is that 6^b itself is a positive integer because b is a positive integer. If 6^b had not been a positive integer, it wouldn't have prime factors that we could speak about.

[tidal tulip]

how can i cleanly express that in the proof in that section

this is more for me because i think it’s excessive to write in an actual proof prob

[coral parcel]

After you reach 4^a = 6^b, add a remark:

This is an equation between positive integers because a and b are positive integers.

[tidal tulip]

i agree the way i express why log_4(6) is pos is confusing. how did you recommend writing that part again

i’ll take all this an tex it up next version and show you i think the next one will be the proof

i wanna practice tex skills

[coral parcel]

I would just say

If x \le 0 then 4^x \le 1
which looks more motivated because "x \le 0" is clearly connected to your claim that x is actually positive, and \le 1 is the most precise bound on 4^x you can get from x \le 0. I would think you can probably leave it to the reader to notice that 6 is not \le 1.

[tidal tulip]

it’ll be a few minutes but i’m gonna tex up the proof now

[tidal tulip]

Proof: By proof of contradiction assume $\log_4 6$ is rational then $\exists a, b \in \mathbb{Z}$ and $b \neq 0$ such that $4 \textsuperscript{(\frac{a}{b})}$ = 6. $\log_4 6$ is positive because if $x \le 0$ then $4 \textsuperscript{x} \le 1$.

Then we see:

$4 \textsuperscript{(\frac{a}{b})}$ = 6

and this is an equation between positive integers, because a,b are positive integers

$4 \textsuperscript{a} = 6 \textsuperscript{b}$

$2 \textsuperscript{a} (2 \textsuperscript{a}) = 2 \textsuperscript{b} (3 \textsuperscript{b})$

which means $4 \textsuperscript{a}$ is divisible by $3 \textsuperscript{b}$ but this is a contradiction since the only prime factors of $4 \textsuperscript{a}$ are $2 \textsuperscript{a} (2 \textsuperscript{a}) $

[vital dew]

strings

[tidal tulip]

@coral parcel how does that look

[coral parcel]

Don't use \textsuperscript for exponents in math mode; that's what ^ was born to do.

The "this is an equation between positive integers" comes a line before it is needed.

I would use $4^{a/b}$ instead of $4^{\frac{a}{b}}$ -- the very tall exponent with a horizontal fraction bar is less readable.

[vital dew]

Troposphere

[tidal tulip]

ok great advice, i'll do this

[coral parcel]

You don't really use the split of $4^a$ into $2^a\cdot 2^a$. In particular "the prime factors are $2^a(2^a)$" doesn't make sense. What you mean is that the only prime factor is 2. However, it might be of some use for that to rewrite $4^a$ as $2^{2a}$ instead.

[vital dew]

Troposphere

[tidal tulip]

what do you mean when you say rewrite $4^a$ as $2^{2a}$ instead, but state the only prime factor of $4^a$ is 2, like how would that look

[vital dew]

strings

[coral parcel]

Oh, then the proof would actually end with "... since the only prime factor of 2^{2a} is 2."

[tidal tulip]

ok let me re-tex and make your edits

[vital dew]

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

[tidal tulip]

@coral parcel

how does that look

Proof: By proof of contradiction assume $\log_4 6$ is rational then $\exists a, b \in \mathbb{Z}$ and $b \neq 0$ such that $4^{a/b}$ = 6. $\log_4 6$ is positive because if $x \le 0$ then $4^{x} \le 1$.

Then we see that this is an equation between positive integers, because a,b are positive integers and:

$4^{(a/b)}$ = 6

$4^{a} = 6^{b}$

$4^{a}$ = $2^{b} (3^{b})$

which means $4^{a}$ is divisible by $3$ but this is a contradiction since the only prime factors of $4^{a}$ is 2

[vital dew]

strings

[tidal tulip]

i need help ending the proof

[coral parcel]

Did I make clear that in "this is an equation between positive integers", the "this" I was referring to is 4^a=6^b?

[tidal tulip]

ah i see

ok i changed the last line again too

does that now look ok

Proof: By proof of contradiction assume $\log_4 6$ is rational then $\exists a, b \in \mathbb{Z}$ and $b \neq 0$ such that $4^{a/b}$ = 6. $\log_4 6$ is positive because if $x \le 0$ then $4^{x} \le 1$.

Then we see that

$4^{(a/b)}$ = 6

$4^{a} = 6^{b}$

and this is an equation between positive integers, because a,b are positive integers

$4^{a}$ = $2^{b} (3^{b})$

which means $4^{a}$ is divisible by $3^{b}$ but this is a contradiction since the only prime factors of $4^{a} are: (2^{a})(2^{a})=(2^{2a})$

[vital dew]

strings

[coral parcel]

Looks fair. I think you have lost the sentence that points out that because log4(6)>0 you can choose a and b to be positive.

[tidal tulip]

oh yeah you;re right

like could i phrase it like ihad it

$\log_4 6$ is positive because if $x \le 0$ then $4^{x} \le 1$. Then means that a, b are positive integers.

[vital dew]

strings

[tidal tulip]

because you used "could" but im making an assertion they are

given log_4(6) is pos

so want to make sure im not saying a false statement there

or i guess you could have a,b both be neg?

idk now im confusing myself lol

bc shouldnt they be pos if we are to use the prime factor part

ah wait

as long as 4^x is pos

a,b has to have the same parity right?

[coral parcel]

You mean the same sign.

[tidal tulip]

it doesnt mean a,b is pos or neg but they have to have the same sign*

[coral parcel]

"Parity" is whether they are odd or even.

Yes, a and b have to have the same sign, and therefore you can choose to negate both of them if the ones you got at first were negative.

The situation we don't want to be in is the one where one of them is positive and the other is negative.

[tidal tulip]

ok so im writing this just for myself

so when i look back at it in 5 days i remember

$\log_4 6$ is positive because if $x \le 0$ then $4^{x} \le 1$. This means both a, b are integers that have to have the same sign.

[vital dew]

strings

[coral parcel]

(Though I suppose we could handle that too: when we get to 4^a = 6^b, if a and b had different signs one of the sides of the equation would be an integer and the other not, which gets us to a contraction early).

[tidal tulip]

or how should i phrase the fact about a,b

where i dont make a false statement

or can i leave that sentence out

[coral parcel]

The fancy way of phrasing it would be: "So, without loss of generality, we can assume a and b are both positive."

[tidal tulip]

ahh i see

[coral parcel]

"Without loss of generality" is a conventional code word for "the reader can figure out how to patch things up if this is not already true".

[tidal tulip]

ok that makes sense

i really appreciate you helping me both understand this proof and helping me learn tex

and the new theorem about prime factoring

prof mentioned that theorem before i forgot, but she didnt formally define it but did use it once somewhere

[weary tiger]

you can use the proof environment by the way

[vital dew]

fermath

\begin{proof} put your proof here \end{proof}

[tidal tulip]

oh cool

[tidal tulip]

how would one being an integer and the other not be a contradiction there, what is it contradicting explicitly?

@coral parcel

[coral parcel]

An integer cannot be equal to a non-integer, so 4^a = 6^b would be false.

[tranquil vector]

I have a sequence s0=1 , s1=100, s2=10011, s3=10011100100

Each time there's a 1 you replace it by 100 in the next step, if its a 0 you replace it with a 1 in the next step

How can I find an expression to the number of 1's that can be found in a specific step in the sequence

ie: I want to know at s10 how many 1's there will be

[coral parcel]

One strategy would be to write down a simultaneous recurrence for the number of ones in each step and the number of zeroes in each step.

[tranquil vector]

but how do I figure that out

[coral parcel]

Writing down the recurrence, or solving it?

[tranquil vector]

finding the recurrence of 1s and 0s

[coral parcel]

Well, the number of zeroes in a step is twice the number of ones in the step before, right?

And the number of ones in a step is just the total number of digits in the step before?

[tranquil vector]

oh yeah ur right

thanks man

So Ones(n)=Length(n-1)

is that a closed form expression

[coral parcel]

No, it's just a recursion equation. I'd write ones(n) = ones(n-1) + zeroes(n-1), by the way, so you only have two sequences to keep track of.

[tranquil vector]

ah yes that makes sense

thank you

but i want the closed form

so it would have to be based on n right

[tidal tulip]

@coral parcel is it correct to say the prime factors of 4^a is 2^a or do i simply say 2

[coral parcel]

Yes. I suppose you haven't learned any general methods for solving linear recurrences?

[tranquil vector]

if you explain it maybe i have but that word doesnt come to mind

[coral parcel]

The prime factors of 4^a are simply 2 (with a multiplicity of 2a).
2^a if not a prime factor because it is not a prime (except in the special case that a=1).

[tidal tulip]

ok i see

[coral parcel]

If the word doesn't ring a bell, then you probably haven't.

[tidal tulip]

if i changed my proof to say that

4^a = 2^b(3^b) means that 3 is a prime factor of 4^a but this is a contradiction since the only prime factor of 4^a is 2.

would that then be correct

[coral parcel]

I've cranked the handle on the general method and found the closed form $\text{ones}(n) = \frac{2^{n+1} + (-1)^n}{3}$. I'm not sure how you might be supposed to discover that without a general method to guide you, though.

[vital dew]

Troposphere

[coral parcel]

That sounds good!

[tidal tulip]

awesome thanks!

[tranquil vector]

Alright thank you troposphere

[coral parcel]

For the record, the method I used was to write the recurrence as $$\begin{pmatrix}\text{ones}(n) \ \text{zeroes}(n) \end{pmatrix} = \begin{pmatrix}1&1\2&0\end{pmatrix} \begin{pmatrix}\text{ones}(n-1) \ \text{zeroes}(n-1) \end{pmatrix}$$ and therefore $$\begin{pmatrix}\text{ones}(n) \ \text{zeroes}(n) \end{pmatrix} = \begin{pmatrix}1&1\2&0\end{pmatrix}^n \begin{pmatrix}1 \ 0\end{pmatrix}$$ and ask Wolfram Alpha to diagonalize the matrix for me, so it becomes easy to raise to powers.

[vital dew]

Troposphere

[timber birch]

Hi yall, can I do TAOCP Volume 1 instead of Concrete Math. I heard Vol 1 covers all of Concrete Math?

[wide vine]

would would the time complexity be of something like a series of for loops?

say we have for (i = 0, i< wordSize; i++)

and we do this 3 times in a row

is it just 3N?

where N is the word size of interest

for my programming class we have to basically recreate worlde and I am trying to think of an efficient way to search the word for my given string comparing to the one selected

in my case my words are always size 5. I natively though I could just loop my word chars against the chars on the selected string

Could I just use a hashmap of the selected string and so my access would be O(1) ideally? can't have duplicate values 😦

Anyways, It seems I will always have to do 5 loops across the selected string to compare with my guess

I guess I can short circuit it by eliminating previous guessed letters

I guess it would be N^2?

Ignore above** but do you think I could do this better than N^2?

[tranquil vector]

Suppose that we want to place disks of radius 1 so that

their centers are all contained in a single disk of radius r; and
no pair of disks overlap.

why it is impossible to place more than ((r+1)^2)−1 disks this way

ie something like this

[jade niche]

anyone know how to solve this problem?

[hard yew]

One way is to prove that (AUB)' is a subset of A' cap B' and vice versa by assuming that an element x belongs in (AUB)' and showing that it must belong to A' cap B' (and the other way around)

Another would be through logically equivalent statements, start from (AUB)' and reach A' cap B', however since you have De Morgan's laws here it isn't advised

[brisk plover]

The second part of the proof is not a "proof by contradiction" right? Since proof by contradiction would require me to show that not A V B -> X where X is false.

The second part is a "proof by counterexample"?

To prove the second part by contradiction would it be,

Since NOT (A /\ B) is True then A /\ B is false then,
A V B - > A /\ B
Since both A /\ B is false that implies that A V B is false too.

dies from confusion

[jade niche]

so what do I write exactly? This is the only part that I dont understand on my hw

[minor zephyr]

Why can’t they just write a damn truth table

[hard yew]

To be honest, both parts look like direct proofs. You have A->B and they assume A is true in both parts and arrive at the conclusion by using previously discovered information from the assumption "A is true"

[silent hinge]

Ok I red the chapter on functions, I watched the freaking lecture on function I still don’t get

Can you explain to me this problem like I am a 7 years old

[hard yew]

Have you not done such proofs in class before?

[jade niche]

no we just started learning and I dont understand it at all

the sets

[hard yew]

I can't teach you how to do these proofs if your teacher/prof couldn't be bothered to and then assigned you homework for them

[silent hinge]

Please

Thank you in advance

is 6 a range set from 1 to 6?

[hard yew]

For 1) you are given:
f: {1,2,3,4,5,6} -> {a, b, c, d, e, f}
and the encoding of f is f=[a, b, c, d, e, f]

[hard yew]

[6] is the domain

[jade niche]

so how would u answer this question

[hard yew]

Assuming you know what injective/surjective means I don't see what's confusing you here

[hard yew]

Let x belong to (AUB)' and show that x also belongs to A' cap B'
Let x belong to A' cap B' and show that x also belongs to (AUB)'
Therefore, (AUB)' = A' cap B'

[hard yew]

If you ask questions I can answer them for you, I can't guess what you don't know though

Do you understand the explained example?

[silent hinge]

so in my case, f(1) would give me a?

[hard yew]

Yes

[silent hinge]

which would be injective since

the input is different from the oputput ?

[hard yew]

Ugh

Injective means f(x) = f(y) -> x=y

In other words, if two outputs are the same, then the inputs that map to them are the same

There are no two distinct inputs that map to the same output

Different inputs map to different outputs

etc.

[silent hinge]

damn dude thanks a lot, that was a clear explanation

if ETH hits 10k im buying you a ps5

[shy reef]

Does anyone understand this? It’s my third assignment and this class still confuses the heck out of me 😭

[hard yew]

Have you tried something?

[silent hinge]

@hard yew ok so for number two it is not surjective because 8 does not have a corresponding input and also not injective since f(5)=f(6)=6 which means 5=6 they are the same pointer

is my reasoning correct

?

[hard yew]

Yes

[silent hinge]

the hell with that ps5 ill buy you a tesla

[hard yew]

I'm not sure what you mean by "they are the same pointer"

You can just say that the condition for a function to be injective fails, that is, the implication f(x)=f(y) -> x=y is false for x=5, y=6

[wide vine]

Is this not just demorgans?

I am sure you can find a proof for that

[weary tiger]

Hey can someone help me with this

I am stuck here

[stray reef]

what rules of inference are you allowed to use?

[distant bobcat]

For the justification of "every tree is a bipartite graph" it is enough to state that since removing any vertex of a tree T makes a disconnected graph its always possible to construct two disjoint sets V_1, V_2 and since T has n-1 edges (assuming n vertices) we can construct an edge set (a,b) where a is in V_1 and b is in V_2?

[stray reef]

??

[distant bobcat]

Im trying to show that its possible to construct two disjoint sets given a tree graph structure.

then show that its possible to reach any vertex in V_2 from a vertex in V_1

[stray reef]

your construction makes no sense to me

how about i give you some kind of tree and you show what your construction gives?

@distant bobcat

[distant bobcat]

@stray reef sure, or I can construct some tree myself and see where my reasoning fails

[distant bobcat]

So I make a cut where the red line is, remove the edges connecting each set and create a bipartite graph

[stray reef]

????

you realize this just completely removes all the edges right

[distant bobcat]

oh I see because the two vertices gets removed and all their extended edges. Yeah that doesnt make sense

@stray reef I could just argue that since a tree has no cycles then it does not contain any odd cycles such that it is bipartite.

Since bipartite graphs must contain no odd cycles.

[stray reef]

bit roundabout but that works i guess

[distant bobcat]

If I wanted to do a construction I think way that works would be to use some sort of 2 coloring

[stray reef]

2-colorability and bipratiteness are literally one and the same lol

[distant bobcat]

but unsure how to formulate it properly

yes, so just need to make sure no two adjacent vertices have the same color right?

[stray reef]

don't overthink it

it's very easy to two-color a tree

pick whatever vertex you like and color it red. then color its neighbors blue, then their neighbors red, and so on

[distant bobcat]

oh and just the fact that any two vertices are connected with exactly one path

@stray reef thanks for good help!

[oak notch]

Saw this in one of my algorithm classes. Why is 0 raised over there?

[gilded finch]

What lead to this result ?

[oak notch]

This was the example

I know that the base is 2, but I don't know why the 0 is up there

[gilded finch]

That's simply explicit application of Master Theorem

[oak notch]

Yep, I'm currently learning about the Master Theorem

[gilded finch]

Case 2 with k = 0, hence lg^0 n, which can be simplified to 1

The 0th power is written here to make the application of the theorem very explicit, for pedagogical purpose, I assume

[oak notch]

I see. Just to be sure, if it's lg^2 n, then is it going to be lg n * lg n?

[gilded finch]

Yes

[oak notch]

Got it, thanks!

Does the master method not work here because f(n) can be undefined? I.e 1/0

[gilded finch]

No, it's because f(n) is not polynomially smaller than log_b a. See

(from CLRS)

[oak notch]

I'll read that in a bit. Thanks, Solon!

[hoary cloak]

are you confused with the logic behind it or notation?
if it's the former, you can just remind yourself that if p -> q then necessarily p and ¬ q is false
in the latter case, just try to think what each part of this means individually. don't worry about what is in E, G, or W, they're black boxes that spit out true or false

[shy reef]

I think I figured it out but this helped a lot

Thank you!!!

[hoary cloak]

good to know!! good studies to you

[weary tiger]

@stray reef these are the rules

[sharp turtle]

why is this only a bijection and not also a surjection

[silent hinge]

What is a?

[sharp turtle]

I feel like if you are considering the function $f: A \to A \coprod B$ sure its only injective but the function $f: A \cup B \to A \coprod B$ should be a bijection

[vital dew]

Invictus

[sharp turtle]

any given set

[silent hinge]

For number two i someone please explain.

None is given through

[sharp turtle]

ok, take the set A={1,2,3} B={4,5,6}

[sharp turtle]

Why did you say that $a-1 \equiv 6(a-1)$ \pmod 6$

[silent hinge]

I don't Know

[vital dew]

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

[sharp turtle]

Okay, so we have $a-1 \equiv 0 \pmod 6$ which is correct

[vital dew]

Invictus

[sharp turtle]

what does it mean for a number n to be congruent to 0 mod m?

[hard yew]

$a \equiv b\pmod n$ doesn't mean $a-b\equiv nk, k \in \mathbb{Z}$

[vital dew]

Alter

[hushed mulch]

Can someone help me explain task b to me? My answer is currently that there are infinite equivilance classes, but I am not sure if I am wrong.

[coral parcel]

Perhaps fix a concrete small p, say p=3 and work out what the equivalence classes look like in that case?

[sharp turtle]

bump

[olive wren]

bijection is injection + surjection

oh

you meant injection

I dont fully understand what they mean by isomorphic copy, but if it is a bijection, it could just be that theyre focusing on the injectivity

[sharp turtle]

yeah

[sharp turtle]

like a set with same cardinality

[sharp turtle]

@olive wren could they have meant domain A and not domain A U B?

[olive wren]

Oh wait

Theyre just referring to the functions from A to the disjoint union (and B to the disjoint union)

[sharp turtle]

okay then its only an injection

i thought they meant A U B

[olive wren]

The function:
[ f: A\cup B\longrightarrow A\sqcup B ]
Doesnt really mean anything because $A\cup B=A\sqcup B$

[sharp turtle]

no

[olive wren]

no?

[sharp turtle]

the isomorphic sets to A and B can have no elements in common to A and B

which makes the 2 sets different

[olive wren]

Oh I see

So yes

[sharp turtle]

just needs to have same cardinality

to define a bijection between the sets

[olive wren]

Sorry im just not familiar with the terminology

[sharp turtle]

np

[olive wren]

But yes youre right

[sharp turtle]

This is my proof that family of congruence classes form a parition, is it correct?
Because each element is congruent to itself by reflexivity, each congruence class has at least one element. To prove that the elements of the family of congruence class are disjoint, we first delete all copies of the same congruent class, except one. We can do this because identical elements in a set are redundant. Because if a ~ b, a would be in the same congruence class as b, the congruence classes are disjoint. We now show that the union of the congruence classes is the set we parittioned (S) by examining the fact that each element is congruent to itself so each element is in a congruence class.

im not sure if i made a mistake somewhere

[pale epoch]

what does "we first delete all copies of the same congruent class, except one" mean

also i would be more explicit on why they are pairwise (!) disjoint

[hard yew]

What does $:\equiv$ mean?

[vital dew]

Alter

[hard yew]

Context: $\forall A, B (A\cross B :\equiv {(a, b): a \in A \land b \in B})$

[vital dew]

Alter

[hoary cloak]

dunno if the disjoint part would convince me if i were pedantic about your logic. but you can use the fact that congruence is an equivalence relation i guess

also i'll kinda double down on what loch said, i think that this "delete redundant elements" is adding more confusion than doing any good

if you just cut it out your proof will prob send the same message. unless there's something i missed

[haughty spruce]

I need help understanding Grinsberg's Theorem in Combinatorics/Graph Theory (Mathematics)

I'm proving that a certain planar graph doesn't have a hamilton circuit. I can do it the conventional way but I've tried it and understanding symmetry doesn't really work. Here's the original graph

https://cdn.discordapp.com/attachments/486841085210132490/942907676478832720/Graph.png

Here's my first attempt (doing rules 1,2,3 and attempting symmetry) https://cdn.discordapp.com/attachments/486841085210132490/942907934097162270/Attempt_1.png

I kind of gave up doing it like that and reverting to a theorem called Grinberg's Theorem. Here's what the textbook states (with an example)

https://cdn.discordapp.com/attachments/486841085210132490/942908678506434580/Grinberg_Theorem.png

https://cdn.discordapp.com/attachments/309690497272905728/942902118090670130/Theorem_4.png

So here's my second attempt using the theorem, but not finished https://cdn.discordapp.com/attachments/309690497272905728/942904858267222097/IMG_1991.jpg

This is my reasoning for the bottom paragraph of the example (AKA the second picture right above this message). The thing is, I'm confused on what reasoning/logic the textbook is saying, so I tried thinking about it and this is what I am coming up with

https://cdn.discordapp.com/attachments/486841085210132490/942909480604147772/My_reasoning.png

I just want to know if my reasoning is correct, then understand why, in the textbook example, |4(r6-r6')| >/= 8 and not a different number

[tidal tulip]

can someone check my proof

Prove/disprove the following statement: consider the set $A={x \in \mathbb{Z} : 3 | x}$ and the set $B = { x \in \mathbb{Z} | x=6k-3$ for some k $\in \mathbb{Z} }.$ Then $B \subseteq A.$

Statement is true. Proof: If x $\in$ A, then x= 6k-3, for some $k \in \mathbb{Z}$, so x=6k-3=3(2k-1) and thus $3|x$, which means $x \in B$.

[vital dew]

strings

[tidal tulip]

pease check this one instead

Prove/disprove the following statement: consider the set $A={x \in \mathbb{Z} : 3 | x}$ and the set $B = { x \in \mathbb{Z} | x=6k-3$ for some k $\in \mathbb{Z} }.$ Then $B \subseteq A.$

Statement is true. Proof: If x $\in$ B, then x= 6k-3, for some $k \in \mathbb{Z}$, so x=6k-3=3(2k-1) and thus $3|x$, which means $x \in A$.

[vital dew]

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

[hoary cloak]

ok so first of all i think you're onto something and this theorem will help.

the reason why this is 8 and not something else is because |r6 - r'6| is at least 2 and 4 * 2 = 8. think about it, r6 + r'6 is an even number and they're not the same, so the difference between them is at least two.

the argument just works in the opposite way for r4, you try to get as big of a difference as you can (which is a hamiltonian circuit containing all regions bounded by 4 edges inside it and none outside), so r4 would be 3 and r'4 = 0. 3 * 2 = 6 so it doesn't get any better than that

[haughty spruce]

Yeah I figured it out. I'll send a picture of what I did but unfortunately the theorem did not help...

¯_(ツ)_/¯

[hoary cloak]

i mean, whatever works is okay i guess

[hoary cloak]

i didn't really finish solving this problem

[haughty spruce]

So now I’m reverting back to the rules one…

AKA this

[hoary cloak]

just wanted to see if i could make the example clearer

[haughty spruce]

Okay if you do work it, can you please tell me if it works?

[hoary cloak]

tbf i probably won't ahah. i happen to have a test tomorrow and it's graph theory so i'm invested in this but not for too long

[haughty spruce]

Ahh okay XD

I just wanted to make sure the picture going back to the regular rules cover all of the cases so I’ll probs go to office hours tomorrow

Cuz the problem with the rules was understanding how symmetry works when it comes to eliminating cases