School vs. discrete mathematics: School texts often start natural numbers at 1; discrete mathematics and computer science often include 0

Why the disagreement?

I'm on team 0.

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

hi, so it's been a couple of hours since i'm trying to prove this my first attempt was to proove it through direct proof by doing the following :

"a" is an integer then

case1: "a" is even so a=2n

a^3=8n^3 /(a^3)-a=8n^3-2n which is not divisible by 3

case2:"a" is odd so a=2n+1/ a^3-a=8n^3+12n^2+4n which is also not divisible by 3 lol

so it would be really nice if u could provide me a lil hint or a general advise to solve this type of prob ty in advance

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.

Just curious if you can imagine the act itself, not necessarily the social implications. Do you think it would be Utopia? If you could access that power to calculate things quickly, would that have a role in the world where p=np?

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

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.

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

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?

In a 3D voxel grid we can generate every possible 3D interaction that could have existed. In binary format, every 1 is where there is an object and 0 is where there isn't an object in the voxel grid. Simply by counting in binary format, until every voxel is filled with 1, we can generate every possible 3D moment that could have existed. This includes objects, languages, formulas, etc. If we combine those models sequentially then we can generate time. I calculated how many possibilities there are for our universe and it's quite insane.

Is there a more efficient way of doing this than this brute force method? With the current technology this is not feasible. If one could find a way to sort through the voxel states coherently like a search engine then they could get any concivable information from it.

I'm watching Numberphile's video on TREE(3), and as they're showing the first few graphs in the sequence, it seems to me like the 3rd graph fits inside the 5th. Both contain two black nodes whos closest common ancestor is a red node; is this not against the rules?

I thought a graph couldn't be contained in a graph further along in the sequence? What am I missing?

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

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?

In decimal 1, 2 and 5 are often used as middle steps between powers of 10. I think the term for that is "preferred numbers". However, in base 6 only two numbers would be needed. 1 is obvious, I'm stuck between choosing 2 or 3. Both are integers and both split the base at the same ratio, just different order. I know 2.4 and 2.5 are a near-perfect split, but I'm looking from the point of, like, currency denominations, and would like to stay away from fractions.

Are there any ways to mathematically determine which division is better, or should I rather look for sociological reasons?

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.

As a bijection is a function that is a surjection as well as an injection(or one-one and onto), we can say that if there are two sets of equal finite cardinality, then there always exists a bijection mapping A to B or vice versa. But, what is the formal mathematical proof of this, the one I saw used heavy higher math. Is there a formalised proof which does not require such advanced study?

A 9X9 board follows standard Sudoku rules i.e. no two numbers can repeat in the same horizontal row, vertical column or 3x3 sub-square, now 9 numbers 1...9 are randomly scattered throughout the entire board without repetition. Since the numbers are all unique the board is always trivially valid with no need for additional checks, the question now is what percentage of these configurations are solvable. (they may have more than one solution)

Note:-

i) A valid set of clues following Sudoku rules may not always be solvable as it may create dead ends later.

ii) There are 6.67 sextillion(6.67 x 10^21) completed Sudoku board configurations.

We can also generalise this problem for any N^2 x N^2 board following sudoku rules and having N^2 clues scattered randomly throughout the entire board without repetition, it isnt possible to use brute force computation for larger values of N. I tried solving it with combinatorics but maybe graph theory would be more suitable for this problem?

Edit:- I made a mistake for the N=2 case and actual solvability is much lower it is only 67.03%.

I came up with a way to use math that suits me. I started with a question “if I were God and I wanted everyone to be able to use math, how would I structure the universe.“ But also “If I could just invent math, what would I invent to be true?” And my question is, do people with degrees turn this part of their brain off?

I was imagining a large number descending to 0 in smaller steps.

Say S is the starting integer of a sequence.

If S= 0, then the sequence is 0.

If S= 1, then the sequence is 1 to 0

If S= 2, then the sequence is 2 to 1 to 0

If S= 3, then the sequence is 3 to 2 to 1 to 0

