discrete-math

[copper ore]

if i do the negation for the outer most bracket

do i have to take it all the way inside?

[sour arrow]

Yes, but you want to trust me

A → B is the same as -A V B

[copper ore]

yeah

i did that

[sour arrow]

Take the negation and apply Demorgan's for all of it

[copper ore]

is there a way you can read that

or should i make it face horizontal

[last sigil]

,rotate

[copper ore]

nvm i got it lol

[cerulean ore]

Had my Maths exam today

Expecting full marks.

[wraith tiger]

Congratulations

[cerulean ore]

Thanks to you guys 😄

[pseudo abyss]

Hey, on my first problem set I have a few exercises like this.
Where I need to prove equality. I have an idea to prove it by induction but i don't really know how to use Big O notation to do this .-.

[stray reef]

by induction?

[pseudo abyss]

It is wrong idea ?

D:

Don't get me wrong, i don't want whole proof, just some kind of starting point

[pale epoch]

start with the definition of the exponential function

i assume this problem set is about introducing you to big o notation?

[pseudo abyss]

yes, exactly

[slender skiff]

when saying x mod y

if x is negative

what happens ?

will the remainder also be negative?
or was there a rule that said its positive ?

[obtuse lance]

remainders are generally given to be a number between 0 and y-1 inclusive

you can always add or subtract multiples of y to your number to force it inbetween that range

-1 mod 5 is the same as 4 mod 5

as an example

[slender skiff]

@obtuse lance I'm supposed to find c in c ≡ a^3 - b^3 (mod 13)

her a is 4 and b is 9

-665

-665 mod 13 = -2

but I also know that 0 <= c <= 12

[obtuse lance]

I just answered what to do, reread what I wrote

[slender skiff]

not sure what you mean by multiples of y

[gentle nebula]

a=b (mod n) iff a-b=kn
so -2=n-2 (mod n)

[slender skiff]

Would this be a valid proof

[pale epoch]

except for notation, yes

[slender skiff]

@pale epoch Whats wrong with the notation?

the ^2?

[pale epoch]

no

you seem to somewhat use ≡ and = interchangeably

there is one line where you state a congruence but not modulo to what

[slender skiff]

Would writing

n^2 ≡ 0 + 0 + 1 ≡ 1 (mod 4)

and n^2 ≡ 0 (mod 4)

be correct?

then

[pale epoch]

yes

[alpine goblet]

can someone explain to me what 4) is asking

<@&286206848099549185>

the wording is pretty weird

[reef thistle]

hmm

[alpine goblet]

👀

[reef thistle]

@alpine goblet please wait 15 minutes to ping

[alpine goblet]

oh

wow

[reef thistle]

okay it does reference to 3

Describe m as a function of epsilon and k such that...

$m(\epsilon, k)$

[vital dew]

Element118:

[reef thistle]

so that a message with length m symbols having k symbols 1 is generated with probability < epsilon

get it so far?

[alpine goblet]

yeahh

[reef thistle]

so, what have you tried?

[alpine goblet]

¯_(ツ)_/¯

i only understood it now

[reef thistle]

okay

[alpine goblet]

I actually have no idea

2^m -1 is the normal probability for it

[reef thistle]

can you express the probability as a summation?

[shrewd spindle]

would someone be able to help me find a formula for this sequence

the 0 starting in the beginning is throwing me off

[obtuse minnow]

er ... separate the numerator and denominator.

Put the two patterns together with a fraction bar 🙂

[shrewd spindle]

well so, i know the top part is like adding odd numbers 1,3,5, but how do you get it to start with zero if n has to start at 1?

[obtuse minnow]

so ... what's the next odd number below 1?

[shrewd spindle]

ohh ok -1

[obtuse minnow]

do you need a recursive formula or a explicit formula?

[shrewd spindle]

explicit

[obtuse minnow]

so ... fun fact ... what kind of numbers are 0, 1, 4, 9?

Yes, you add odds to get them, but like ... how do you get from your counting numbers 0, 1 , 2, 3, 4 to 0, 1, 4, 9, 16?

[shrewd spindle]

yeah my brains kinda turned off at this point this was a stupid question sorry lol

perfect squares

[obtuse minnow]

yeah 🙂

[shrewd spindle]

appreciate it

[obtuse minnow]

Do you have to start with a1 or can there be an a0 ... oh okay 🙂

[shrewd spindle]

i do have to start with a1, but i think i know what to do

[obtuse minnow]

sure sure ... as is said by Bill Nye 🙂 ... carry on.

[weary tiger]

hey guys i just started learning discrete maths in uni and I'm not sure if proof i have written is correct

Show that log7(n) is either an integer or irrational, where n is a positive integer.

my solution:

assume log7(n) is rational > log7(n)=(a/b) > 7^(a/b)=n > 7^a=n^b
therefore if log7(n) is rational. then n must be factor of 7

is this correct solution?

,help

[vital dew]

A brief description and guide on how to use me was sent to your DMs! Please use ,list to see a list of all my commands, and ,help cmd to get detailed help on a command!

[reef thistle]

@weary tiger

n is a multiple of 7

since 7 divides both sides

n can be 49

[weary tiger]

yes thats what i wanted to write :DDD

[reef thistle]

but you are not done yet

because you haven't shown a/b is an integer

[weary tiger]

and how would i show that a/b is an integer?

[reef thistle]

you have shown n is a multiple of 7

So you can induct

[obtuse minnow]

I'd do cases. When is it an integer and for all else it must be irrational.

oops nvm sorry element

[reef thistle]

or consider a factor of n that is not a multiple of 7

[weary tiger]

okay thanks for your help

i will probably frequent this text chat in this semester :DDD

[cinder python]

Hi all, I am struggling to think of an example where set operations (i.e. union, intersection, difference etc) are used in real life or business organisations.

[faint narwhal]

Have you ever heard of sql?

[cinder python]

@weary tiger Thanks, but what about business organisations?

@faint narwhal Yes

[faint narwhal]

Sql is basically modeled off of set theory operations

[cinder python]

@faint narwhal how are set operations used in SQL?

[faint narwhal]

Well sql uses predicates, which are a common thing used in set theory

Depending on what exactly you use, you can do things like cartesian product, intersection

All of which are just set theory operations

[cinder python]

I am not exactly clear but are operations used when writing SQL queries?

[faint narwhal]

Yes

[cinder python]

@faint narwhal Thanks, I will read a bit on SQL then

[faint narwhal]

Why exactly do you ask?

