discrete-math

[tidal tulip]

ok that was clever

the trick was to use the idempotent law which i was unaware of

basically states (x in A and x in A) = x in A and (x in A or x in A) = x in A

and then you use assoc

comm

group them

get what you desire

[tidal tulip]

is that right for idempotent law?

[wide vine]

I guess but really it just says if you have some set A

A U A = A

A n A = A

so in your case when they said

[tidal tulip]

ok that was the idea i was missing - very helpful

ty for helping i learned something

[light heath]

yea I ended up redoing it by using a specific example

this is my updated solution to number 22

could someone give it a look

[weary tiger]

anyone can someone please explain me the formula for combination with repititions

i am really confused

[outer rune]

how do i solve thiis

[cerulean wind]

chinese remainder theorem and eulers theorem

[outer rune]

i dont know what that is

oh

i know what that is but i learned this before chinese remainder theorem

is there a more basic way

[cerulean wind]

it sounds like this is from a class you're taking. maybe try looking at past lecture notes? im not sure of a more simple method

[woven lagoon]

how would I begin to prove Z×Z→Z is onto if f(x, y) = x^2 − y^2?

[weary tiger]

well, onto implies surjection, so think about that

[cerulean wind]

break it into cases depending on whether or not z is even or odd. also recall that x^2 - y^2 = (x - y)(x + y)

[onyx hull]

Anyone have some good youtube links to learn this?

My lecture content isn't great

[cerulean wind]

this is more suited for #prealg-and-algebra or #precalculus

[obtuse lance]

2=x^2-y^2 has no solution mod 4

[weary tiger]

I hope I'm not missing something, but b) and c) are unanswerable correct?

ik this is more algebra but i didnt have access to that channel

[cerulean wind]

why do you think they are unanswerable?

[weary tiger]

Because for the composite relation to be defined, you need to have it like a chain, so S o R is defined because R: A --> B and S: B --> C

And I don't even know where the elements in the ordered pairs of T come from

T could be from any set to any set

[cerulean wind]

T is a subset of {1,3,4} x {1,4,5}. R is a subset of {1,2,3,5} x {2,4,5}.
that said, T is also a subset of {1,3,4} x {1,2,3,4,5} and R is also a subset of {1,2,3,4,5} x {2,4,5}
note {1,2,3,4,5} = {1,4,5} U {1,2,3,5}

i agree that the problem statement lacks precision

but the question itself is certainly answerable

[weary tiger]

Yes certainly lacks precision because the '1's in T's ordered pairs can be different from the '1's in the other ordered pairs of R or S

I guess he just assumes you will assume that they are constructed from the same sets

[weary tiger]

Thank you

[cerulean wind]

im not sure what you mean here

[wide vine]

i think they are saying the 1's might represent something else

[weary tiger]

Yes

exactly

[cerulean wind]

ah, for me that would be a reach

[weary tiger]

I just assumed since I'm in a mathematical reasoning course, that might not be out of the realm of possibility for him to pull something like that

[cerulean wind]

if thats the case then you should be arguing with me over whether or not the 2 in Z is the same as the 2 in R, or the 2 + 0i in C

1 is a 1 is a 1 is a 1 unless otherwise specified. it would be weird one of the 1's here were like, the identity element of some group

[weary tiger]

I could make a case that they aren't the same, as in, the 2 in Z represents 2 'hatches' on the non-complete number line, the 2 in R represents 2 hatches on the real line, and the 2 + 0i in C represents 2 hatches along the real line, in the complex plane

if we're talking about the elements representing something

but i guess that would be false since R is constructed from Z

[wide vine]

well they are subsets

[weary tiger]

yeaaa

just realized that

[cerulean wind]

realized as subsets

[weary tiger]

but you're right, i'll just go with the assumption he wants us to make to complete the problem

thank you

[wide vine]

wdym by that

you mean it isn't so easy to show it is true?

[cerulean wind]

Z (technically) isnt a subset of Q, Q isnt (technically) a subset of R

but its so minor that we just ignore it

[weary tiger]

ohhh since Q is constructed by equivalence classes

[cerulean wind]

yes

[weary tiger]

makes sense

[cerulean wind]

but again, thats really pedantic and technical and nobody really cares

[weary tiger]

except the logicians 😭

[formal flicker]

Does anybody know a good YouTube video that explains this?

[spring surge]

I am writing poker related software.. What maths should I look up to into in order to minimize the combinatorical calculations ? I'd like to try find some algebraic pattern which i can exploit reducing load on CPU.

[outer rune]

What do i need to do to prove the divisibility rule of 2

like how do i prove that a number is divisible by 2

lets say N = 5814, what steps do i take to prove that 2 | 5814

in my professors lecture it has something to do with congruence but i dont understand

[coral parcel]

Multiply 3907 by 2 and point to the result?

[stray reef]

"prove the divisibility rule of 2" and "prove that a (particular) number is divisible by 2" are two very different tasks

[outer rune]

My professors notes on the divisibility rule by 2

i dont understand what im supposed to do

what is the rule

theres just a bunch of stuff but what is the actual rule that i use?

[stray reef]

2 | N <=> 2 | (last digit of N)

that's the rule

said in words, "a number is even iff its last digit is even"

[outer rune]

so whats the mod stuff

like the N (mod 2) and congruence stuff

[stray reef]

that is how your professor chooses to prove why the rule works.

[outer rune]

ohhhhhhhh

okay, thank you

[stray reef]

a little overkill and a little abuse of notation but it works as a proof

[outer rune]

yeah it rreally confused me

[stray reef]

the proof hinges on the fact that 10 is even and that the last digit of a number is, by definition, its remainder mod 10

[wide vine]

Are you trying to set up a boolean equation that will be true under specific xyz inputs?

Because the common approach is sum of products

you only worry about the solutions the F(x,y,z) that evaluate to 1 and write out the entire boolean expression that gave you 1

Here is one example from my notes that goes over it

I would recommend look up "Sum of products" and converting truth tables as sum or produts

This video seems okay

https://www.youtube.com/watch?v=xnLBbOYYnHM

There is also a product of sums form but doesn't seem your assignment is looking for that

and you might have to simplify those sum of products

[outer rune]

how did my prof get from d | 2014 and d | 2067 to d | 2067 - 2014

[little prism]

d|2014 means 2014=dk, the other means 2067=dm. then 2067-2014=dm-dk=d(m-k) and d divides the difference

[sacred dune]

Could someone provide a hint to this problem from my discrete math class? I’ve been stuck on it for >4h… It asks us to prove that given n reals a_i with |a_i|>= 1, the number of solutions to -1< e_1a_1 + … + e_na_n < 1 with e_i = +-1 is less than or equal to n choose floor(n/2)

I’ve mainly been focusing on trying to solve it for a_i integers and hopefully gain insight there but I haven’t made any progress: I’ve looked at a bunch of different structures that might give me some insight but except for a few simple realizations I haven’t gotten much

[wide vine]

can you give me a few examples of this in action because I am not sure what is going on

or 1

[sacred dune]

For example take a_1 = 1.5, a_2 = 3, a_3 = 2. Then the possible solutions are a_1-a_2+a_3, -a_1+a_2-a_3, and this is smaller than 3 choose 1

(ie 2<=3)

[wide vine]

so as long as |a_1| >=1 and by solutions you mean you mentioned that by taking either sums or differences it will fall between -1 and 1?

[sacred dune]

Yes, a solution is a sequence (e_1,…,e_n) in {-1,1}^n

And they are coefficients of the sum

[wide vine]

how are the other numbers a_2 and a_3 generated or is it only important that a_1 has a magnitude >=1?

[sacred dune]

No no a_2 and a_3 aren’t generated

[wide vine]

oh...

oh my bad

[sacred dune]

They are all given and of magnitude >=1

[wide vine]

(a_i)

okay

[sacred dune]

Just to bring you up to where I got to, here are the only simple results I got

We can suppose all a_i positive wlog. If the a_i’s are integers they must have even sum (say 2k). We are then looking for subsets of {a_1,…,a_n} whose elements sum to k. This seems the most promising approach to me for the integers case

Reason I’m considering integers is because replacing all the inequalities with 1 by M yields an equivalent problem, and so when solving for rationals we can forget the common denominator

And then I was hoping density might lead the result for the reals

[wide vine]

this problem sounds hard. Is this like a normal first discrete math course?

[sacred dune]

Yeah

[wide vine]

Anyways I think I will play around with it and see if I have anything insightful

Is there a specific topic you are doing right now?

[sacred dune]

No this is exam revision

[wide vine]

oh

[sacred dune]

In general we’ve seen things like generating functions, graphs, linear recurrences, mobius inversion, asymptotic estimates for binomial coefficients, probability, and some other stuff

So a typical first course

Since this is supposed to be exam level there’s probably just one smart idea that resolves it in like 15m but I can’t figure it out

