In the video, he used:
Let p = all vegetables are orange
Let q= peaches are orange
If p then q
Intuitively, both are false
F then F = T

Then we have this
All vegetables are orange, but not all orange things are vetables , thus false

I saw this problem on instagram reels and was wondering if there is any way to formally show that there exists a walk from the enterance to the exit, adhering to the rule regarding the colors of the lines. I have been learning some graph theory in a discrete structures course at university but i havent seen anything similar to this, where there are different types of edges. Some googling brought me to multigraphs, but i cant find any theorem or lemma which would help with this.

Thanks in advance! Also sorry for the poor drawing.

Recently on an Instagram doom scrolling session, I encountered this interview from Steve Ballmer where he describe his "guessing game", which he gave to interviewees at Microsoft. https://www.youtube.com/watch?v=svCYbkS0Sjk

The basics are:

• Steve Ballmer chooses a number between 1 and 100.
• The interviewee guesses a number, and Steve will tell you if it's high or low.
• If you get it correct on the first guess, then you get $5. Each additional guess reduces the prize by $1, until on the 7th guess you start paying him.

(watch the video if that's not clear)

Should you play this game?

Now, this analysis is pretty easy if Steve chooses a random number. The worst case binary search is lg(100), which rounded up is 7 gusses at worst. And it's easy to make a table of payout of each guess, sum it up and average.

So, on average you'll get $0.20 per game ($20/100). (So yes, you should play)

But that's not the game. The game is whether you should play this game if Steve is able to strategically choose which number. THAT game is much harder to figure out.

As Steve is going to try to choose numbers that are worst case for a binary search, the optimal search algorithm is NOT going to be to start with 50 every time. You would use an alternative search tree in order to optimize for Steve choosing numbers that require 7 guesses. And of course, Steve would then need to optimize his strategy further in kind.

So, as one does, I asked chatgpt how this would work.

Astonishingly, it's very confident that by using a pool of optimal binary search trees, you could get an average payout of $0.196 per game. Meaning we only lose ~1/2cent by allowing steve to choose strategically.

I understand the basics of the strategy, but when it comes to the math of calculating the average payout I am just lost. (Basically everything after and including 296 / 51)

Can anyone explain to me how this works? Or if chatgpt is off its rocker?

I especially can't get my head around the fact that chatgpt believes that Steve has no choices that are more optimal than others. No matter which number Steve chooses, it claims the randomized collection of search trees can make the expected payout exactly 0.196 (average) every time. That doesn't make any intuitive sense to me.

My answer is that you should still play. If both sides play optimally, your expected payout is about +$0.196 per game, or just under 20 cents.

The first thing to notice is that a normal, fixed binary search does not work against a strategic Steve. If you always use the same search tree, Steve can look at that tree, choose one of the numbers that requires 7 guesses, and guarantee that you lose $1.

The solution is to randomize which binary-search tree you use.

This does not mean picking a random number from 1-100 as your first guess. That would often produce a badly unbalanced search. Instead, you randomly choose from many different good binary-search trees. Each individual tree still finds every possible number within 7 guesses, but different numbers occupy the good and bad positions in different trees.

So, for example, 73 might take 7 guesses in one tree, 5 guesses in another, and 4 in another. Steve is allowed to know exactly how your randomized strategy works and choose 73 every single game if he thinks that is best. What he does not know is which search tree you privately selected for that particular game.

We can describe the problem mathematically. Let d(n) be the expected number of guesses needed if Steve chooses the number n. Steve will choose whichever number makes d(n) largest, while you want to choose your randomized strategy so that this largest value is as small as possible.

The optimum turns out to be:

296 / 51 = 5.803921568... guesses

Since the payout on guess k is 6 - k, the expected payout is therefore:

6 - 296/51 = 10/51 = $0.196078...

or about 19.6 cents per game.

The really important part is that this is not an average over Steve choosing different numbers. The randomized search strategy can be constructed so that every single number Steve could choose has the same expected result:

d(1) = d(2) = ... = d(100) = 296/51

So if Steve chooses 1 every game, your expected payout is $0.196078.... If he chooses 50 every game, it is $0.196078.... If he chooses 73, 99, or 100, it is still $0.196078....

In other words, Steve has no number that is better for him than any other. He can study your strategy as much as he wants and deliberately choose what he thinks is the worst number, but the randomized mixture of trees has equalized the expected payout across all 100 choices. Strictly speaking, every number is an equally good choice for Steve — but none of them reduces your expected payout below 19.6 cents.

There are two things that need to be shown for that number to be meaningful. First, you have to show that no strategy can do better. One way to do that is to temporarily imagine Steve assigning weight 2 to the numbers 1 and 100, and weight 1 to every number in between. That gives 102 total weight.

For any valid binary-search tree, you can calculate its weighted total number of guesses. The smallest possible weighted total is 592. Therefore even the best tree has weighted average depth:

592 / 102 = 296 / 51 = 5.803921568...

Randomizing between trees cannot beat that bound, because an average of several trees cannot have a lower weighted cost than the best individual tree for those weights. So no strategy can guarantee an expected search depth below 296/51.

The other half is showing that the bound can actually be reached. Solving the corresponding optimization problem gives a randomized mixture of valid search trees for which:

d(1) = d(2) = ... = d(100) = 296/51

In other words, every possible number has exactly the same expected search depth. Steve can choose whichever number he wants; there is no longer a particularly bad number for him to exploit.

I also checked this by simulation: 1,000,000 games for each of Steve's 100 possible fixed choices, for 100,000,000 games total. The results converge to the same expected payout of about +$0.196 per game.

So the answer is: yes, you should play. If Steve chooses randomly, the game is worth exactly 20 cents per play. If Steve chooses strategically and both sides play optimally, it is still worth about 19.6 cents per play to you.

If pi has no end it has to have every combination of numbers but could it hold an infinite combination? Like 1 2 3 4... To infinity

Please help this is missing my brain up

My maths profesor has given me this problem and said it is the Galactic hard question. I even afraid to attempt it . Like how does the logarithm gets even harder and confusion in all the steps which will be required.

I'm thinking about a chessboard as a graph where each square is connected to other squares by eight edges. Both the bishop and rook can move continuously along four of the eight edges. Yet the rook is worth almost twice as much as the bishop. Why is that?

My philosophy book (and wikipedia) says that there are 256 different logically distinct syllogisms wherein 24 of them are valid

Syllogism - Wikipedia

We know it has the structure

- premise 1

- primeise 2

- conclusion

for example

- All men are mortal.

- Socrates is a man.

- Therefore, Socrates is mortal

Where each of them has a quantifier attached to a binary predicate. There could be 4 different quantifiers attached to the premises and conclusion (all, some, not all, none) so we have 4^3=64 scenarios from that. We obviously need to multiply by more things to get all the scenarios with the predicates and variables out and also there are equivalence classes we need to divide by after that since for example "All M are P" is logically identical to "No M are not P".

This all gets very messy but can someone help me finish the calculation because I seem to get it wrong every time

Friend gave this "easy" sum for Olympiad practice, can't solve it even though I already tried relating it to e's Taylor series done harmonic stuff etc, any help?

Show that n^4 - 5n - 8 is O(n⁴.)

Definition of f(n) is O(g(n)):

Solution:

1. Guess that g(n) = n^4
2. Then 0 <= n^4 - 5n - 8 <= n^4, where B = 1
3. Find b by trial and error ('-->' means 'implies'): a) n = 1 --> 0 <= 1 - 5 - 8 <= 1 --> 0 <= -12 <= 1 --> False, b) n = 2 --> 0 <= 2^4 - 5 x 2 - 8 <= 16 --> 0 <= -2 <= 16 --> False, c) n = 3 --> 0 <= 3^4 - 5 x 3 - 8 <= 81 --> 0 <= 58 <= 81 --> True, d) n = 4 --> 0 <= 4^4 - 5 x 4 - 8 <= 256 --> 0 <= 228 <= 256 --> True, e) n = 5 --> 0 <= 5^4 - 5 x 5 - 8 <= 625 --> 0 <= 592 <= 256 --> True
4. We conclude that b = 3
5. So, 0 <= n^4 - 5n - 8 <= Bn^4, for every n >= b
6. By definition of O-notation, n^4 - 5n - 8 is O(n⁴)