About the uses of set theory in the real world?

[cinder python]

Is just the way I memorise things

and learn

[faint narwhal]

Sure

If you plan to continue to study math

You're going to get to things that have no real use or connection to the real world

[cerulean ore]

Exams have just ended 😄

Recommend me something related to graphs

I want to learn them for Algorithms

[obtuse minnow]

hmm trees?

category theory? 🙂

traveling salesman problem

[cerulean ore]

I've not started with them yet^

[obtuse minnow]

The concepts for trees and the traveling salesman problem are widely understandable.

Sorry. I meant those three as suggestions.

[reef thistle]

hmm, graphs hmm

graph automorphisms

np complete problems on graph like 3-colouring

planarity checking

and this https://en.wikipedia.org/wiki/Robertson–Seymour_theorem

you can find problems, prove they have a polynomial time algorithm, but have no idea what the algorithm is

all because of this

as well as maximum independent set, matching, bipartite matching, graph traversal

topological sorting

@cerulean ore

[topaz tendon]

Hello

someone here?

So someone told me that you can find out wether psi is tuatology by using a method called backward method. and they said that in this method, you try to falsify tautology and if there is a contradiction, then it means it is a tautology. it is similiar to truth tree

I dont know how backward method works like?

---

there is a channel bout logic

[patent rover]

yo

what are some good books on discrete math

[coarse gyro]

Discrete Mathematics and Its Applications 8th Edition by Kenneth Rosen @patent rover

[coarse gyro]

Also this is a dumb question but is (p OR q) AND p equal to (p OR p) AND (q OR p)?

[weary tiger]

Help

[patent rover]

@coarse gyro yes, p or p == p

[weary tiger]

Pls

[cerulean ore]

@reef thistle I want to learn them :3

But, I will check those out.

[weary tiger]

HELP ME

[glossy star]

what have you tried

[weary tiger]

I tried asking “will the dude on the left stop me if I’m going to certain death” but that is implying that the person cares lol

Idk

[glossy star]

have you solved similar questions before

or seen them solved

you should spend more time on it, not ask for help

because the answer is simple and will completely spoil the fun away from you

[sour arrow]

@weary tiger
So the person you ask will always "care". One of the two will always tell you the truth to your question, the other will always lie.

[weary tiger]

@glossy star smd

@sour arrow so knights care about my life?

[sour arrow]

It's a magical Island

[reef thistle]

hmm

I can find the correct answer pretty quickly with a computer

I write a computer program which is compiled

argh, too many numbers for 64 bit integers

argh the asymmetric range is causing problems for me

I'm going to deal with the lower bound separately then

argh precision is annoying me

ah, integer division

[sour arrow]

It would be very difficult to do this "mathematically" cuz integers

Oh wait, are these allowed to be reals?

[reef thistle]

ag

ah I'm doing integers

[sour arrow]

@gleaming dew
Do x and y have to be integers or reals?

Damn

[reef thistle]