[wide vine]

we never touched those topics 😦 other than graphs and a bit of recurrence and closed form about very specific functiosn

[sacred dune]

I don’t think it needs an intensive theory though, just a change in perspective

[wide vine]

we did sets, logic, induction and recursion, basic function stuff (domain, range, codomain, injective, surjective, bijective), relations, directed graphs

[sacred dune]

It might be cause it’s second semester course

So the function stuff was covered first sem

[viral crown]

If the a_i’s are integers they must have even sum (say 2k).
isnt this just

wrong

?

[sacred dune]

If they have odd sum you don’t get a solution

Just pass mod 2

[wide vine]

do you know the cases that will always maximize the upper bound?

[sacred dune]

For even n just take all a_i equal

For odd n I’m not too sure

[wide vine]

i guess I probably will be of little help but let me know if you figure it out (ill look at it after my linear algebra stuff not that I think I will not fair much better)

[viral crown]

i think maybe since it's asking about n and not specific kinds of a_i focusing on n could be better?

for example if n is even or odd?

[sacred dune]

I mean for the case n is even there is that intuition of the most balanced set being when all the a’s are equal

[viral crown]

also wait. say a_1 = 103102381, a_2 = 2, and a_3 = 3

[sacred dune]

This notion of balance made me think there might be something to do with entropy but I don’t know anything about entropy

[viral crown]

oh, wait

less than

[sacred dune]

Then no solution

[viral crown]

if you assume all are positive then there are solutions iif you add some of the a_i you are +-1 if you add up the others and the the number of solutions corresponds to the different ways of adding them up, right?

[sacred dune]

Could you rephrase that

[viral crown]

yes

[wide vine]

I think they are saying the solutions are defined in terms of the coeffiencts

[viral crown]

^

just getting confirmation since not entirely sure

[sacred dune]

I mean yeah solutions are the coefficients 🤔

It doesn’t really matter what the solutions are though only how many there are (or there are at most)

[viral crown]

i'm saying that there are solutions iif you can add up some combination of the a_is such that if you add up the others and add or subtract one, then the inequality between the two changes or turns into an equal sign

[wide vine]

well if all the co-effiecnts are positive as a solution then you would also know that having all negatives is a solution, right?

[viral crown]

and the number of solutions is the same as the different number of ways to add both of them up

[sacred dune]

Im still not getting you

[sacred dune]

Can’t have all coefficients positive

[wide vine]

oh

duh

[sacred dune]

But yes there is a symmetry

You can always flip the coefficients around

[viral crown]

wait let me rephrase

If all a_i are positive, then there are solutions iif you can sum some combination of them such that if you sum the rest, the difference between them is at most 1.

[sacred dune]

Why do you say that

Oh positive sum

Yeah sure I agree (though it would be at most 2)

[viral crown]

difference

[sacred dune]

Oop yeah

[viral crown]

and i think this implies that there can only be an even number of solutions

[sacred dune]

I still think it would be more helpful to start thinking about integers

[sacred dune]

This follows from the coefficient symmetry

[viral crown]

that too

[sacred dune]

I should be getting a correction of this exercise in a week or so I’ll let you know if I haven’t figured it out by then

[raven grove]

can someone help me prove this?

if a^2 is a multiple of 3 ,then a is a multiple of 3

and a is a natural number

[coral parcel]

Do you have Euclid's lemma?

[raven grove]

idk what that is

just need to prove that using a proof by contrapositive or proof by contradiction

[cerulean wind]

do a proof by cases: a must be of the form 3k, 3k+1, or 3k+2. just rule out the cases where a = 3k+1 or a = 3k+2.

[weary tiger]

can anyone explain the combinatorial proof of pascals identity?

C(n,r) = C(n-1, r-1) + C(n-1, r)

[haughty garden]

Imagine you want to find the number of ways to pick r objects out of n many possibilities and let’s consider one such object. Call this object x.

On the one hand, the number of ways to pick r objects (with or without x) is simply C(n, r). On the other hand, let’s consider separately what happens when we pick or don’t pick x.

If we pick x, then you are ensured that this object is in the subset of r objects that we pick. To pick the remaining objects, we exclude x from our total number of objects AND the number of objects we have remaining to choose. In other words, we have n - 1 objects remaining to choose r - 1. You can do this in C(n - 1, r - 1) ways. See if you can reason about C(n - 1, r) by considering what happens when we exclude x from our subset of r objects

[weary tiger]

If we exclude x, then we have n-1 total objects (as x isn't included), and we have r objects to choose from those n-1 objects because x wasn't picked

is that good reasoning?

[haughty garden]

Yep

[viral crown]

look up the fundamental theorem of arithmetic

[wide vine]

@sacred dune any luck on your problem?

[true venture]

Because e_i can only be +1 or -1, there are 2^n possible arrangements of e's for a set of n real numbers. And if all the e values in a given arrangement are the same sign there is no possible solution.
There will always be only two arrangements with all e having the same sign.
So the number of possible arrangements of e coefficients for a given set of n real numbers with a solution is (2^n)-2.
(2^n)-2 is always <= n choose floor (n/2)

[true venture]

That is my thoughts, I'm not sure how to make it a proof

[true venture]

Hmm, actually there are values where all -1 e's will work but then, two of the other possible combinations would not work. So I still think there are at most (2^n)-2 solutions which is <= the range given

[unreal stump]

The thing is $\2^n-2 > \binom{n}{\floor{\frac{n}{2}}}$

[vital dew]

Drake

[unreal stump]

@true venture

[unreal stump]

Because $\2^n=\sum_{i=0}^{n}\binom{n}{i}\$
There's a term where i is $\floor{\frac{n}{2}}$

[vital dew]

Drake

[true venture]

Oof I see

[sacred dune]

Yeah as drake pointed out the final inequality is wrong

If you want a combinatorial interpretation for n choose n/2 here, the case n= even, a_1=…=a_n achieves this upper bound

[formal flicker]

Can someone please expand this definition

[obtuse lance]

it's not really a definition, more of a theorem

[cerulean wind]

it says that X bijects onto a proper subset of itself, so i can squeeze a "smaller" copy of X inside of X

[viral crown]

so if you assigned n to 2n

that would be like that?

since set of even numbers is obviously a proper subset of n

[obtuse lance]

yep

[viral crown]

oh cool cool

[formal flicker]

Thank you

Can you please also explain the proof of part a of the theorem ( the circled part)

[west vessel]

Can you take a better picture

[formal flicker]

Sure

[formal flicker]

Hey I seriously need help with this

[sacred dune]

What do you need help with?

Not managing the last step?

[silent frost]

I have bezoutyish equation 27x + 59y = 1, using egcd I got x = -24, y = 11
How do I find all the other solutions?

Oh ok, so x mod 59

so -24 + 59n and 27n + 11 are solutions?

Wait no

-24 + 59n is ok

11 - 27n is what i need

but why...

Yeah so all solutions of 27x + 59y = 1, are:
x = 59n + (-24)
y = -27n + (11)

But why is 'y''s one a minus?

actually nvm

[unreal stump]

Hint: what can you say about solutions of 27x+59y=0

[silent frost]

I was going to do:
27(59n + (-24)) + 59(-27n + 11) = 1
so
27*59n + 27(-24) + 59(-27)n + 59(11) = 1
27*59n - 59(27)n + 27(-24) + 59(11) = 1

[unreal stump]

Well ok you are right

[silent frost]

So given any ax + by = c

And if I have solutions x, y

I can go ahead and add (abn - abn) to the equation

And generate all the other solutions...

[unreal stump]

That won't cover all the solutions in general

Like take 2x+6y=4

[silent frost]

Yea?

x = -1, and y = 1

Then 2x + 6y + (2 * 6n - 2*6n) = 1
2x + 2*6n + 6y - 2*6n = 1
2(x + 6n) + 6(y - 2n) = 1

So all solutions are x = 6n - 1, y = 1 - 2n?

[unreal stump]

Not exactly

[silent frost]

Where have I dungoofed?

[unreal stump]

x=3n-1,y=1-n is the general solution

[silent frost]

Oh I have to remove the common factors?

[unreal stump]

Yes

[silent frost]

And then it's general... yeah that makes sense

[unreal stump]

Now do you think this is sufficient?

Or do we have to do something else

[silent frost]

Idk man looks good to me...

[unreal stump]

Yea it's enough

[silent frost]

Is there a prettier way of doing it?

Rather than the weird method i used from (abn - abn) then common factor?

So is the general method:
"all solutions" will be:
x = bn + u
y = ab - v (where u, v are certain solutions)
Then removing common factor from b, n

[unreal stump]

So let (x_0,y_0) be a particular solution to ax+by=c,then suppose (x_1,y_1) is another solution,then
a x_1+b y_1=c
a x_0+b y_0=c
a(x_1-x_0)+b(y_1-y_0)=0

Which implies it's enough to find all solutions to ax+by=0 to find the general solution for ax+by=c

[weary tiger]

I am a bit confused on the topics of recurrence relations in discrete math. I would like to practice these types of problems but I have a couple of questions

1.) Is iterative method and recursive method the two traditional ways to approach these types of problems? My professor said to know iteration way, so I am wondering what are the other ways to approach solving recurrence relations