QED

I am trying to find a mathematical way to make a series that goes 1, 2, 4, 16, 256. I don't care what happens after 256.

I can get close with the following 2^(fibonacci(n)-1) starting at n=3. This gives me 1, 2, 4, 16, 128 [2^0, 2^1, 2^2, 2^4, 2^7].

Is there any series that gives the result I want? There is no real reason for this. I just like this series.

I am starting work on the problem and feel as though nobody else is even touching it. Off the top of your head do you know who first formalized the problem? What amount of effort should be going into it, in your opinion? Are there more important math problems?

This is killing me not being able to find it. I remember learning about it, either on a Veritasium video or in one of my classes, but i very vividly remember learning about some theorem that someone made who "Proved" it by calculating up to n=5 i think, and then said "And this pattern continues", but then when you calculate it for one greater than his maximum he calculated it for, it is false, and its false either for all values of n greater than what he tested, or a significant amount. Im trying to find the name of it but i cant for the life of me seem to find it. Please tell me one of yall can help me remember this

Hello,

I've been looking into discrete calculus for the past few days. I’ve also been examining the function below, which I denoted with the capital Lambda symbol. Is there anyone who could help analyze the behavior of this function?

if the infinite summation of 1/n diverges, and the infinite summation of 1/n² is the famous π²/6, what is the smallest value k for which the sum converges? Assuming it's not 2 already