big = pow(2, 61)-1
small = -pow(2, 61)
total = pow(2, 124) # all the possibilities
ways = 0
x=1 # try it out for different x
while x<=big: # for all x
    maxAmount = big//x # find largest positive y, and smallest negative y
    maxX = min(big//maxAmount, big) # find largest x that has the same range
    ways += (maxAmount*2+1) * (maxX-x+1) # add in these solutions
    x = maxX+1 # update x
ways *= 2 # (x, y) works, so (-x, -y) works
ways += 1 # unless x=-2^61, y=0, that's not included
ways += 124 # ways to make -2^61
ways += pow(2, 62) # ways where x=0
print(ways/total)

[sour arrow]

Computer is by far the best you can do here. There won't be a closed expression

[reef thistle]

I'm checking my code, the idea is there

I have 4.336808689942018e-19 of it being in the range

9223372036854775931 ways

can someone independently check?

argh

wait

I typed wrong in my code

no wonder the number looked familiar

it's definitely taking a while

while my code is churning out the answer, anyone else can double check my code?

(python)

[sour arrow]

I can extend this problem to the reals. Plus if we only consider positive numbers, we're interested in
The numbers where x ≤ z/y, for z = 2^61
∫ z/y dy for y between 1 and 2^61
= 2^61 ln(2^61)

And the area of the square, that is (2^61)² - 2×2^61

So the answer is approximately
2^61 ln(2^61) / (2^61)² - 2×2^61
≈ ln(2^61) / 2^61

Problem is, I don't know how approximate that answer is

Clearly 0.999... for like 17 decimal places

You sure? At best, that's good enough to show a computer sim is approximate

It could be off

You might be able to use some error theorems to find how far off it is

[reef thistle]

https://discordapp.com/channels/268882317391429632/496785905474994186/630195845190647819

code here

[sour arrow]

What'd you get? I'm interested

[reef thistle]

calculation would take a bit

it's python

It's looping 10^6 times a second
So, it's going to take about 2000 seconds

or an hour

[reef thistle]

great news

it's done

I count 202620924671441687225 ways (with nonegative x)

so, the answer is 9.527190092386719e-18 of the result not overflowing

@sour arrow

@gleaming dew

[sour arrow]

I got 1.833E-17

With my approximation. Jury is out whatever the comparison might mean

Wow, grats on the program literally counting the number of ways to make x, y. That's impressive

[reef thistle]

let's see

mine is off by a factor of about 2, for some reason

let me check

ah no wonder

because I didn't consider negative x

ah

don't worry, quick calculation

okay

updated

400630163324455986423 ways

1.8837539750276337e-17

@sour arrow you got 1.833 or 1.883?

[sour arrow]

Whoa seriously

,calc ln(2^61)/2^61

[vital dew]

The following error occured while calculating:
Error: (intermediate value)(intermediate value)(intermediate value) is not a function

[sour arrow]

,w ln(2^61)/2^61

[vital dew]

Display results online and refine query

Requested by Kaynex#7520

[sour arrow]

That was my approximation by extending to the reals. It won't be exact

[lilac pivot]

damn

[reef thistle]

nice, only 2.7% off

[lilac pivot]

that's wild

[sour arrow]

Agreed, I'm suprised we ended up that close together

[reef thistle]

nah, it was more or less to be expected

now let me put in the correction factor for the reals

x=0, 1, all y are possible
x=+-2, 1/2 of y are possible...
x=+-3, 1/3 of y are possible...
So, the answer is just 1+2*sum(1/n until 2^61)/2^62

but, then the terms after 2^30.5 are going to get pretty inaccurate

so, there we flip x and y

,w 2^622(1+2*(ln(2^30.5)+euler gamma))-(2^30.5)^2*4

argh not getting the answer yet, hold on

so close, off by a factor of 2 but I don't know why

wait

yeah that looks right

[vital dew]

Display results online and refine query

Requested by Element118#2437

[reef thistle]

whoops

let me get more digits

4.0063016332445566735637254554719563225420935286099713... × 10^20

Actual:
400630163324455986423
Estimate:
400630163324455667356

good enough?

now let's calculate error bound

assuming our calculations of sum(1/n) were precise...

ah, the fractional error for them is less than 2^-30.5

okay, then the absolute error of our probability would be on the order of 2^-92.5

@sour arrow

what do you think?

I made a calculation that has an error of only 330k

[sour arrow]

I don't understand it! :D

[reef thistle]

okay, the main idea is because if we use the entire 1+1/2+1/3...+1/2^61

then the terms at the end will have lots of error

that's were all the error came from

so I decided to use half of it and move it around

okay let me demonstrate with a picture

So, we get the shaded region

and then we place that region on the board 8 times

that's the main idea

[cerulean ore]

Whatever you guys are doing looks interesting/fascinating but, alien to me.

[reef thistle]

I have no idea why it gave me so many correct digits

[stray reef]

what... are you even doing

[cerulean ore]

I can still assure you that you're a genius!

[reef thistle]

@stray reef want me to try to explain?

[stray reef]

sure

just don't throw walls of code at me

[reef thistle]

Given two integers, x and y, each randomly chosen from the range of -2^61 to 2^61-1. What is the probability that these two numbers, when multiplied, will not produce a third number, z, (z = x * y) where z is in the range -2^61 to 2^61 - 1 ?

Here's the original problem

[stray reef]

oh oof

[reef thistle]

yeah, I used code to find what I think should be the answer

let's skip that and estimate the answer

[stray reef]

wait

okay so like

[reef thistle]

The answer is near 1, but we are finding 1-answer

[stray reef]

oh

nvm

ok

h

[reef thistle]

Now look at this diagram.

I'm going to try to estimate the number of numbers in the shaded region

the square in the middle is from -2^30.5 to +2^30.5

the region I'll count from x=1 to x=2^30.5

all okay?

@stray reef

[stray reef]

bah sorry i

might not be in the best state for this

[reef thistle]

okay, maybe next time you can bring it up

[cerulean ore]

@reef thistle

Sorry for the spacing (university sends like this only)

I want to learn them (Graph theory, trees) properly as they're involved in Data Structures and Algorithms as well.

Which book do you recommend?

[stray reef]

H OLy fucking shit the spacing is an eye-sore

[cerulean ore]

@stray reef lol, could you please recommend?

[stray reef]

recommend what

[cerulean ore]

A book

I don't want to use local author's book

[stray reef]

there's no way i'm gonna recommend you anything based on this sickening list of poorly typed buzzwords

[lilac pivot]

oof

[cerulean ore]

That's what I get from my university. Do you want me to fix the spacing?

[stray reef]

no need

i don't want to see it at all

[cerulean ore]

That was rude. (Tell me you don't care)

[reef thistle]

Here's a book https://cpbook.net/

[cerulean ore]

Thank you!

[opal ember]

@reef thistle no,sir,only this https://www.pdfdrive.com/competitive-programming-3-e32649251.html

[cerulean ore]

@opal ember You're also into it?

[opal ember]

no i just made it the way links are posted in the served

for your convenience

[cerulean ore]

oh, thank you!

[glossy relic]

when you have this in english language and you want to represent it into a truth table , we use xor and not the normal or right? because the sentence is missing a "or both"

[stray reef]

this seems to suggest xor yes

but english is notoriously ambiguous

[glossy relic]

i see thanks^^

and if i have "if albert comes , so do cornelia and mr meyer" , if mr meyer comes , does it imply that albert came? from my understanding , it should be the case

[stray reef]

no it doesn't

if then statements generally do not work the other way and should not be assumed to do so

[glossy relic]

okay thanks !

[azure lichen]

example:
If it rains, then the road is wet.
but if the road is wet, then it doesn’t have to be raining. It could have rained just before, or someone could have poured water there, or there was a flood…

@glossy relic

[glossy relic]

true ^ thanks

[alpine goblet]

would the time complexity for T(n) = T(n-1)*c^n where c > 1 be O(1) time...?

[stray reef]

no it'd be O(c^(n(n-1)/2))

[cerulean ore]

How much time do you guys spend on a problem before checking the answer

[obtuse lance]

depends on the problem

the longer you spend not knowing, the more likely you're going to remember it in 5 years from now and appreciate the solution

[cerulean ore]

But, if you're preparing for a competition, then?

[alpine goblet]

hows that @stray reef

[stray reef]

c^n * c^(n-1) * c^(n-2) * ... * c^2 * c * T(0)

[alpine goblet]

wouldnt it be (c^n) in that case?

sorry i suck at substitution and stuff

pretty ok with master theorem

@stray reef

[stray reef]

i'm just applying your recurrence n times lol

c^(n + n-1 + n-2 + ... + 2 + 1)

[cerulean ore]

@reef thistle

What say?

Till know what I think is that we have to find the letters such that one or group of them divides the numbers in this pattern

[clever nacelle]

I have a pretty simple homework assignment. It is just 9 questions but worth like 20% of my grade, so any small mistake could mess me up. If anyone has an extra minute could you please look it over, and point me in the right direction if I missed something?
https://docs.google.com/document/d/1GEtf3HR3TUL9GJRUIMjyldZtDsS1Ztp46gG2lDdjc84/

Fixed the link

[pale epoch]

already your first answer has a typo, so maybe you should re-check yourself

other than that it seems fine, though

@clever nacelle

[clever nacelle]

It should say is in the set of B alone, correct? I just caught that now

[pale epoch]

yeah

[weary tiger]

help

trying to prove distributivity for XOR

(r and p) XOR (r and q)

r and (p or q) and not (r and (p and q))

[r and (p or q)] and [not r or not(p and q)]

where do i go from here

[lilac pivot]

aight, so here's my notation:
bar above = not

• = or
  multiplication = and
  ^ = xor

[lilac pivot]

btw sorry if the notation is kinda weird, it's just what I've used

[azure lichen]

I’ve seen worse I guess, the + is weird tho I’d just stick to the usual symbol for or (∨) or use sth like a pipe | because that’s used in programming langs

[lilac pivot]

this is the notation usually used in ece

as far as I know

it's pretty confusing notation

[clever nacelle]

Can you please help me understand what a valid subset of d would be?
(a) Is {5} є {1, 3, 5}? False. {5} is a set, not an element .
(b) Is {5} a subset of {1, 3, 5}? True, {5} is a set, found within the set of {1, 3, 5}
(c) Is {5} є { {1}, {3}, {5} }? True, {5} is an element of the set of sets.
(d) Is {5} a subset of { {1}, {3}, {5} }? False, the elements in the set are {1}, {3}, {5}.

I am sorry for the really easy question. I am just wondering. Since {1}, {3}, {5} are elements, would {{1}} be a subset?

[lilac pivot]

{{5}}

so to make a valid subset, first just start off with {}

then pick any number of elements (or even no elements!) and put them in

say I pick {5}

and I pick {3} too

then I put it in

{{3}, {5}}

that's another valid subset

[clever nacelle]

Alright, thank you! makes sense.

[gusty thorn]

please don't solve it, but I don't understand: what is " Show that among any n + 1 positive integers not exceeding 2n there must be an integer that divides one of the other integers." asking

what's the other integer it's talking about?

sry if it's more of an english question than math :(

[stray reef]

no matter what n+1 integers from {1, 2, ..., 2n} you pick, there's going to be a pair of them where one divides the other

that is what you are asked to prove

@gusty thorn

[gusty thorn]

hm

if I chose 5

{6, 7, 8, 9, 10}

there's no pair that divides into the other, no?

[stray reef]

n=5,

n+1 = 6

you need to pick six

[gusty thorn]

oh ok

I still don't see where the other integer is

[stray reef]

no like

for example

give me six integers between 1 and 10

any six you want

[gusty thorn]

2 3 4 5 5 6

[stray reef]

no

you've only picked five

[gusty thorn]

oh distinct integers

2 3 4 5 6 7

2 x 3 = 6?

[stray reef]

sure yes 2 divides 6

the theorem says this is always going to happen. that you're always going to find a pair like this

[gusty thorn]

OH

I see thank you! 🙏

n = 4
n+1 = 5
{1, 2, 3, 4, 5, 6, 7, 8}

oh wow this is pretty cool

-end-

[rose bolt]

for a binary relation, given a set A that contains {1,2}, is the relation that contains the ordered pairs (1,1) and (2,2) also symmetric? i know that its reflexive but like how can i make it so that its reflexive and symmetric but having the minimum number of pairs for an n-size set?

like say that i have a set A with n elements, if i were to have a relation that is reflexive and symmetric what would be the range of the number of ordered pairs one can get given n elements?

[faint narwhal]

What do you need for a relation to be symmetric

[rose bolt]

for a relation to be symmetric both A is related to B and B is related to A, with A and B being elements

[faint narwhal]

So does that relation satisfy that property

[rose bolt]

no it shouldnt but heres the thing

why is A symmetric?

[faint narwhal]

Why doesn't it satisfy the symmetric property?

[rose bolt]

if it were to satisfy the property wouldnt there be ordered pairs (1,2) and (2,1)? based on the pic i dont get why picture A would be symmetric when theres only one arrow pointing to itself

[stray reef]

no

symmetry does not require the membership of (1,2) in the relation

[rose bolt]

oh so the ordered pairs (1,1) and/or (2,2) can be considered a symmetric relation by itself?

[stray reef]

...

language

[rose bolt]

im confused 😭😭

[pale epoch]

read the property again

[weary tiger]

$\frac{27^{10} + 7^{51}}{10}$

help please

[vital dew]

epelta:

[weary tiger]

I need to find remainder

[obtuse lance]

use Euler's theorem

[weary tiger]

what?

[obtuse lance]

it's basically the souped up version of Fermat's little theorem for when you want the remainder of division without a prime, look it up

[reef thistle]

alternatively, just look at the remainder of 7, 7^2, 7^3... and 27, 27^2, 27^3... and so on

look at the pattern

@weary tiger

[weary tiger]

yeah that one I got

I didn't know of euler theorem tho

[reef thistle]

okay, so you solved the problem?

[reef thistle]

you only have like a small number of cases

@gusty pasture

just do casework and you are done

[gusty pasture]

Do they really just want me to go 0+1 =1 which is odd then the other ones also?

that doesnt seem like the objective

[wintry rock]

1 and 2 are correct, what did I do wrong with 3?

I accidentally went -3 when deciphering and the first 2 ended up being correct, I don't understand...

Ah alright, it's decryption. That's why it's back 3

[faint narwhal]

Eh

It's a nice application of modular arithmetic

[civic phoenix]

anyone has worked on game theory problems?

more exactly , collaborative game theory

[weary tiger]

look up evolutoinary biology

[coarse gyro]

What approach can I use ?

[dapper rose]

counterexample

[coarse gyro]

Would x = cuberoot(a) work?

[stray reef]

what is a

[coarse gyro]

a = 2 my b

[reef thistle]

@coarse gyro okay, can you show that x^2 is irrational and x^3 is rational?

if so you are done

[coarse gyro]

Ah okay! Thanks @reef thistle

[cerulean ore]

@reef thistle yo, I was trying to solve this problem: https://codeforces.com/contest/1209/problem/D

[reef thistle]

and so far you have?

[cerulean ore]

Actually, I am new to graphs so I am kind of learning from the editorials

For the given input, I have drawn the graph

[reef thistle]

what's the graph?

[cerulean ore]

1,2,3,4 are the snacks

[reef thistle]

okay so what do you notice?

[cerulean ore]

edges are the animals so, I have joined the edges with their favorites

[reef thistle]

so how do you calculate minimum number of sad

[cerulean ore]

If I give one edge between 3-4 their favorite then I will need to assign the other edge to any other node since that is not possible, at least 1 member is sad

because one edge will finish both of the nodes

Wait, if that is the case then only one will be happy

[reef thistle]

Say I have a K_n, how many will be happy?

[cerulean ore]

K_n is?

[reef thistle]

complete graph, n vertices

[cerulean ore]

So, for n=3, the answer is 2

Let me check for n=4

[reef thistle]

does the answer change depending on what type of graph it is?

[cerulean ore]

So, for n=4, it is 3, so n-1 is the maximum number for each n

woah

It doesn't change even when the graph changes

Everyone would be happy in this case that is n-1

@reef thistle You're a genius!

But, how was the M-(N-C) formula derived?

C is the number of connected components

M is 5
N is 6
C is 5
5-(6-5) = 4 that is not true

[cerulean ore]

There are 5 connected components in the above graph, right?

[stray reef]

in what graph

the chain you showed up there?

the one that has 1 connected to 2, 2 to 3, 3 to 4, 4 to 5 and 5 to 6?

this has only 1 connected component.

[cerulean ore]

Yep, the above one

How only one connected component?

[stray reef]

the graph is connected

no matter what two nodes you pick there's going to be a path between them

what led you to think there were 5 connected components?

[cerulean ore]

Because 1 is connected to 2 so I thought that is also a component

[stray reef]

uh

and why would 3 not be in the same connected component as 1 and 2?

[cerulean ore]

argh

So, 1--2 is connected subcomponent?

1 for this as well?

[stray reef]

no, {1, 2} is not a connected component.

because it's not maximal.

you can add more nodes to that without making it disconnected.

also, that ^ is a multigraph but it is indeed still connected so yes one connected component

[cerulean ore]

Thank you very much!

How did you complete the BFS and DFS topics?

[stray reef]

BFS?

DFS?

[cerulean ore]

breadth first search

depth first search

[stray reef]

and what do you mean by "complete these topics"

i'm not exactly sure what that'd entail

care to clarify?

[cerulean ore]

Like what resource

[stray reef]

...

i'm afraid i can't answer that

[cerulean ore]

Haha, no problem. Thank you for helping out!

[stray reef]

i mean like... these were mentioned in my CS class back in second semester? and i had come across the terms on my own time before that? but i

can't really pinpoint a resource

[cerulean ore]

You're another genius.

[stray reef]

i disagree but thank you

[cerulean ore]

Good night!

[pseudo abyss]

Hey :), I have to prove this equality

i did some basic steps

and now im thinking about using this formula

but its a lot of work

is there a simpler way to do this?

[reef thistle]

what do you mean by equality?

there's big O on both sides lol

is it an equality of sets of functions?

[elfin lagoon]

If I choose to prove the affirmative of a universal statement indirectly by way of contraposition, and during the proof of contraposition I encounter a contradiction , does this mean I proved the original statement?

[weary tiger]

hey can anypme help me with this question

hold up I will take a pic

this one thanmks

[stray reef]

ok well

what do you think

[weary tiger]

I know I have to use the binomial theorum

I just dont know what do to when the x and Y have coefficients

[stray reef]

but you don't care about what the terms are

just how many of them there will be

[weary tiger]

so its just the binomial theorum?

oh that makes sense thanks lol

[weary tiger]

hey I tried the binomial theorum I think i did it incorectly but not sure what to do

cant I do 2^12 for this ?

[lilac pivot]

list the possible things you can have

for variables, not the constants

you can have x^12, or x^11y, or x^10y^2, etc all the way to y^12

can you use that to figure out how many terms there can be

[weary tiger]

oh

its 13 thanks

[cerulean ore]

@reef thistle Why do we need to perform BFS/DFS for that question?

We just need to know the number of connected components, that's it?

We can check the adjacency matrix for the node that has whole column 0

That means that the node is connected to no one

[pale epoch]

that just tells you about isolated nodes, not connected components?

[stray reef]

what question

[cerulean ore]

@stray reef https://codeforces.com/problemset/problem/1209/D

[reef thistle]

BFS/DFS is for connected components, yes

I think all the points are raised already

[cerulean ore]

You mean, have been discussed before?^

[reef thistle]

that just tells you about isolated nodes, not connected components?

[cerulean ore]

2 connected components? or 1?

[stray reef]

yes

2

[cerulean ore]

Aah

[stray reef]

one of them is an isolated node though

[cerulean ore]

aah

so, my way only* finds isolated nodes

[stray reef]

indeed

[cerulean ore]

you guys are lovely!

[lilac pivot]

start a dfs or bfs at a node
record every visited node
when the dfs or bfs ends, go to the next node
keep going to the next node until you reach one that hasn't been already been marked as visited (if you visited all nodes, then you're done)
restart at the first step