just to clarify I'm not really sure what is meant by iterative and recursive? Like I know in programming iterative means typically the usage of for/while loops and recursion is just recursion, but I am not sure what that looks like when solving these problems?

2.) Does anyone have a good guide, it seems that there is not a lot of material on how to solve nonhomogeneous/homogeneous linear recurrence relations
Perhaps a video, or a link to a blog or something

[silent frost]

Right so I can try find the solution by considering the homogenous version?

So solving the homogenous version is the "nicer"/"more standard" method for finding general solutions?

[unreal stump]

Yes

Well you can say b divides ax

Which is to say b/gcd(a,b) divides x

So this tells us a solution has to be of the form
x=(bk/gcd(a,b)),y=-ak/gcd(a,b)
For some integer k

[silent frost]

Ok, that makes sense, but that feels like it'd have less solutions than the weird:
x = u + bn, y = v - an, and then remove common factor from a & b
method

Oh

but it'd be the same

since that's doing it for homogenous

and u, v = 0

Ok, thats cool

Damn, nice. That makes a lot more sense

Thanks heeps Drakesama

[coral parcel]

I don't think there is a generally understood distinction between "iterative methods" and "recursive methods" here. The words have clearly distinct meanings in programming, but in a mathematical treatment they tend to blur more together. If they have crisp meanings in the particular course you're following, you may need to consult the course material.
Methods for what exactly, though? There's a difference between trying to find a closed expression for a function that satisfies a recurrence equation, or finding a practical way to compute terms of the sequence defined by a recurrence without going through a closed expression. Or for that matter, finding a shortcut to just the asymptotic behavior of the solution without getting either a closed formula or concrete values.

For example, consider the Fibonacci numbers, the mother of all recurrences. Binet's formula is closed and exact, and is useful for some purposes. But if you want to use it to the exact value of the 1024th Fibonacci number, you need to calculate with an extremely precise approximation of the golden ratio. Then it's much simpler to use successive squarings of an integer generating matrix. On the other other hand, if you want asymptotic growth, Binet's formula immediately tells you what you need to know, and you can ignore its practical shortcomings.

[true venture]

Did you figure out a correct solution?

[sacred dune]

dont really have time to think about it since it's my last exam and i have to focus on my other exams for now

but ill get back to it once im done with all the other exams

[keen geode]

Is this correct?

[pale epoch]

no

can you provide your reasoning?

[coral parcel]

Looks like they think an element is in an intersection if it is in more than one of the input sets.

[weary tiger]

what x could give you f(x)=0?

[stray reef]

none of this is correct and there are multiple issues with your notation

[keen geode]

Thought so, didn't seem correct...

Cheers, I'll look into it

[keen geode]

I just wanna be sure that I'm correct in my way of thinking here;

For the union, the interval ends up being (0,1) because for all i>1, S_i is a subset of S_1, therefore the union is S_1

For the interssection, since for all i>1 S_i is a subset of S_1, and because as n goes towards infinity the final set S__(infinity) is {0,0}, the infinite intersection is thus an empty set?

Also, I'm confused why the person isn't using {} for the sets in S_i, is that correct?

[pale epoch]

the first one is correct

there is no $S_\infty$ however

[keen geode]

And are unions and intersections always written as intervals?

[vital dew]

Lochverstärker

[keen geode]

oh, so how can we justify the second intersection?

[pale epoch]

ok so

take an element in the intersection

it must be in every S_i

[keen geode]

ohhhhh ok

[pale epoch]

then for example it certainly must be in S_1 so its between 0 and 1

and now you can try to find an S_i its not in

so whatever element in S_1 you choose is not in some S_i

then the intersection is empty

the other things about curly braces is hmm

you made this error in the other thing you posted (though thats not the only one)

of adding an extra set of curly braces

i would review the definition of intervals

$(a, b) \coloneqq {x\in\bR \mid a < x < b}$

[vital dew]

Lochverstärker

[pale epoch]

so if you enclose it in another set of curly braces, its a set in a set

and we want a set of numbers

[keen geode]

ooooook

ok, so the intersection would be a set

[pale epoch]

and like ${\bN}$ for example is a set of one element

[keen geode]

and the union is always an interval

[vital dew]

Lochverstärker

[pale epoch]

an interval is a set

its just a different notation

[keen geode]

oh right!