Exericse 11.4.10: Use the definition of logarithm to show that (a) log_b(b^x) = x for every real number x, (b) b^{log_b(x)} = x for every positive real number x

Property 7.2.5:

Solution for (a):

Let log_b(b^x) = y
Then b^y = b^x               by definition of logarithm
Then y = x                   by property 7.2.5
Since log_b(b^x) = y and y = x, log_b(b^x) = x, for every x in R
QED

Solution for (b):

Let log_b(x) = y
Then b^y = x                by definition of logarithm
Also, b^{log_b(x)} = b^y    by substitution
Since b^y = x and b^{log_b(x)} = b^y, b^{log_b(x)} = x, for every x in R^+
QED

Is my solution correct?

Please see attached photo for the problem. I dont really understand how to solve this because I applied the standard induction steps but its a bit complicated for me. I admit that Im not really good at math. I would appreciate if someone could show me how to solve this on paper. I asked help from ChatGPT and other AI tools but its just difficult for me to understand.

This is the description of the Method of Proof by Mathematical Induction according to Epp (I'm working through her book):

This is the example exercise (alluding to the title question):

The description above assumes a general form of the statement to be proved by mathematical induction and it goes like this:

'For every integer n>=a, a property P(n) is true.'

Let A be 'For every integer n>=a'.
Let B be 'a property P(n) is true'.

---

What is A and what is B in the example exercise above? What criteria do we use to distinguish A from B? How do we identify the property P(n)?

In the example exercise, do we use mathematical induction on n or on m ? How do we decide this?

---

Intuitively, I'd say A is 'if n is any interger with n>=1' because it's the first mentioned variable and because 'if n is any integer with n>=1' is equivalent to 'for every integer n with n>=1'. And B is '{then} for every integer m>=1, (n^m)>=1. So we're useing mathematical induction on n.

But I might be wrong.

I’ve been studying a question about graceful path labelings and am trying to determine whether it already has an established name or literature.

Let f be a graceful labeling of a path P_n.

Instead of asking only whether f is graceful, I’m interested in a different question:

How much information about a graceful labeling must be retained in order to determine its possible future extensions?

Suppose we associate some representation I(f) to each graceful labeling. If two labelings f and g have the same representation,

I(f) = I(g)

does that guarantee that they have the same possible continuation behavior?

In other words, I am interested in representations for which:

same retained information => same admissible future extensions

I’ve been calling this property continuation sufficiency, although I don’t know whether there is already standard terminology for it.

For one natural representation of graceful path labelings, an exhaustive finite computation gives the following behavior:

• the representation is sufficient through P_7;
• the first failure occurs at P_8;
• at P_8, two graceful labelings can have identical retained information but different sequential-extension behavior.

One witness pair is:

(4,1,5,3,2,7,0,6)

and

(4,3,1,5,2,7,0,6)

with ports (0,6).

They agree on the representation being tested, but their extension thresholds differ.

What I’m mainly trying to find out is whether this kind of question has already been studied under another name.

For example, is there literature on any of the following?

• equivalence of graph labelings according to extension behavior;
• invariants sufficient to determine future extensions;
• extension-equivalent labelings;
• state minimization for combinatorial extension problems;
• continuation equivalence or right-congruence ideas applied to graph labeling;
• related notions in graceful-labeling theory that I may have missed.

I’m especially interested in references from graph labeling, graph extension problems, combinatorics, or related areas.

I have a proof and computational writeup of the specific P_8 result, but I wanted to ask the literature question directly rather than assume that the formulation is new.

In graph theory, a node's (or vertex) degree is how many other nodes are immediately connected to it by a vertex. What if I wanted to find out how many nodes were connected within say 7 edges? There is the brute force way. I tried to be fancy and come up with shortcuts. For example, if the first node is connected to 3 nodes that each have degree 2, then surely the immediate neighbors are connected to the first node and one other node so there would be 3 nodes one edge from the first node and 3 nodes two edges away? Well no, there could be a cycle.

For context, a magic square is a square grid of numbers in which the sum of the numbers in every row, every column, and both main diagonals is the same value (the magic constant).

I have been trying to construct a very specific magic square. After many attempts, I always end up either repeating a number or violating one of the required sums.

My question is:

Is it possible to construct either

• a 4×4 magic square, or • a 5×5 magic square,

such that:

• the magic sum is exactly 37,
• every entry is a distinct integer (no repeated numbers),
• the integers do not have to be consecutive, and
• every row, every column, and both main diagonals sum to 37?

If such a magic square exists, I would greatly appreciate:

1. A valid example.
2. A construction method or algorithm.
3. A proof or reference explaining why it works.

If no such magic square exists, I would appreciate a proof or explanation showing why it is impossible.

Thank you!

I was doodling stars in lecture and started wondering how many lines you can draw before they begin to overlap.

For a pentagram, you can draw 2 lines before you have to begin overlapping, for 7 points its 3 lines, and for 9 its 4. So for odd numbered stars, it seems to ascend by 1 each time, and the shapes formed before and after overlapping also follow a similar rule.

max lines before overlap = (# of points -1)/2

Ik this is probably just an incidental pattern based on something more basic or obvious, but Im curious if this relates to any math concept? The equation above? Probably something to do with circles.

I’m trying to solve this Jane Street-style water-flow puzzle, but I’m confused about how to model the splitting rule.

My understanding so far is:

The well is a 7-by-7 grid, where each square has a different depth. Water starts at section 1 and enters at 1 cubic foot per minute. Since each section is 1 ft by 1 ft, filling one foot of depth in one section takes 1 minute if the full flow goes there.

The rule says that when water enters a region of constant depth, it immediately disperses to all orthogonally adjacent lower-depth regions evenly along that region’s exposed perimeter. I interpreted this as water flowing from each numbered section to neighboring sections with larger depth numbers, since larger numbers mean deeper sections.

Where I’m stuck is figuring out how to handle branching. For example, from section 1, the lower/deeper adjacent sections are 46 and 44, so I think the water splits between those two. But after that, I’m not sure whether I should track each path separately, treat connected regions as basins, or account for spillover after sections fill.

I’m specifically trying to find how many minutes it takes before water begins to accumulate in section 35. I would appreciate help setting up the correct model/algorithm rather than just the final answer.

Prove that if n is any integer with n>=1, then n^r <= n^s for all integers r and s with r<=s.

Proof 1 (proof by mathematical induction):

Suppose n is any integer with n>=1

Let P(n): For all integers r and s with r<=s, n^r <= n^s

I. Show that P(1) is true

1^r = 1^s, thus 1^r <= 1^s, so P(1) is true

II. Show that for every integer k>=1, if P(k) is true then P(k+1) is true
Let P(k):   For all ints r and s with r<=s, k^r <= k^s [inductive hypothesis]
    P(k+1): For all ints r and s with r<=s, (k+1)^r <= (k+1)^s

(k+1)^r = k^r + (r 1)k^{r-1} + ... + (r r-1)k + 1 [by Binomial Theorem]
       <= k^s + (s 1)k^{s-1} + ... + (s s-1)k + 1 [by inductive hypothesis]
    = (k+1)^s

Thus, P(k+1) is true

Therefore, since we have showed I. and II., P(n) is true

QED

Proof 2:

Proved fact: If n is any integer with n>=1, then for every integer m>=1, n^m >= 1.

Suppose n, r, s are integers with n>=1, r<=s

Then s-r is an integer with s-r >= 0

Case 1: s-r = 0
Then s = r
Thus n^r = n^s, so n^r <= n^s

Case 2: s-r > 0
Then s-r >= 1
Then, by Proved fact, n^{s-r} >= 1
Myltiplying both sides by n^r gives n^r * n^{s-r} >= n^r * 1
Thus n^s >= n^r

Therefore, by Case 1 and Case 2, n^r <= n^s

QED

---
Are my two proofs correct?

Suppose G is a connected graph and T is a circuit-free subgraph of G. Suppose also that if any edge e of G not in T is added to T, the resulting graph contains a circuit. Prove that T is a spanning tree for G.

Proof idea: Proof aims to show that T satisfies the definition of a spanning tree. -> 'A spanning tree for a graph G is a subgraph of G that contains every vertex of G and is a tree.'

Proof:

1. Suppose G is a connected graph and T is a circuit-free subgraph of G
2. Suppose that if any edge e of G not in T is added to T, the resulting graph contains a circuit
3. Claim 1: T is connected
4. Assume for contradiction that T is not connected
5. Let T consist of 2 connected, circuit-free components T_1 and T_2
6. Then we can connect T_1 and T_2 with e without producing a circuit
7. But this contradicts 2.
8. Thus, assumption is false, so T is connected
9. Claim 2: T contains every vertex of G
10. Assume for contradiction that T doesn't contain every vertex of G
11. Let v be a vertex of G that is not in T
12. Then we can connect v and T with e without producing a circuit
13. But this contradicts 2.
14. Thus, assumption is false, so T contains every vertex of G
15. By 1. and 8., T is circuit-free and connected
16. Thus, T is a tree
17. By 1. and 14., T is a subgraph of G and contains every vertex of G
18. Therefore, by 16. and 17., T is a spanning tree for G

QED

---

Is my proof correct?

Recently I have thought of this question, and I have not seemed to find anything similar (it's not really a "proper" or "useful" question, I think):

I am making patterns on a 4 by 4 grid of unit squares. I shade at least one and at most all of the unit squares black such that the resulting shape has at least one line of symmetry. In how many different ways can I do this? Note that two shapes that are rotations and/or reflections of each other are still treated as different.

I've tried to count by how many squares are shaded one at a time, but is there a way to more systematically solve it? Additionally, I haven't come to an actual answer yet. This question does seem easier (or at least less time-consuming) with a 3 by 3 grid so I'm wondering if there's an actual systematic way to approach it with that I'm just not seeing or if it just gets harder with larger grids.