this algorithm is a pretty easy way to divide up the nodes into connected components

each bfs/dfs you do is one connected component

[cerulean ore]

How do we ensure that we're not recounting a connected component? @lilac pivot as we're creating visited node each time?

[lilac pivot]

because we're marking nodes as visited

in the second step

we never do a dfs on a connected component ever again

since it's already been marked as visited

as in the 2nd last line

[cerulean ore]

when we do restart?

[lilac pivot]

when we find a node that hasn't been visited

[cerulean ore]

wow

[lilac pivot]

let's take a look at this

we start at A, and find a search A,D,E,F

then we end the dfs

then we go to the next element

which is B

that hasn't been visited

so we start another dfs

and get B,C,H

then we go to C

that's been marked so we skip

then we skip D

then we skip E

then we skip F

then we get G, and we get a dfs, G

then we get H

and we skip it

so we're done, we did every node

we are left with 3 things:
A,D,E,F
B,C,H
G

which are obviously the 3 connected compenents

[cerulean ore]

wow man!

This was DFS, let me try if BFS also checks the components

A -> D - > F
D - > F -> E
F->E
E
ending with ADFE marked as visited

bfs(B)
B->C
C->H
H
ending with BCH marked as visited
now only the node that is not visited yet is G therefore,

bfs(G)
G
ending with G marked as visited