so (0,1) is a non listable set (it's infinite)

[pale epoch]

sure

[keen geode]

but {0,1} is a set of cardinality 2?

[pale epoch]

yes

[keen geode]

fantastic, thanks a lot

[pale epoch]

i think a good heuristic is to ask yourself what the elements of the sets you are given are

and what the elements of the set you are writing down is

if you take the union/intersection of a set of numbers then the result should be a set of numbers

and not a set whose elements are sets for example

[keen geode]

ok gotcha

I'll try and do some practice problems

thanks a lot for your help

[pale epoch]

👍

[keen geode]

I'm ready to face the fact that i'm probably wrong once again, but if I'm not yipee I guess

[fading gust]

man wtf is all that crap

[keen geode]

wdym?

[coral parcel]

The first two lines are good, but the third is a bit iffy. There are ways to give a meaning to "lim S_n", and they'd even agree with what you say, but I doubt you have those definitions available.

[keen geode]

ah

[coral parcel]

The argument for the middle line you should be making is something like: Because the limit of the fractions is 1, every number that is less than 1 is also less than one of the fractions. Therefore it is in one of the Sn, and therefore it is in the union.

[keen geode]

Ok, I see the logical thinking

thanks a lot!

[stray reef]

Because the limit of the fraction is 1, every number that is less than 1 is also less than one of the fractions.
and this argument does not even hold wate

water*

if anything you need to say that the supremum of n/(n+1) for n ranging over the natural numbers is 1.

otherwise the same argument would have you conclude $\bigcup_{n=1}^{\infty} \paren{0, \frac{n+1}{n}} = (0, 1)$ and not $(0, 2)$ as it actually is.

[vital dew]

Ann

[keen geode]

ouf, and I was just about to post another one with the same argument

[coral parcel]

Okay, strictly speaking I only argued that (0,1) is a subset of the union, not that it is the entire union.

The fact that 1 and numbers larger than 1 are not in the union needs separate reasoning.

[tribal pond]

Is it possible that ax=ay and x not equal to y and a not equal to 0??

[keen geode]

How about this?

[coral parcel]

Here the limit is in fact irrelevant.

[keen geode]

Yeah, I thought so

so i can cut that bit out and just say what follows it?

[coral parcel]

Hmm, it seems to be arguing the wrong way. It is also true that an element that is in all of the sets must be in S_42, but that doesn't mean S_42 is the intersection.

The critical fact is an element of S_1 is also an element of all the other sets. Or in other words, that S_1 is a subset of each of the S_n's.

[keen geode]

Is this reasonable enough?

[sick dirge]

To me it seems this is more an explanation than a proof. To prove those two are equal, you need to prove two subset relations. Any element in the intersection must be in S_1, so it must be in (0, ½) and you'll prove that the intersection is a subset of (0, ½). You also need to show that every element in (0, ½) is in the intersection of the S_n. This will let you conclude that (0, ½) is a subset of the intersection.

Also I think you're confused about the concept of a set. You refer to a set S_x that is in all sets S_n, which doesn't make sense.

[coral parcel]

It's not uncommon to say "in" (or "contains") about both membership and subset, and leave it to the reader to figure out which of them makes sense.

Unfortunately this tends to create problems for students who have not yet firmly grasped the difference.

[sick dirge]

Still though I don't think this is sufficient as a proof. It seems like an intuition-based argument and does not use the notion of sets being equal $A = B$ iff $A \subseteq B$ and $B \subseteq A$.

[vital dew]

PhenomPlasma

[coral parcel]

Intuition is important too, though. We're not sure exactly what is expected of Dealersgrip here. (It might be a "lean to write proper proofs" exercise, in which case your criticism is definitely justified, or a "develop a feeling for how sequences of sets behave" exercise).

[keen geode]

more of a developing a feeling exercise

I started getting into set theory very recently, so i'm just trying to get the hand of it

[sick dirge]

Hm, in that case I'm not very sure if what you wrote would be sufficient. Still though I'd recommend writing it out in a more formal manner. It'll also make your thought process clearer.

I think you have the main idea that because S_1 is the smallest of the S_n that the intersection should be S_1, but the language is a bit vague.

[keen geode]

In the goal of being sure that I've understood the idea of infinite unions and intersections, I just want to see whether this is correct or not. The next time I post here I'll offer a whole reasoning behind my statements:

[coral parcel]

The last line of that seems to claim that, for example, pi is in one of the Sn's. Which of them would that be?

(Or even just 3).

[keen geode]

I don't understand 😅

the union of all the Sn is the interval from (1/2) to infinity

or maybe I'm totally wrong

pi is in onne of sns I thinkk

ohhhhh it's not

hmm, how can I re-write this?

[coral parcel]

I can't offhand think of a nicer way to write the resulting set than the infinite union itself ...

[keen geode]

that sucks

[nimble sequoia]

what about something like $$\left{ n \in \mathbb{R} | \floor{n} = \floor{n-\frac{1}{2}} \right}$$

[vital dew]

Nathan_

[nimble sequoia]

its not quite right but i think its close

[wide vine]

so are you asking is that equivalent to R or T?

well okay then

anyways your answer is yes

[weary tiger]

even if a = 0, this is still ''technically'' incorrect, which is one of the reasons why division by 0 is undefined. but to answer your question, no, it is not possible

[tribal pond]

Ok thanks

[buoyant zephyr]

If I prove that a language would have a pumping length greater than any finite number, have I proven that the language is not a regular language? Idk if you can prove that it would have a pumping length larger than any finite number, but I can prove a language has some string that needs n+1 states for a machine to accept it no matter what n equals. I'm trying to prove that the set of strings that repeat once (w°w) isn't a regular language, and my idea right now rests on showing that for any string in the language, you can make a string not accepted by the machine by simply adding another character to both strings, because you can pump a string of ww by designating y to be the entire string. I figure this is really the only way to prove it's not a regular language? But please do tell me if there's another, simpler way.

This implies that the machine would have to have an infinite number of states to accept this language, I think.

Which contradicts the definition of an FSM

[pastel hollow]

my book says that
$$\sum_{k > N}\frac{1}{2^{k-1}} = \frac{1}{2^{N-1}}$$

[vital dew]

EdgarAlnGrow

[pastel hollow]

how are they getting that?

[weary tiger]

anyone know how i can practice combinatorial proofs

i've got a test tomorrow with some combinatorial proofs/arguments on it

[sick dirge]

Well you essentially have that $\sum_{k > N} \frac{1}{2^{k - 1}} = \sum_{k = 1}^\infty \frac{1}{2^{k - 1}} - \sum_{k = 1}^n \frac{1}{2^{k - 1}}$ and I think that should drop out from using the geometric series formula. First one would be $\frac{a}{1 - r} = 2$ and the second one would be $\frac{a(1 - r^n)}{1 - r} = 2 - \frac{1}{2^{N - 1}}$.

[vital dew]

PhenomPlasma

[vivid tulip]

I just proved that if x and y are real numbers, then x relates to y if x-y is rational is reflexive, symmetric, and transitive. So x and y belong to an equivalence class if their difference is rational, and belong to an equivalence class if their difference is irrational. So basically I can partition the real numbers using this relation. But I'm not sure what it looks like.

[vast hearth]

It basically partitions the reals into disjoint subsets; one of them is the subset of reals that are also rational; the others are the subsets of the reals containing an irrational number and those numbers whose differences with it are rational.

What might be confusing you is that there are several *representatives” of each equivalence class

[vivid tulip]

Oh, I think I see

Is this a way to prove that rational minus irrational is irrational?

[vast hearth]

You’d still have to prove their difference is not rational; then you’d know they’re not R-related, which would mean they’re in separate equivalence classes

Are you given that the two terms you’re subtracting are one rational snd one irrational?

In that case you can work backwards and say their difference can’t be rational since they’re each in distinct equivalence classes

But if you’re just given two arbitrary real numbers, there’s no way of knowing if their difference is rational or not

[cerulean wind]

there are uncountably many partitions (or equivalence classes). the collection of all the equivalence classes is the set of all r + Q, where r + Q = {r + q : q in Q}. This set is typically called R/Q, or, R mod Q.

[cerulean wind]

you dont really need this set up to do that. if r is irrational and p is rational, if p - r = q is rational, we have r = p - q being rational, which is false

[sick dirge]

Hey, can I just quickly check if my work is correct? Define $I^+ = {n > 0 : | : n \in I}$. By the well-ordering principle, $I^+$ has a least element, which we claim fulfills the criteria of $n_0$. (Note that $I^+$ is nonempty since $\exists m \neq 0 \in I$ and either $m$ or $-m$ is in $I^+$ by (a)). To see this, note that evidently ${kn_0 : | : k \in \mathbb{Z}} \subseteq I$ by (c). Now consider an arbitrary $n = n_0q + r \in I$. Then by (c), $-n_0q \in I$ and by (b), so does $r = n + (-n_0q)$. If $r > 0, r < n \in I^+$, a contradiction. Hence $r = 0$ and the reverse inclusion is proved. Thus we are done.

[vital dew]

PhenomPlasma

[little prism]

Yes

[sick dirge]

Aye good stuff. Thanks.

[keen geode]

Does this make sense?

Or Can i not use unions in this manner?

[little prism]

the union is not the set containing N, it's just N itself

[keen geode]

what's the difference?

[little prism]

one is a set containing a set, the other is a set containing numbers

[keen geode]

Ok I see, because N is a set in it's own right and can be written as {1,2,3,4,5,6...}

[little prism]

yes

[keen geode]

great, thanks a lot

And the notation for the 3rd line is correct?

[little prism]

no

it's also jsut the empty set itself

[keen geode]

alright, cheers!

[obtuse lance]

it might help to see them written differently as well

{N} = {{1,2,3,4,5,6...}}
{empty set} = {{}}

you're like "double bagging" everything

[keen geode]

yeah i get it

I think there's also different notations in my country

Because whenever we said an equation has no solutions S, we'd write S={∅}

which I guess is incorrect?

I've also noticed that here we use () to say that the boundaries of an interval are not included

In France we use ][

[little prism]

that is fine

[little prism]

this isn't

[keen geode]

thought not

I'll have to have a word with my teachers then 😂

[weary tiger]

I have to show if relation R is an equivalence Relation. Is my attempt correct?

[little prism]

for reflexive it isn't. you start with aRb and conclude that aRa and bRb. but what if there is no b such that aRb? (here there is but in general there might not) show directly that aRa by showing that a +2a is even for all a in 2Z^+

rest is correct

[weary tiger]

👍

[weary remnant]

how do I show for all sets A,B (A∪B)\B=A I showed (A∪B)\A ⊆ A but I don't know how to show the other direction

[weary tiger]

But, since a+2b + a+2b is even

(b + 2a) + (3b) is also even
So, b+2a and 3b must be even

If 3b is even, then b is also even by definition, because b belongs to 2Z^+
In other words, 3b can only be even if b is even, which is true

And 3b = b + 2b
Hence bRb.
Same can be done for aRa, starting with bRa

This can work right?

[little prism]

But you don't know if aRb exists. That's the point

You can conclude everything from a false premise. That isn't helpful

[weary tiger]

Ohh

Ohh I see why now

Thanks 👍

[weary tiger]

any hints for how to count $\varphi(p^k)$ where p is prime

[vital dew]

紫の

[weary tiger]

totient

i kinda had a conjecture

(p-1)pk

not the case

tried with one

pk -1 tho 🤔

(k-1)(p-1) 🤔

[keen geode]

Rigorous enough?

[final cliff]

Here's one way to see it. Notice phi(p)=p-1 because in {1,...,p} there are p-1 numbers relatively prime to p (so no multiples of p). For phi(p^2) we have {1,...,p} containing p-1 numbers relatively prime to p^2 and one number (p itself) not relatively prime to p, we have {p+1,p+2,...,2p} containing p-1 number relatively prime to p and one number (2p) not relatively prime to p. So, you should see if we continue this pattern in {1,...,p^2} that only the multiples of p, {p,2p,...,(p-1)p,p^2} are not relatively prime to p.

[weary tiger]

o

so (p-1)^k

[final cliff]

No

[weary tiger]

o

wait

mb

[final cliff]

Sorry I hadn't quite finished typing the hint lol

[weary tiger]

is it k(p-1)

cuz

[final cliff]

In {1,...,p^2} how many sets can you chop this set up into sets of the form {kp+1,kp+2,...,kp+p}?

This is the last part of the hint lol

This trick generalizes to p^k

Notice how that kp set has p-1 elts relatively prime to p^2 and one element that is not.

Maybe there is an easier way, I've just done it this way before. Hopefully I'm not butchering it, I haven't thought about this in a while lol.

[weary tiger]

(k-1)k/2 ..

[final cliff]

No

[weary tiger]

naah this looks too ugly

[final cliff]

It's really not lol

[weary tiger]

gimme a sec

[final cliff]

Uhh

[final cliff]

Ignore the fact that I used k here and also

[final cliff]

here

I don't mean to make it seem like I'm talking about the same k mb

[weary tiger]

p or p-1

[final cliff]

Yeah, so really we can kind of look at it as hoe many choices of k are there that make {kp+1,...,kp+p} a subset of {1,...,p^2} I guess? Also notice kp+p=(k+1)p.

[weary tiger]

man what

wait im tripping

[final cliff]

The smallest choice of k is def k=0

So what is the largest?

[weary tiger]

card of this {kp+1,kp+2,...,kp+p} is p right

[final cliff]

Yeah

[weary tiger]

p

[final cliff]

Mmm no

[weary tiger]

p-1

(p-1+1)p

so we end in p²

?

[final cliff]

No

[weary tiger]

hmm

[final cliff]

Don't just guess the largest choice of k lol

[final cliff]

We're trying to count how many sets of this form we can chop up {1,...,p^2} into.

So, the largest choice of k has to end in (k+1)p=p^2 yeah?

So, then solve for k and you get k+1=p hence k=p-1 like you said.

[weary tiger]

yes

[final cliff]

So, k can be any number from 0 to p-1, there are p such choices of k then.

[final cliff]

So, we have p sets of this form.

Each one has p-1 elements relatively prime to p^2

Notice the union of them all is just {1,...,p^2} and each is disjoint too.

[weary tiger]

OW SHIT

BRUH

[final cliff]

You see it now? Lol

[weary tiger]

im so dumb, ive been counting all those between p+1 and p² including p+1

but it turns out

theres 2p 3p... and so on till p²

aaand 1P 2P 3P .. P² that p in total

so p-1 for the set {1;...;p} and (p-1)p for {p+1;..;p²}

ig

i rushed this wait

[final cliff]

Yeah you mixed up the {p+1,...,p^2} part

[weary tiger]

but it does feel close

is it?

[final cliff]

Notice that this set still has only p-1 numbers not relatively prime to p and a single number that is a multiple of p.

[weary tiger]

lemme go through what u sent again

theres p-1 elements between each here

[final cliff]

I'm doing this: {1,...,p^2}={0p+1,...,0p+p}U{1p+1,...,1p+p}U{2p+1,...,2p+p}U...U{(p-1)p+1,...,(p-1)p+p} basically then I'm noticing that each set in this union is disjoint and contains p-1 elements relatively prime to p^2 the rest (the multiples of p) are not relatively prime to p^2.

Then you just add up all those relatively prime elements in each set to get phi(p^2).

[weary tiger]

so

[weary tiger]

in this set only

there are (p-1)(p-1)

plus those <p

which gives

(p-1)²+(p-1)

which is p(p-1)

[final cliff]

Yeah

[weary tiger]

damn

[final cliff]

That's a nice way to put it.

[weary tiger]

thanks a lot

really

[final cliff]

And this same trick generalizes to p^k.

[weary tiger]

yeah i can see a bit into the fog now

[final cliff]

Though you'll have to count it out until you see the full pattern ofc lol

[weary tiger]

i like taking wild guesses lol

$\frac{(p-1)^k-1}{p}$

bruh

lol

[final cliff]

It's not hard to see what the formula is for p^k as you were putting it earlier, you'll consider {p,2p,...,(p-1)p^(k-1),p^k}.

[weary tiger]

yes yes

gonna bring out paper n pen and stop being a lazy number enjoyer

[vital dew]

紫の

[weary tiger]

@final cliff sorry for the ping

[final cliff]

Np

It's gonna be an integer for sure.

[weary tiger]

my brain

im trying to count

[final cliff]

Try and count it using the same trick you used last time.

You were kinda counting the commas to notice that between each mp and (m+1)p there are p-1 numbers relatively prime to p^k.

Then you remarked that all you had left was to account for the remaining coprimes less than p.

This seemed like a good way to look at it to me.

[weary tiger]

mb but i cant not think that there are (p-1) between tp² and (t+1)p²

no

what i did was between p and p²

so i cant just down it on p² and 2p²

brain gone

[final cliff]

For p^k you'll have to count between 1 and p, between p and p^2, between p^3 and p^4 up to counting between p^(k-1) and p^k.

I guess that's kind of a bad way to put it.

We have a lot more multiples of p now is all I'm trying to say. "Counting the commas" like you did before requires you to pay more attention to the multiples of p and powers of p in the set {p,2p,...,(p-1)p^(k-1),p^k} from before.

[weary tiger]

oooooooooooooooo

[final cliff]

If it helps we can write that set as {p,2p,3p,...,p^2,2p^2,3p^2,...,p^(k-1),2p^(k-1),3p^(k-1),...,(p-1)p^(k-1),p^k}?

[weary tiger]

this is my last guess probably

$p^k-1-(p-1)(k-1)$

[vital dew]

紫の

[weary tiger]

no

[final cliff]

I don't think that is correct.

[weary tiger]

god wtf is my counting

i lowkey went like

there are p²-1 elements between p² and 2p²

excluding those two

i am braindead

[final cliff]

Thinking about how many times we can chop this set up into subsets of the form {p^m,2p^m,...,(p-1)p^m} might help?

[weary tiger]

following this. there are (p²-1)(p-1) between p² and p^3 and again (p^3-1)(p-1) between p^3 and p^4

and so on

[weary tiger]

added them all up together, a few cancellations and got this

[weary tiger]

this is what i was trying to do

well not directly

i assumed theres k-1 of em

[weary tiger]

following this again (p-1)(1+p+p²+...p^(k-1) - 1-1...-1 )
-1 (k-1) times

[final cliff]

This might be easier the multiples of p^k in {1,...,p^k} are of the form mp^n so if we count all choices of m and n we can find the cardinality of the set of multiples.

Then subtract 1 to count all the commas and do your same trick as last time.

Well, maybe I'm confusing myself lol

[weary tiger]

card of this {1,...,p^k} is p^k right?

okay so

[final cliff]

Talking about how to count the set of multiples you have.

[weary tiger]

counting the numbers n st gcd(n,p)=1 from $p^{t-1}$ up to $p^t-1$ goes by first counting all whats in there, which is $p^t-p^{t-1}$ and subtracting the number of multiples of p in that interval which is p-1 , so total is (in this case) $p^t-p^{t-1}-(p-1)$ and since we have $(k-1)$ intervals like that , then the total number is $\sum_{i=1}^{i=k-1}p^i-p^{i-1}-(p-1)$

[vital dew]

紫の

[weary tiger]

@final cliff what do you think

[final cliff]

That seems complicated. If you take the set of multiples here, notice between any two consecutive elements of this set there are p-1 relative primes and there are also p-1 relative primes less than p, so the value we want at the end is (p-1)(cardinality of set of multiples) I think.

The multiples are just {p,2p,...,(p-1)p^(k-1),p^k}={mp: m in ???}, so for ???, what values can m take on?

[weary tiger]

{1;...;p}

[final cliff]

No

If that were true the set would just be p to p^2.

The biggest value of mp we want is p^k itself and the smallest is just p

[weary tiger]

{1;...;p^(k-1)}

br

[final cliff]

Yep

So there are p^(k-1) choices of m

[weary tiger]

simply p^k -p^{k-1}?

[final cliff]

Hence the set of multiples of p (less than or equal to p^k) has p^(k-1) elements.

[weary tiger]

wtf

[weary tiger]

which we will remove from the big set(main) that has p^k elements

[final cliff]

Yeah one way to do it.

But your comma counting trick made it easier.

With no weird factoring stuff at the end.

[final cliff]

I was trying to rewrite it here.

[weary tiger]

what comma counting trick

what have i done

where am I

[final cliff]

You were saying between p and 2p there are p-1 relative primes and so on

[weary tiger]

who are you

[weary tiger]

oh yes

[final cliff]

Between p and 2p there is a comma lol

[weary tiger]

ah

[final cliff]

You were effectively counting the commas in our set.

Then adding in the relative primes less than p at the end.

We just counted p^(k-1)-1 commas

[weary tiger]

ooooooh

[final cliff]

Same basic idea I just finesse away the -1 here by counting the relative primes less than p early to get the formula we're going for.

Basically I counted the commas and added 1 for the { bracket lol.

[weary tiger]

please carry on what you were writing

typing*

[final cliff]

Mmm I was just gonna mention this stuff with commas and brackets is kinda wishy washy. We're really just noticing for any mp in {p,2p,...,p^k} there are p-1 relative primes to p^k between mp and (m+1)p then counting the missing relative primes between 1 and p.

[weary tiger]

m in {1;..;p^(k-1)} always yeah?

[final cliff]

Yes of course

[weary tiger]

yes you're right

my vision is quite narrow and im a bit stubborn, so like i cant back off and see things from above

and it seems to me that i confused u a bit as well

[final cliff]

Yeah I recall this being a kind of confusing thing to prove off the top of my head when I first did it lol.

There might be an easier way but so long as you recall the issue being multiples of p in {1,...,p^k} you can fiddle around until you find the proof of it.

[weary tiger]

wait in what u can I prove this?

induction seems quite easy

but now that we went through it, it seems to me that there is actually nothing to prove

[final cliff]

I guess it depends on what you know. But I'd be fine accepting a proof like this in most cases.

[weary tiger]

if there's anything to prove, i think it'd be to prove that the way of counting is correct, and directly from that we can say our result ( what we counted) is indeed true

[final cliff]

Oh wait your bounds on m here are messed up I think.

you accidentally picked m too big is all

I guess it's kinda ambiguous on my end.

[weary tiger]

on our end

[final cliff]

Anyway. For any mp in {p,2p,...,p^k} where m is in {1,...,p^(k-1)-1} notice there are p-1 numbers between mp and (m+1)p relatively prime to p^k and between 1 and p there are p-1 numbers relatively prime to p. Hence by product rule of counting there are (p-1)[p^(k-1)-1+1]=(p-1)p^(k-1) numbers in {1,2,...,p^k} that are relatively prime to p^k.

[final cliff]

Yes lmao

[weary tiger]

this is much

much

much

much

$\sum_{n=1}^{\infty}much_n$ better

[vital dew]

紫の

[final cliff]

Yeah, induction seems like it would be overkill here.

[weary tiger]

st much_1<much _2<...

[weary tiger]

wdym

[final cliff]

Well, we could try and make some ugly induction argument or just let basic counting principles that are commonly accepted do the majority of the work.

I guess there could be an induction argument hiding in your proof of the product rule for counting somewhere but that's way out in the weeds lol.

[weary tiger]

just let basic counting principles that are commonly accepted do the majority of the work.

[weary tiger]

yes please 🤝

[weary tiger]

😭

[final cliff]

Usually you get to take those rules as a given.

https://en.m.wikipedia.org/wiki/Rule_of_product

[weary tiger]

GASP

this is my biggest weakness

imma go through it in the summer

it's keeping me from doing most maths

[final cliff]

Combinatorics is hard lol

[weary tiger]

one bad thing about this is that you can count something in two different ways, and it feels like they're both logical

[final cliff]

This can be useful though

Because if you count something in two ways correctly you wind up with two formulas for the same quantity.

Rather than just one.

[weary tiger]

mb i meant like

when u dont know whats right and whats not

@final cliff ngl, I don't know how to thank you

such patience and kindness

you are a wonderful person

thanks a lot

[final cliff]

No problem

[rough radish]

.

[keen geode]

.

[formal flicker]

Guys does anybody know why there is this a11a12...instead of a1a2...?

Someone please help 😭

[final cliff]

Because f(1), f(2), f(3), ... are all different numbers.

They're using a_ij to be the jth digit of the ith number in the list f(1), f(2), f(3), ...

[weary tiger]

can someone give a hint oto show that eulrer's totient is multiplicative

[pale epoch]

hm, the proof is either very easy (if you have enough theory) or kind of tricky (if you dont)

in the former case the hint is chinese remainder theorem in the latter case i am not sure a hint will do

[weary tiger]

o

i'll try that

i was trying to find some kinda sequence to how things go by studying various examples but im too blind lol

[pale epoch]

there is a trick way i know that goes like this:

you want to see what phi(mn) is

so you write the numbers 1, ..., mn like this:

now either every element in the r-th column or none are coprime to m

and phi(n) elements are coprime to n

[weary tiger]

o

[pale epoch]

both of these statements need some kind of proof

[weary tiger]

🤝

[pale epoch]

the former is not too hard, the latter a bit

[weary tiger]

gotcha

[pale epoch]

and then you need some additional argument, but it will work out

if you know what rings are and know the chinese remainder theorem and how units in quotient rings of Z look, its just a simple corollary of CRT

[weary tiger]

yup i did a study of (Z/nZ,+,.)

guess my vision is just too narrow

[pale epoch]

well, then look at CRT and count how many elements $(\bZ/n\bZ)^\times$ has

[vital dew]

Lochverstärker

[formal flicker]

Is my proof correct?

[weary tiger]

oooooooo i understand this now!

thanks a lot!

id say i mostly used

gcd(a,b)=1 =>gcd(a,a+b)=1

i mean to filter things out ofc, ur trick is still the main idea to my answer

[weary tiger]

i have an answer!

imma write it out n send it!

[weary tiger]

well things didnt go as planned

and I think im satisfied with the answer

seen a few vids to get a bit deep in the topic of the tot function

gained a good understanding!

thanks nyways

[sick dirge]

Hey. I'm having a bit of trouble with (c). I don't see why the proof method of considering $n = 8p_1...p_n - 1$ would fail. Am I missing something blatantly obvious here?

[vital dew]

PhenomPlasma

[sick dirge]

1. A number is perfect if the sum of its factors is twice itself. For any prime $p$, you know that $1, p, p^2, p^3, ..., p^n$ are the only factors of $p^n$. So all that's left is to show that the sum of these factors is not $2p^n$.

[vital dew]

PhenomPlasma

[sick dirge]

As for 2, I'm not entirely sure how to approach it. But we know that the form of the factors of $a = 27q$. Since $q$ is not divisible by $3$, $q$ and $27$ do not share any common factors. Hence, the factors of $a$ must be of the form $k, 3k, 9k$ or $27k$ where $k$ is a divisor of $q$.

[vital dew]

PhenomPlasma

[obtuse lance]

the problem is with mod 4 the only options for primes is 1 and 3, similarly with mod 6 the only options for primes are 1 and 5. When looking mod 8, you have 1,3,5,7 now, so you're not trapped into only one option, they could be finitely many since you can make 7=3*5 mod 8

[cursive wind]

#help-7｜zen1thxyz

[undone ibex]

im confused about this question: For every prime p, p + 2 is a prime. I know the answer is false and that 7 is the counter example. But why? 7+2 = 9 is a prime number.

[little prism]

9 is not prime

9=3*3

[undone ibex]

thanks, i had a brain fog

[little prism]

happens

[untold lion]

Could anyone help explain vii? I get the rest but this one is kind of confusing me

For the image (iii) i got {0<= x < 1}

but for the preimage = y where y can be +-, im confused cause to me it just seems like the answer would be {-1 < x < 1}

[quaint notch]

Hey all, I need to decide which ordinals are greater (2 different sections)

a. w^2 + w^3 or w^3 + w^2
b. (w+2)(w+1) or (w+1)(w+2)

How do you start such question? got no clue sadly

[sick dirge]

Terribly sorry. I get that we can have 1, 3, 5 and 7, but I don't understand your last line. What do you mean that "they could be finitely many since you can make 7 = 3 × 5 mod 8"?

[sick dirge]

Should be right.

[sick dirge]

I think (vii) is just being tricky. The -1 < x < 0 part has no effect on your answer since |x| is never negative.

[sick dirge]

And yeah that seems right.

[untold lion]

Yeah, that’s why I got confused cause we have -1 < x < 1 but in the true image we never get -R, but since it’s the pre image, y = |x|, the pre image can be negative since x would end up being positive no matter what so that’s why I think the answer is -1 < x < 1 but my prof isn’t replying to my email 😭

[undone ibex]

How do i prove that For all integers n, n3 −n is divisible by 3.

[hard oriole]

Try proving by induction.

[floral field]

So, I'm trying to prove that the maximum number of attacking non-attacking kings on an nxn board is floor{n^{2}/4}. Any hints on how I might be able to prove this? I've tried to justify it by a direct counting argument, but I can't quite get it.

Would setting up a bijection work?

[stray reef]

maximum number of attacking kings?

[floral field]

non attacking

[stray reef]

ah.

[floral field]

Oops

[stray reef]

i believe this only works for even n

on a 5 by 5 board you can place 9, more than the 6 predicted by your formula

[floral field]

Shoot

[final cliff]

There are only 3 choices of remainder under division by 3 for n. So, really there's only 3 cases you need to consider here.

If you want to avoid induction you can maybe try that instead.

[floral field]

Any hints as to how I might re-approach the non-attacking kings problem?

[stray reef]

in any 2x2 subgrid there is at most one king

you can show that this implies the number of kings is at most k^2 for n = 2k and at most (k+1)^2 for n = 2k+1

[floral field]

I concur, yes

I will try this, thank you

[quaint notch]

Any help guys?

[final cliff]

For (a) you can factor w^2 on the left and notice 1+w=w I think.

[stray reef]

is ordinal multiplication actually left-distributive tho

[final cliff]

I coukd be mixing it up lol it distributes one way but not the other

Lemme double chk

[stray reef]

(ω+2)*(ω+1) = ω^2 + 2 i believe

ok yeah i just checked on wikipedia it's distributive on the left only

[final cliff]

Yah yah

[quaint notch]

Yeah I'm just confused about it

[final cliff]

Yeah ann said it right

In the ordinals you have a(b+c)=ab+ac

But not always (b+c)a=ba+ca

There's this one theorem you can prove that might help for (b)

[quaint notch]

so w^2(w+1) or w^2(1+w), meaning w = 1+w right?

[final cliff]

It took me a min to find it

[final cliff]

I'm not sure what you are asking?

[quaint notch]

Like, am I right?

😛

Is this what you meant? for a

[final cliff]

So, there would be more to do from here I suppose.

The thm I was gonna mention for (b) is that for n a finite ordinal, a a limit ordinal and b an ordinal (a+n)b=ab+n when b is a successor ordinal and (a+n)b=ab when b is 0 or a limit ordinal.

This is an exercise from a book called "problems and theorems in classical set theory" by Komjath and Totik.

Idk if it will help. If you wanna use it you should prove it first though.

[quaint notch]

Yeah of course, I'll try 🙂

[final cliff]

Or prove the parts that you need by letting a=w or whatever you find useful.

[quaint notch]

I'll give it a shot thank you

🙂

[obtuse lance]

it'd be easier if you wrote out a proof and I can point out specifically where it goes wrong

main thing is you can really only say there are infinitely many primes that are of the form 3, 5, or 7 but it could be that there's only finitely many that are 7 mod 8 with this kind of argument.

[sick dirge]

Oh wait, in trying to explicitly explain this proof I seem to have found my own mistake.

[obtuse lance]

nice lol

[sick dirge]

Assume finitely many primes $p_1, ..., p_n$. Let $n = 8p_1...p_n - 1$. Since $8p_1...p_n - 1 > p_n$, $n$ cannot be prime. So there must be a prime dividing $n$. However, in the $4k + 3$ and $6k + 5$ cases we can show that there must be a prime of that form. But in this case the prime need not have the form $8k + 7$, as you said, since we could have primes of the form $8k + 3$ and $8k + 5$ that go into $n$ instead.

[vital dew]

PhenomPlasma

[obtuse lance]

cool 👍

[sick dirge]

Cheers mate!

[vagrant glen]

In a typical non-cooperative, non-zero-sum game, is the aim for each player to maximise their points or to maximise their point advantage over the other player?

(if there's a better channel for game theory, let me know; i just joined this server)

[floral field]

So, it seems like this can be cerged to [ceiling{n/2}]^2. If I went with this, would this be harder to argue via some direct counting argument?

[stray reef]

well if you refuse to split into cases based on the parity of n like i said here then i think itll be a little tricky to find such an argument

[floral field]

No, I agree that it's easier to prove the formula with cases. I was just curious if the proof for the one using the ceiling had a proof of similar flavor

Out of curiosity, would proving [ceiling{n/2}]^2 involve some kind of analysis?

[coral parcel]

I'd assume each player wants to maximize their own score. If they just cared about the difference, we could reformulate the game as zero-sum by tracking that difference instead, and get access to nicer theory.

[quaint notch]

Hey all, I need to prove the follow statement.
Was thinking about the following way, would love to hear your feedback.

Say $\alpha = \beta$, so we could just choose $\gamma = 0$

Otherwise,
$\alpha < \beta$, meaning $\alpha \in \beta$, so we could just take $\beta \ \alpha$ and finish

Am I missing something?

[vital dew]

meitar5674

[stray reef]

did you mean $\beta \setminus \alpha$?

[vital dew]

Ann

[quaint notch]

oh yeah, my bad

[coral parcel]

That looks like a good strategy. But there would be some details to argue for in more depth. First, that beta\alpha is well-ordered. Second, if you don't already have it established, that ordinal addition actually corresponds to putting the ordinals end-to-end.

(E.g., it is common to define ordinal addition by transfinite recursion, and then it takes some work to show that it corresponds to placing the two orders after each other).

You ought to get that gamma=0 case automatically when alpha=beta since then alpha\beta = Ø.

[quaint notch]

Ain't all sets are well ordered?

so there exist such ordinal?

Also sorry but the transition from my language math to English math is sometimes difficult for me

thanks for helping 🙂

[coral parcel]

All sets are well-orderable, but when you want to identify beta\alpha with an ordinal gamma, you need to consider the particular ordering it inherits from being a subset of beta. (It is not hard to show that this is indeed a well-ordering of beta\alpha; I'm just saying you ought to note that explicitly).

[quaint notch]

Oh I understand, thanks 🙂

[vagrant glen]

thank you, yes that does make the most sense

[true venture]

Hello I want to express the sum of the integer sequences $1,121,1232121,1234321232121...$
Is this sum written correctly?

$a(n)= [\sum_{a_0=0}^{n-a_i>=2}(n-a_i)^2]-a_n$

[vital dew]

jo_fish

[true venture]

Main question being why does

$a(n)= [\sum_{a_0=1}^{n-a_i>=2}(n-a_i)^2]-a_n$ and $a(n)=(2n^3+9n^2+7n+6)/6$ work for this sequence???
This is also OEIS A047732

[vital dew]

jo_fish

[stray reef]

your notation definitely makes no sense

and oeis A047732 seems to have nothing to do with the sequence (1, 121, 1232121, 1234321232121, ...) that you posted about

it is not clear how it continues past the ninth term and it is not clear whether you want a formula for the sequence itself or for the sum of its first n terms...

[true venture]

Thanks, I also made an error in the sequence. But what I am trying to say is this sequence of integer strings 1, 121, 1212321, 1212321234321. When you sum the digits of each string, the sequence of sums is A047732.
The sum I am trying to write represents this process.

[undone ibex]

How do you algebraically manipulate this? Can someone explain the steps?

[true venture]

The formula I want is for the sum of the digits of each string

[vital dew]

jo_fish

[true venture]

What I am trying to write in the sum notation is for

$a(3) = 3^2+2^2+1^2 -(n-1)$

$a(4) = 4^2+3^2+2^2+1^2 -(n-1)$

[vital dew]

jo_fish

[tame trench]

Macro Economics:

Is this thread the right place?

In case not, I'll delete it but if you can explain what is going on here and the "how" and "why".. I would really appreciate the help.

[true venture]

Um I'm not totally sure, what "price elasticity" is there a separate equation for that?

Ok revised sum, does this one make sense

$a(n)= [\sum_{i=0}^{n-1}(n-i)^2]-(n-1)$

[tame trench]

Ep is the elasticity formula for percentage i believe..

Triangle means "difference of"
Q= Quantity
D= Demand
S= Supply
P= Price

Ignore the numbers... Lets see them as empty unknown variables

[vital dew]

jo_fish

[tame trench]

No it doesn't to me.

[true venture]

Does this notation make sense?

$a(n)= [\sum_{i=0}^{n-1}(n-i)^2]-(n-1)$

[vital dew]

jo_fish

[tame trench]

Its the same as above.
No I don't recognise it at all.

I mean.. it reminds me of statistics but my problem isn't statistics.

[true venture]

This was for something else, not elasticity

[tame trench]

oh.

[true venture]

Is 4.71 elastic the given answer?

[tame trench]

No. It what is "supposedly" the answer but mustn't be.

I want to know how my collegue came to this answer, how to do it myself but I am heavily confused.

[true venture]

I'm not sure either, do you have notes on the "midpoint method"?

[tame trench]

Yes and no

Np though.

thanks anyway

Like.. I know the formula for mid point method but I dont know hoe to implement any of it.

[true venture]

What is the formula?

[tame trench]

This

Difference of Qdemand/ difference of price

but anyhow.. Ill youtube it.

Thanks though

[true venture]

Googling the equation for elasticity demand, gives a different equation that gives 4.71 as the answer

[true venture]

Using this formula, I get 4.71.

[tame trench]

huh..

interesting

What did you do exactly (insert into that formula) ?

[true venture]

Since the problem asks for a price increase of 1 from the market eq. You know which values to use for Q and P. Does this make sense?

[tame trench]

well.. if I equate 20-3p=-5+2p of the market quilibrium, i get P= 6

so.. how do i find out Qd and Qs?

[true venture]

You only need to look at Qd and P. You have the Qd and P values at the equilibrium and then Qd and P values after P is increased by 1 as the problem says

[tame trench]

oh no.. P = 5
I did it wrong

my bad

Okay

P= 5

But still. How do I find out Qd and Qs?

[true venture]

Think of it as you have P = 5 and P = 6. Then find Qd at both those price points. Then use the equation

[tame trench]

okay.. This may take a bit. I'm still here and giving you my full attention though

okay. Now I caught up.
Qd with P=6 is Qd= 2

[true venture]

Those two values of P are your P_2 and P_1 . Then solve for Qd at each P. Those are your Q_2 and Q_1 values. Then plug everything into the formula

[tame trench]

Aha... So as I wrote above.. and my difference given is that of case1 P= 5 and Case2 P= 6 ?

[true venture]

Yes

[tame trench]

fml

hah!

Wait, lets see if I get the same result

hmm... Difference of price would be 1 right? (6-5)

[true venture]

Yes

[tame trench]

difference of Qd is 5-2 = 3

but... elasticity is 4,71 and what I get is a clear 3..

Im doing something wrong

I did 3/1 (Qd1 difference to Qd2/ P1 difference to P2)

[true venture]

You have to plug Q1=5 Q2=2 P1=5 and P2=6 into the equation

[tame trench]

... I still get 3.. I am doing something stupid.
Would you please type exactly what you insert?

[true venture]

Q1=5 Q2=2 P1=5 P2=6

[tame trench]

Finally!!

Thanks so much!

E= - 4,709 ~ - 4,71

wait...

I get - 4,71

.. fml xD

---

Okay. I just found out.
For elasticity, the minus is to be ignored.

So -4.71 = 4.71

Therefore it is above 1 = Elastic
It is not equals 1 or 0, not over 1 but below 0. Therefore an inferior good

[true venture]

Ok maybe this makes sense now,
When checking values of a(n) I get the same answer.

$a(n)= [\sum_{i=0}^{n}((n+1)-i)^2]-n$

And

$a(n)=(2n^3+9n^2+7n+6)/6$

Is there a way to derive on from the other?

[vital dew]

jo_fish

[vale cairn]

Well you can expand out the first sum in terms of sums of 1,i,i^2 and use the standard formulae for those to get the second expression.

Deriving the first from the second seems impossible without already knowing what it should be and if all you're interested in is truth of equivalence of the two expressions, rather than worrying about how one might stumble across the first, say, you can just use induction on n.

[true venture]

What are the standard formulae for those? Would i use 1,i,i^2 for n?I came up with the sum form and was surprised someone else expressed it as the second form.

[sick dirge]

Hey can I just do a quick check about this? To show well-definedness, what I should check is that $[a_1] = [a_2] \implies F([a_1]) = F([a_2])$, right? And in this case $a_1 \sim a_2 \implies f(a_1) \sim f(a_2)$, so $[f(a_1)] = [f(a_2)]$ and $F([a_1]) = F([a_2])$ right?

[vital dew]

PhenomPlasma

[weary tiger]

Yea

You already have done everything

[sick dirge]

Ye thanks. Just wanted to check if that was what I was meant to do.

[cerulean cosmos]

Anyone knows how to do this?

[stray reef]

think about parity

[cerulean cosmos]

Apparently it uses invariant principle I dont know how to do with it

[stray reef]

try playing around with this setup and seeing what numbers of white squares you can achieve.

then try to make a conclusion about said numbers.

[cerulean cosmos]

0 2 4

So even parity?

And does that come to a conclusion where the preserved invariant is even number of white squares?

[stray reef]

well, why don't you attempt to prove that the number of white squares is always even?

[cerulean cosmos]

Hmm alright

I could but Im not sure how do I start with?

Not really sure how do I go about it

[stray reef]

by what amounts can the number of white squares change after one move?

[cerulean cosmos]

Depends. If a side with black and white color is chosen the number of white squares will be the same. But if a side of both black squares is chosen that number of white squares is +2. If a side with 2 white squares is chosen then -2 number of white squares.

[stray reef]

yes, so the only amounts by which the number of white squares can change are -2, 0 and +2.

and you have exhausted all possibilities

[burnt lynx]

~(p->q v r)
is their something equivalent to that or can I simply write the statement as it is
" if it is not the case that n is prime, then n is odd or n is 2 "

[stray reef]

where did n come from and what do p, q and r have to do with it?

[sick dirge]

Not an exam. This is a practice test from 2015/2016. Was just looking through it and was wondering if my ideas here are correct since there's no answer scheme. For (a), I noted that for all $n \in \mathbb{N}$, we can write $n = (2k - 1)2^{(2j - 1)2^{i - 1} - 1}$ and thus we can define a bijection $f : \mathbb{N} \to \mathbb{N}^3$ by $f(n) = (i, j, k)$. For (b), I note that such a mapping $\mathbb{N} \to $ Maps($\mathbb{N}, {0, 1})$ is not surjective. To this end, suppose such a mapping exists and let $n \mapsto M_n$, with $M_n$ being a map $\mathbb{N} \to {0, 1}$. Then, $M_n(n) = 0$ or $1$. Now, define a new mapping $M$ so that $M(k) = 1$ if $M_k(k) = 0$ and $M(k) = 0$ otherwise. Then, $M$ differs from $M_k$ in its choice of mapping $k$. This disproves surjectivity.

[vital dew]

PhenomPlasma

[little prism]

looks good. I don't wanna go through all the details of a) but seems like a correct idea. and b) also sounds good

[sick dirge]

Aye nice.

That took too long. Don't think I'll have that much time during a real exam. 💀

[little prism]

do you know the theorem that if you have injective maps from A to B and B to A then there exists a bijective map between them?

[sick dirge]

Hm, nope I didn't. Interesting.

[little prism]

with that you can solve a) by showing that the maps n->(n,n,n) and (n,m,k)->2^n3^m5^k are both injective

[sick dirge]

Ah that makes far more sense. 😂

[little prism]

but I also really like your idea. just needs a bit more checking for all the details with the +-1 etc

[sick dirge]

Yeah I need to check the exact details to make sure it actually maps all of N to something.

Just wanted to see if that was the right idea.

I hope there's a simpler idea but since I don't have the answer scheme I guess I'll never know.

[little prism]

you could first write your map as N->(odd)x(odd)xN or something

and then bijection from (odd)x(odd)xN to NxNxN is somewhat obvious

[sick dirge]

My idea kinda came from me experimenting first with N -> N² and that's fairly easy, just n = 2^i(2j - 1) and f(n) = (i, j). Then I tried to extend using 2^i3^j but that didn't work since the leftover term doesn't have a nice form. So I just went with the tower of exponents. 💀

[sick dirge]

Ah that does make sense. I'm sure there's probably a relatively more straightforward method by combining multiple maps.

[little prism]

well you can always go from NxNxN=NxN^2 to NxN=N^2 and then to N

[sick dirge]

I just thought of something but using the same idea of 2^i(2j - 1) we could map N -> N². And then take the second element in N² and map it again using 2^i(2j - 1) and that should give N² -> N³.

[little prism]

in each step use your map N->N^2

[sick dirge]

Yeah. I think I over-thought. 😂 Thanks for the ideas!

[little prism]

essentially this is what you did with your tower

[sick dirge]

Yeah but there's a chance I messed up with some cases.

Like previously the mapping I found didn't map 1 to anything. Oops. Had to change it a bit.

[little prism]

there is an obvious map between N and N\{1}

[sick dirge]

True.

[little prism]

handwave all the details away by doing stuff like this

[cerulean cosmos]

Can anyone tell me what is the closed form for

I thought it was (x^(n+1)-1)/x-1

Sorry I do not know how to use latex

[sick dirge]

For $|x| < 1$, it's $\frac{1}{1 - x}$.

[vital dew]

PhenomPlasma

[sick dirge]

What you wrote is the sum up to some n, not up to infinity. If you let n go to infinity, the x^(n + 1) goes to 0 and you get the same thing as above.

[cerulean cosmos]

Okay if it were to some n lets just say

Would what I wrote be correct?

[sick dirge]

Yep.

[cerulean cosmos]

Alright

Thanks

Wait hold on

[cerulean cosmos]

Whats the difference between what I wrote here and this
$\frac{1-xⁿ}{1-x}$

[vital dew]

Tony Chiba

[sick dirge]

Uh it's the same.

Just take the negative of both numerator and denominator.

[cerulean cosmos]

Ok makes sense but since my numerator has x^n+1 and in the other equation the numerator xⁿ

Im still seeing some difference here

[sick dirge]

Oh wait.

[sick dirge]

Sorry didn't see that. Yours is the sum up to n. This is the sum up to (n - 1).

[cerulean cosmos]

Ahh. Gotcha. Thank you.

[spice basin]

Hey guys, can you explain to me how can I reach the final answer, in this case is d. I'm having a very difficult time to understand this concept

[stray reef]

do you still need help with this?

[spice basin]

can you give me the name of this type of worksheet only ?

It's will be great if you help me but more importantly, I need to know the name of this type of problem for more further practice

[idle hazel]

so the subset {1,2} is the same as {2,1} right? i forgot this basic concept

[stray reef]

you mean set, not subset

but yes

[stray reef]

this problem does not belong to a type with a name

but if i had to give it a name it would be "finding gcd and lcm through prime factorization"