If S= 81,000, then the sequence 81,000 to 80,919 to 80,903 to 80,902 to 80,901 to 80,900 to 80,899 to 80,898 to 80,897 to 80,896 and so on to... 0.

If S= 256,000, then the sequence is 256,000 to 255,744 to 255,663 to 255,647 to 255,646 to 255,645 to 255,644 to 255,643 to 255,642 to 255,641 and so on to... 0.

If S= 625,000, then the sequence is 625,000 to 624,375 to 624,119 to 624,038 to 624,022 to 624,021 to 624,020 to 624,019 to 624,018 to 624,017 and so on to... 0.

If S= 10,000,000, then the sequence is 10,000,000 to 9,990,000 to 9,983,439 to 9,979,343 to 9,976,942 to 9,975,646 to 9,975,021 to 9,974,765 to 9,974,738 to 9,974,722 to 9,974,722 to 9,974,721 to 9,974,720 to 9,974,719 to 9,974,718 and so on to... 0.

So if we take N to be an integer and S= (1000)*(N^4), then S is 1,000 times power of 4. If S= 1000(N^4), then the first step to descend is N^4, then (N-1)^4, then (N-2)^4, (N-3)^4 until the sequence is descending by 1 each step and heads towards 0. Sorry if the ttile is confusing, I'll repost with a better title if someone can think of a better one.

Would there ever be a number S such that 0 is skipped? So for example an S where at the end of the sequence it goes something like 7,796 to 3,700 (descending 8^4) to 12,99 (descending 7^4) to 3 (descending 6^4) and now the next step would be descending by 625, but that skips 0.

I suspect there will never be an S such that 0 is skipped. The harmonic series diverges but the infinite sum 1/N^4 converges to π^4/90 and my hunch is that this is related to this descending sequence I made up.

Edit someone suggested "let N be the largest integer (if any) such that S >= 1000*(N^4), or 1 if there is no such integer; then subtract N^4, (N-1)^4, (N-2)^4, etc. until you reach 1^4, then keep subtracting 1^4" which is a nice way to put this statement, thank you u/johnpeters42

Can you get very far with writing in simple English enough that people can understand you? Thank you.

Picture this:

Yesterday was my first day in pure math major, in our discrete math lecture we started with arithmetic in Z (divisibility and basic number properties)

At the end of the lecture our professor gave us an assignment

Given a triangle ABC where angle A = 90° and angle B = x and angle C = y. x is a prime number > 5 and y is a composite number.

1) Prove that 7 divides y

2) Find possible pairs of x and y

I literally sat for like 2 hours thinking about the first question, how to derive the proof, nothing worked. Contradiction didn't, contrapositive didn't, the only way I found was y = 90 - x and x is a prime > 5 and < 89 and there are like 20 cases. Of course, such a question must not be solved by brute force.

Any help?

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

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?

Mathematical Problem: Minimum Number of Vectors in an (N x N) Grid
Consider an ( N X N ) square grid, where (N) is any positive integer.
Rules and Definitions
• Empty boxes: Exactly one box in each row and exactly one box in each column must be empty. Therefore, the total number of empty boxes is (x = N).
• Vectors: Every non-empty box belongs to a horizontal or vertical vector. A vector may occupy a single box or multiple consecutive boxes, but it must be straight: it cannot turn or be both horizontal and vertical.
• Counting vectors: A vector is a maximal uninterrupted straight run of non-empty boxes. Consecutive non-empty boxes in the same row or column may belong to one vector; separate runs count as separate vectors.
• Objective: The positions of the empty boxes may vary, provided the rules above are satisfied. Vectors may be horizontal, vertical, or a mixture of both.
The Question
Let ( Y ) denote the total number of vectors and \(x=N) the total number of empty boxes.
Is it true that ( Y > X ) for every valid configuration whenever ( N > 3 ), regardless of the grid size or the arrangement of the empty boxes?

This was one of my practice problems. Everything else had clear answers, but this I can't solve even with ai help. Maybe I am missing something? At least it gives us this cool fraction ladder that looks similar to chain fractions.