No unvisited nodes left, total components = number of times BFS called?

Thank you!

[cerulean ore]

Applications of BFS and DFS looks tougher ;-;

[short wyvern]

What’s the method of finding X in this kind of tasks. Substituting each of the possible answers takes too long, so I was wondering if there is another technique to approach that one

[cerulean ore]

@reef thistle

is this a coloring problem?

[clever nacelle]

Can someone please help me understand what is expected of me here:
2. Fill in the blanks in the following sentence: If A, B and C are any sets, then by definition of
set difference x є A - (B ∩ C) if, and only if, x ________ and x ________ .

Would be that X is in the set of A and is not in the set of B ^ A or am I way off?

[faint narwhal]

What do you mean by B ^ A

[clever nacelle]

B and A.

[faint narwhal]

How do you take the "and" of two sets?

[clever nacelle]

It is the Intersection

x must not be in the Intersection of B and C

[faint narwhal]

Okay, so what's your final answer

[clever nacelle]

If A, B and C are any sets, then by definition of
set difference x є A - (B ∩ C) if, and only if, x є A and x ∉ (B ∩ C).

But that seemed redundant. I felt like there had to be more

[faint narwhal]

No that's it

[clever nacelle]

Thank you!

[clever nacelle]

7. Prove or disprove the following statement by finding a counterexample.
   For all sets A, B, and C, A ∪ (B ∩ C) is a subset of (A ∪ B).

Last Question. How can I use a counter example for proof? That would be endlessly exhaustive because it is always true.
Everything in A will always be apart of the set for both, and for set B, it will always have equal (if C has the same elements) or less (If C has some)

[faint narwhal]

This statement says that it holds for all sets

So for a counter example, you just need to give an example of some sets where it doesn't hold

Since that would mean the statement is false since it claimed to work for all sets

[clever nacelle]

I can not think of a set that it is not true for. As I explained before, A will always be apart of both A ∪ (B ∩ C) and (A ∪ B), and (B ∩ C) means that there will not be any elements that do not exist in B. Would it be false if it is equivalent? That is the only thing I can think. if B = C

[faint narwhal]

I mean then maybe it's true? If you can't think of a counterexample

[clever nacelle]

But if we are told "Find a counterexample" how would that work. if they are all true, wouldn't that be exhaustive checking and that goes infinitely.

[faint narwhal]

But that's what proofs are for

[reef thistle]

@cerulean ore sounds like it, do you have the idea?

[clever nacelle]

I am sorry. I am clearly misunderstanding something. If to get the question correct I need to find a counterexample. but a A counterexample is used to show a general statement is false. How can I get a counterexample if it is always true? Am I missing an option that is false?

[faint narwhal]

Ah you might be reading the phrasing wrong here

Your two options here are

1. Prove

or 2) disprove by finding a counterexample

You don't prove it by finding a counterexample

[clever nacelle]

Ah. Okay thank you that makes sense.

[clever nacelle]

So:
Let, x є A ∪ (B ∩ C)
x є A or B ∩ C
x є A or B
x є (A u B)

[faint narwhal]

Yep, looks good

[patent knoll]

Hey can someone help me with the last part of this problem

[weary tiger]

guys

how I do this sum

$\binom{1000}{50} +2\binom{999}{49} + 3\binom{998}{48}.... .51 \binom{950}{0} $

[vital dew]

epelta:

[weary tiger]

any halp?

[obtuse lance]

I'd try rewriting it in terms of an index, then start to compare to things I already knew which were similar maybe, no guarantee

my guess it's something like the derivative of (x+y)^1000 with numbers plugged in

might have to do something to fix up stuff by playing around

[weary tiger]

$\binom{1000}{950} +2\binom{999}{950} + 3\binom{998}{950}.... .51 \binom{950}{950}$

[vital dew]

epelta:

[lilac pivot]

is the first one or the second one the correct question

[weary tiger]

both are equivalent

🍔

"?

seems like some kind of hockey

[last sigil]

wdym, I believe that they are different?

[weary tiger]

why exactly?

I just changed the bottom

by using identity

[last sigil]

Which identity

[weary tiger]

k+k'=n

like for each k for a binomial coefficent $\binom{n}{k}$

[vital dew]

epelta:

[weary tiger]

there is a complementary coefficent l

k'

[lilac pivot]

they are indeed same

[weary tiger]

thank you sir

now how do I evalaute the sum

[last sigil]

yeah, my bad, sorry bout that

[weary tiger]

guyss?

[lethal sequoia]

@weary tiger A lot of these types questions can be solved using a combinatorial argument. But since you mentioned hockey stick, try $\sum_{k=0}^{50}(k+1)\binom{1000-k}{950}$ and making a substitution of $ m = 1000-k$

[vital dew]

Kei:

[prime chasm]

What's the method for determining if a linear recurrence is homogenous?

wait nvm, found it in my notes

[cerulean ore]

@reef thistle As I am learning, I just checked the editorial

it was a bipartite problem

[whole bluff]

Hey, I’m new to this course and for my assignment I have to find the complement of :

(A-(A u B)) U (A-(B-A))

This whole equation is just equal to A (If I’m not wrong) so would the complement of it just be Ā ?

[stray reef]

indeed

[whole bluff]

Thanks!!

[steel valve]

can anyone explain how y=x^3 is an one to one function or injective?

y(1) = 1, y(-1) = -1

this contradicts the definition of one to one in my notes. one to one must have different outputs and inputs.

i was also given that it has to pass the vertical line test, but im confused which is correct.

[obtuse lance]

by different outputs and inputs that means something else than that

for instance f(x)=x^2 this would not work for f(1)=f(-1) = 1

that's because f(1)=1 and f(-1)=1, they have the same output, so it should be the same input, but the inputs are different

you can see why this is failing the vertical line test because it cuts the parabola at both of those points

[steel valve]

ah ok

so a function can't have same outputs

[stray reef]

this contradicts the definition of one to one in my notes. one to one must have different outputs and inputs.
how does it

[steel valve]

which makes it one to one.

[stray reef]

1 is not the same as -1

[steel valve]

🤦

thanks

[obtuse lance]

I see how it can be interpreted wrong, "have different outputs and inputs" does sound like f(a)=a is not allowed because the output and input are the same

[weary tiger]

@lethal sequoia COuld you elaborate on what you mean by combinatorial arguements?L

[weary tiger]

$\binom{m}{k} = \binom{m}{m-k}$ right?

[vital dew]

epelta:

[stray reef]

yes

[weary tiger]

How would i go about solvong problem 6.3?

[stray reef]

prove by induction

do you know how proofs by induction go

@weary tiger

[weary tiger]

Yes but im not sure if standart method works with inequalities as well

[stray reef]

what do you mean by "standard method"

[weary tiger]

First you check if it works for 0 in this case 2

Then you write it for m and after that (m+1)

[stray reef]

the format of a proof by induction is the same regardless of the nature of the statement being proved. why would it be any different if the statement to be proved happens to be an inequality?

[weary tiger]

Yes i get that

But im not sure about next steps

This is what im writong and im not sure if its correct: "2-(1/m)+(1/(m+1)²) <=2-(1/(m+1)

Wait

I think i got it

No worries

[stray reef]

36 out of what

[cerulean ore]

36

[stray reef]

nice

[cerulean ore]

Thank you guys for helping me! You are my real teachers.

@reef thistle @stray reef @pale epoch and many others!

[weary tiger]

Uhm, is 63^1337 mod(64) the same as (63 mod(64)^1337?

[reef thistle]

hmm

[stray reef]

yep

[reef thistle]

the parens don't match though

[weary tiger]

63 mod (64) = 63 no?

[reef thistle]

well, there's another number it is congruent to

that is easier to carry calculations with

[weary tiger]

maybe, i'm just wondering why i'm getting the second one to 63^1337 and the first one should be 63 according to my calculator 😄

[reef thistle]

yeah, it is 63

[weary tiger]

Nvm I think i just got a little confused with equal/congruent ^^

So how would I go finding that easier number that's congruent @reef thistle were talking about?

[reef thistle]

well

what sort of numbers are congruent to 63?

[cerulean ore]

@reef thistle yo!

my first submission for BFS

[reef thistle]

nice

[whole bluff]

Hey guys, just a quick question...

12. Determine whether each of these functions from Z to Z is one-to-one.

a) f(n)=n2 +1
a) f(n) = n3

When given a question like this I know how to solve but is it possible that you could have a question in which instead of Z to Z, it was something different (e.g R to Z) ?

[cerulean ore]

Yes

They can change the domain/co-domain and ask if still the function is one-one or onto (or both)

[whole bluff]

So for that question if we had f(n)=x^3 for aEZ and bER

How would it change the way we solve it?

[faint narwhal]

Changing the codomain doesn't really how you solve the one to one part

But it does change the onto part

But, changing the domain changes how you do both parts

[whole bluff]

Ohh okay thank you so much!

[weary tiger]

Yeah okay so I figured out that 63 would be congruent to -1, which made everything a little bit easier

[ocean viper]

can someone possibly help me with this problem?

[sour arrow]

It's pretty easy to guess what these numbers might be

Think very simple numbers

[ocean viper]

i tried they dont seem to work

i tried perfect squares

idk if theres another way of doing it other than the method of exhaustion

[sour arrow]

You can't try every real number lol

There's a very simple solution here. If you're thinking squares, you're already overthinking it

[ocean viper]

i dont understand

😦

[sour arrow]

The solution is a = 0, b = 0

[ocean viper]

.............................

omg

kill me

[sour arrow]

When finding examples/counter examples, try to think of 0 objects first as they're usually the right guess

[ocean viper]

okok

ty

wait

a and b are different variables

u can have the same values?

[sour arrow]

Do they have to be?

Well, there is another solution that's pretty similar

[ocean viper]

idk from what i learned say u try to express 2 different even numbers u have to use different variables

a=2k b= 2j

or something like that

[sour arrow]

Seems like you've been working with vectors, but these are real numbers

[ocean viper]

vectors?

[sour arrow]

The question is looking for 0,0 and might not like any other format

[ocean viper]

its right

but im just wondering

[sour arrow]

There is also 0,1 and 1,0

Actually, 0 with anything else

[ocean viper]

0

oh

okok

but say if i run across a problem with different variables , can they have the same value?

[sour arrow]

Yes of course. They don't have to be different unless the question makes it clear they are supposed to be

"distinct" is the word commonly used to say two variables have to have different values

[ocean viper]

oh ok

i dont get why 3 is not right :/

2(3)^2 -5(3) +2 = 5

and 5 is a prime number

oh wait i had to put in the 5 too

smh

~-~

[pseudo abyss]

Hey, I have function f(h)=f(n)+O(g(n)) where g(n)=o(f(n)) how can i try to estimate 1/h(n)? D:

[lethal sequoia]

@weary tiger With a combinatorial argument, try to make an argument by counting instead of using algebra

[weary tiger]

@lethal sequoia what do you mean?

[earnest canopy]

I wanted to see which values are both in the fibonacci sequence and sum from 0 to n sequence, and tried programmatically with values close to long overflows, and didn't found any match except the 4 first, is there a mathematical way to prove that there is no other match except those 4 first, even going up to infinity?

[reef thistle]

hmm

@earnest canopy Well I know the only powers in fibonacci are 8 and 144...

there's a good chance we can prove

so for the sum 1 to n sequence, k is a sum from 1 to n if (and only if) 8k+1 is a square.

A number k is Fibonacci iff at least one of (5k^2 + 4) or (5k^2 – 4) is a square

Let's just whack 5((a^2+a)/2)^2+4 = b^2

5(a^2+a)^2+16 = 4b^2

5(a^2+a)^2 = 4(b+2)(b-2)

gcd(b+2, b-2) is either 1, 2, 4.

if 1, then either (b+2)=5c^2, (b-2)=d^2 or (b+2)=c^2, (b-2)=5d^2, probably can attack from there.
so 5c^2-4 is square in first case, 5d^2-4 is square in second case... whoa new fibonacci numbers

[earnest canopy]

I read everything, but my brain isn't big enough to process everything you wrote I guess 😂

but didn't know about those properties of "8k+1 have to be a square to be a 1 to n sum", pretty interesting

so here you brought some paths but no conclusion? I don't think I'm good enough to help you continue the path 😦

also what is gcd function?

[faint narwhal]

gcd is greatest common divisors

[earnest canopy]

ok, know those names in french but not in english, thx 👌

[raven lodge]

Hey anyone can help me doing this?

[faint narwhal]

What have you tried?

[raven lodge]

Idk where to start so no

[faint narwhal]

Think about it

[reef thistle]

let me think

whoops forgot definition of theta

Okay, consider each part

[raven lodge]

Do I need to prove both big Oh and omega?

[reef thistle]

what happens after log log n presses?

You may want to write n =2^m

[raven lodge]

But how to represent the precision smybol

[reef thistle]

what precision symbol?

you mean $\epsilon$?

[vital dew]

Element118:

[reef thistle]

@raven lodge

[raven lodge]

Yes

How to represent it in log

[reef thistle]

what do you mean?

representing it in log?

@raven lodge

[raven lodge]

Hmm can I directly prove big theta taking log in both sides?

[reef thistle]

the first line you would need to be careful by bounding the proportionality

[raven lodge]

I have to write down the equation is larger than 1 and smaller than 2?

Or do I need to explain more on why 1+e =2^e?

[reef thistle]

you probably should write that n^(2^-k)<1+e<n^(2^-(k-1))

[raven lodge]

Okay thanks

[ocean viper]

how do i approach this type of problem?

[reef thistle]

@ocean viper any ideas?

try simulating the problem

[sweet island]

Need help with the following probability question: If there is a best of 7 soccer series, what is the probability that the team that wins the first game goes on to win the series. Assume that both teams are equally likely to win the game and the games are independent events.

[outer spire]

Casework: what’s the probability that the team wins in 4,5,6,7 games

[jovial rock]

@sweet island Would that be (1/2)^6? Because there are 6 more series and in each series it's a coin toss between the teams

[outer spire]

The answer is 21/32

[cerulean ore]

How does the matching of team works?^

Category wise?

one team vs all other teams?

[stray reef]

there are only two teams

they play a best of 7

[cerulean ore]

oh

[clever nacelle]

My answer is in bold. I am struggling a bit with understanding. I have watched a few videos and read the book. My understanding is it may be possible with a subcircuit? If anyone has a resource to help me understand please link me.

[jovial rock]

@outer spire If you don't mind me asking, why?

[pale epoch]

@clever nacelle i doubt you defined eulerian circuit that way, usually this is a theorem, but that's correct so far

for the other question your idea is correct

but it could be explained better

you can maybe split it into 3 cases: starting in the "left" part of the graph, the "right" part and starting at i

[clever nacelle]

Okay. Thank you.

Is that better?

[reef thistle]

that would do

basically

for hamiltonian cycle, in general, if you remove k vertices, you should be left with at most k connected components

[sick yoke]

Hey guys, just joined the discord. I'm working on some exercises from Rosen's discrete math book and am stuck on a question. How is 8x2^n-1 turning into 8x2x2^n-1.. where is the second 2 coming from?

[reef thistle]

It's 2^(n-2)

@sick yoke

[sick yoke]

sorry that's what I meant 8x2x2^n-2

I just did some research, and it's an exponent rule that lets us do that

definitely gotta brush up on my fundamentals, it's been a while since I was in school and am struggling in college

[ocean viper]

can someone possibly help me wif this xd

[reef thistle]

@ocean viper simulate the problem

[ocean viper]

im not sure how to approach simulating it

[reef thistle]

try thinking what happens at specific times

@ocean viper

[ocean viper]

at 8 min thaat guy will be at the start and the 10min guy will be still running

[reef thistle]

then?

try other times?

[ocean viper]

at 10 min the 8min guy will be running? aanad the 10 min guy aat starting?

8,16,24,32,40
10,20,30,40

[reef thistle]

so...?

[ocean viper]

40

min

[kind tapir]

More generally, if n runners are simultaneously running with constant speeds on a circular track, beginning at the same spot at the same time, and for all j, the jth runner first returns after aⱼ minutes, then the jth runner will be at the start after i minutes if and only if j divides i, and thus the least number of minutes after which all runners will be at the start simultaneously is the least common divisor of all the aⱼ's, that is lcm(a₁, a₂, ..., aₙ).

[ocean viper]

o-o

uhh

i dont understand rip

[kind tapir]

your solution is correct, I just proved a more general statement

[ocean viper]

what does the x mean

\

[placid raptor]

It is Cartesian product of sets

[ocean viper]

so {A U B} , {A U C}?

[stray reef]

no

[kind tapir]

the set of ordered pairs whose first element is in A and whose second element is in B

[stray reef]

$A \times B$ consists of ordered pairs $(a,b)$ where $a \in A$ and $b \in B$

[vital dew]

Ann:

[kind tapir]

So, for example (1, green) is a member of Integers * Colors

[stray reef]

for example

if you take S = {spades, hearts, diamonds, clubs} and R = {A, K, Q, J, 10, 9, ..., 3, 2}

then S x R is a deck of cards

[ocean viper]

oh wait i remember now

say a = {1,2,3} b {4,5,6}
axb would be {1,4} {1,5} , {1,6} {2,4} {2,5} {2,6}??

and so on

[stray reef]

no

[ocean viper]

o-o

[placid raptor]

It would be {(1,4),(1,5),(1,6),...}

[ocean viper]

o

[stray reef]

ordered pairs

not 2-sets

[ocean viper]

okok

[wanton sable]

not sure if this is the right channel for this, since this is a question from one of my discrete math courses, but i was wondering if i could get some help in solving this one?

i'm torn between k^n and n!k

i have a feeling it might have something to do with n choose k or stirling numbers of the second kind

[placid raptor]

Let's say you have k empty boxes. And you have n objects that you can put in them

How would you approach this problem?

@wanton sable

[wanton sable]

i figure it would have something to do with factorials right? like n choices for box k, n-1 choices for box k-1, etc

or is that completely off?

[placid raptor]

First pick one object out of n objects

How many ways you can put it in boxes?

[wanton sable]

k ways?

[placid raptor]

Yes

So pick another object

Still k ways, right?

[wanton sable]

yep

oh ok i think i see the bigger picture here

[placid raptor]

And put such n objectd in those box

So what do you think answer should be?

[wanton sable]

n!k ?

[placid raptor]

No!

[wanton sable]

wait really?!

O

wait is it k^n

[placid raptor]

Each object can be put in k ways

And you have n such objects

Yes, it is k^n

But did you really understand?

[wanton sable]

yes, i understand when you explained it using boxes

thank you :D

[placid raptor]

You're welcome then!

[subtle halo]

Hi

Im currently studying DFA/NFA

Im struggling with the language here

why is there a hat on the transition function

Could somebody put into english what that is trying to say? Thanks 🙂

[urban talon]

I’ve just now heard of DFA so I can’t really help except to search stuff on google. Maybe this will help

@subtle halo forgot to ping you

[pale epoch]

@subtle halo yeah, it mostly likely refers to the extended transition function

to put it into english, the transition function takes a state and a single letter and outputs the state reached

the extended transition function can take in a state and a string (multiple letters) and outpute the state when entering this string

in this case i assume $\widehat{\delta}(x)$ is the state that is reached when inputting the string x

[vital dew]

Lochverstärker:

[pale epoch]

yes, that's it

L(M) is the language accepted by the DFA, i.e. it's all strings that when entered end up in a final state

[civic phoenix]

hi, does anyone know if there is any generalization of the knapsack problem with lower and upper bounds? So the elements that one can include in the knapsack such that the knapsack does not have a weight less than N and more than M ?

[reef thistle]

shouldn't be too hard to generalise

[subtle halo]

@pale epoch ah that makes sense, thank you!!

[summer gull]

hi

can someone help me undertsand a few things about logic?

in discrete mathemetics terms

I know that P -> Q is synonymous with ~P v Q, but is ~P -> Q synonymous with just P v Q? Or do I follow demorgans laws here?

[summer gull]

?

[pale epoch]

the former

you can always make a truth table to check