Editor, Expert player (2073)
Joined: 6/15/2005
Posts: 3282
p4wn3r wrote:
In a previous post, I mentioned the following result: If a and b are two positive integers, with gcd(a,b)=1, then the set S = {ma+nb | m,n integers in Z} = Z However, if we constrain m and n to be non-negative integers, it's in general not true that the set will be {0, 1, 2, ...}. For this case, however, we still can say something. Namely, if we define f(a,b) the largest integer not expressible by the form ma+nb (or, as a mathematician would say, a linear combination with non-negative integer coefficients), we have: For any integers a, b greater than 1 such that gcd(a,b)=1, f(a,b) = ab-a-b Prove this.
Proof by citation: https://artofproblemsolving.com/wiki/index.php/Chicken_McNugget_Theorem This is known as the (Frobenius) coin problem on Wikipedia, by the way. For n=2, the formula is well-known.
Player (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
Nice! Cut the knot also gives a proof based on generating functions. You can actually find everything that AoPS derives directly, by looking at the values of the polynomial at x=1 and x=-1, although you do need to apply l'Hopital to actually evaluate them. Anyway, about its generalizations for higher n, for n=3, people have found a closed "formula" (if you can call it that) that's usually to messy to write down. For higher n, even showing that the number exists is quite a challenge. The standard proof invokes Schur's theorem. However, there's a very elegant proof using sheaf cohomology, which is how I came to be interested on it. This time, however, the complicated stuff is helpful and it actually improves the elementary solution quite a bit, It turns out that one can construct the proof using Castelnuovo-Mumford regularity and actually prove a bound for the Frobenius number. This is very unusual. Usually homological/category-theoretical methods are highly non-constructive and provide no insight into elementary problems. For this one, however, it seems to be the only approach that yields a useful result!
Editor, Expert player (2073)
Joined: 6/15/2005
Posts: 3282
p4wn3r wrote:
For higher n, even showing that the number exists is quite a challenge. The standard proof invokes Schur's theorem.
Can't you just use induction on n to prove it?
Player (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
FractalFusion wrote:
p4wn3r wrote:
For higher n, even showing that the number exists is quite a challenge. The standard proof invokes Schur's theorem.
Can't you just use induction on n to prove it?
If you want to approach the problem elementarily, yes, but it does get a bit messy when you write down the bound. The elementary induction approach is given here, in Proposition 2.1. Well, at least I think it's hard to write down the bound, others may find it easier. Anyway, the bound you get from that is horrible. The same text proves it using Schur's theorem in Proposition 2.2, where the bound is better, but still not that great. For the McNugget problem (6, 9, 20), it gives 5*19=95, when the actual value is 44, less than its half. Anyway, I'm not that interested in the elementary approach. By using generating functions, Schur's theorem arises quite naturally by looking at the multiplicity of the poles. See page 98 here. From this, it's quite simple to prove the existence using Schur's theorem directly.
Player (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
Next one! Prove that P.S.: I recently came across this video sketching the proof of the Banach-Tarski paradox. It's much simpler than I thought it was, very similar to the construction used in the Grand Hotel paradox.
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
For the life of me I cannot remember if I have asked this before in this thread (it's 116 pages, and apparently the search functionality of this version of phpbb is broken in that you cannot search for posts containing all of the search terms; or at least I can't figure out a way to do it; the setting that supposedly selects "search for all the terms" seems to have no effect), and I'm too lazy to browse through 116 pages of posts, so I apologize if I already asked this and it was answered. Anyway, in this video blackpenredpen casually does ln(-2) = ln(-1) + ln(2) This got me thinking whether the logarithm rule is valid when the argument is negative. (After all, there are lots of rules in math that are valid only when the arguments are valid. Ignoring such rules is commonly the basis for "proofs" that 1=2, etc.)
Player (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
I remember you asking something along these lines about the sine function. In essence, your observation is correct. The logarithm function we all see in high school is defined from the set of positive real numbers to the set of real numbers. In view of this, it's already wrong to even write ln(-2), because -2 is not in the domain, and the final result makes no sense either. He gives an infinite sequence of complex numbers, when the answer should be a single real number. From this (narrow) point of view, his result is not just wrong, it simply does not "compile". If a sentence like that comes up in a test, for example, by all means mark it as wrong. However, this kinda misses the point. In the real world, mathematicians need to generalize things, in the hope that these will help them solve harder problems. It's a somewhat speculative endeavor, no one knows if a new concept will help solve tough problems, if we did we would already have solved them! You should understand this video as "can we generalize the logarithm so that it makes sense to evaluate it at negative numbers?". The answer is yes, but there's not an unique way (in fact, in math you can generalize pretty much everything in a non-unique way, or else it wouldn't be a generalization xD) I could also claim ln(-2)=ln(2). Notice that ln(1) = ln(-1)+ln(-1), which gives ln(-1)=0. So, ln(-2)=ln(2)+ln(-1)=ln(2) Unjustified algebra arguments were a favorite of Euler. They are strictly speaking wrong, but they often lead to deep ideas. When blackpenredpen writes the distributive law of the logarithm for negative numbers, he's in fact making a political statement. He believes this law to be so important, that his generalized logarithm should obey it, or even be defined by it. In modern terms, he's thinking of the logarithm as a homomorphism that should preserve some operations in a prescribed manner. And it turns out that, defined this way, it can be made rigorous. His logarithm is perfectly well defined as a homomorphism that takes the set of non-negative real numbers to the complex plane (where numbers that differ by a multiple of 2pi*i should be considered equal) and maps the multiplication on the reals to addition in the complex numbers. In category theory, the whole syntax of the definitions is made to allow these kinds of arguments to be carried out rigorously with ease. There's a famous manifesto which is pretty accessible to computer scientists that introduces this kind of reasoning.
Editor, Expert player (2073)
Joined: 6/15/2005
Posts: 3282
p4wn3r wrote:
Next one! Prove that
(All products are over the prime numbers) There are two important identities: prod(1-1/p^s)=1/ζ(s) prod(1+1/p^s)=ζ(s)/ζ(2s) First one is by Mobius inversion; second is because prod(1+1/p^s) = prod(1-1/p^(2s))/prod(1-1/p^s) = ζ(s)/ζ(2s) So: prod[(p^4+1)/(p^4-1)] = prod[(1+1/p^4)/(1-1/p^4)] = (ζ(4)/ζ(8)) / (1/ζ(4)) = ζ(4)ζ(4)/ζ(8) and by ζ(4)=pi^4/90 and ζ(8)=pi^8/9450, ζ(4)ζ(4)/ζ(8) simplifies as 7/6.
Patashu
He/Him
Joined: 10/2/2005
Posts: 4043
I came up with a puzzle while falling asleep. If you've ever played Minesweeper before, you'd know that if you set the mine quantity VERY low or get VERY lucky, you can solve a board in almost no time, because you don't actually have to flag every mine - just reveal cells until every unrevealed cell is a mine, e.g. Link to video So an interesting question might be to ask - if you had TAS levels of luck, what's the most mines you could have on a board, while still solving it instantly? ... But that's actually not interesting - just have there be one less mines than the board size. Then whatever tile you click on solves the level! So a slightly MORE interesting question would be to additionallyrequire every mine to be adjacent to a clue (so no mines entirely surrounded by mines/out of bounds). On a 15x15 board I get 96 (pretend the 1s are the appropriate numbered clue):
***************
*111**11111111*
*1 1**1      1*
*1 1**1 1111 1*
*1 1**1 1**1 1*
*1 1**1 1**1 1*
*1 1**1 1**1 1*
*1 1**1 1**1 1*
*1 1**1 1**1 1*
*1 1**1 1**1 1*
*1 1**1 1**1 1*
*1 1111 1**1 1*
*1      1**1 1*
*11111111**111*
***************
Is this the best 'pattern' or is there an even more powerful one?
My Chiptune music, made in Famitracker: http://soundcloud.com/patashu My twitch. I stream mostly shmups & rhythm games http://twitch.tv/patashu My youtube, again shmups and rhythm games and misc stuff: http://youtube.com/user/patashu
DrD2k9
He/Him
Editor, Judge, Expert player (2213)
Joined: 8/21/2016
Posts: 1088
Location: US
Patashu wrote:
So a slightly MORE interesting question would be to additionallyrequire every mine to be adjacent to a clue (so no mines entirely surrounded by mines/out of bounds). On a 15x15 board I get 96 (pretend the 1s are the appropriate numbered clue):
***************
*111**11111111*
*1 1**1      1*
*1 1**1 1111 1*
*1 1**1 1**1 1*
*1 1**1 1**1 1*
*1 1**1 1**1 1*
*1 1**1 1**1 1*
*1 1**1 1**1 1*
*1 1**1 1**1 1*
*1 1**1 1**1 1*
*1 1111 1**1 1*
*1      1**1 1*
*11111111**111*
***************
Is this the best 'pattern' or is there an even more powerful one?
200 Bombs on a 15x15 board:
***************
*8*8*8*8*8*8*8*
***************
***************
*8*8*8*8*8*8*8*
***************
***************
*8*8*8*8*8*8*8*
***************
***************
*8*8*8*8*8*8*8*
***************
***************
*8*8*8*8*8*8*8*
***************
All bombs touch a number 8 somewhere. EDIT: Sorry I somehow missed the requirement to have an instant win in one click. EDIT #2: I'm guessing that 96 is the max possible, but there are other patterns that could still yield that number of bombs.
***************
*5333333333335*
*3           3*
*3 12333333335*
*3 2***********
*3 3***********
*3 3**53333335*
*3 3**3      3*
*3 3**533321 3*
*3 3*******2 3*
*3 2*******2 3*
*3 123333321 3*
*3           3*
*5333333333335*
***************

OR

***************
*5333333333335*
*3           3*
*3 12333333335*
*3 2***********
*3 2***********
*3 12333333335*
*3           3*
*3 12333333335*
*3 2***********
*3 2***********
*3 12333333335*
*3           3*
*5333333333335*
***************
These, along with your design, could obviously be rotated or mirrored in any direction.
Editor, Expert player (2073)
Joined: 6/15/2005
Posts: 3282
Riddler has an interesting Ridder Express problem, as follows: ---- While spending more time at home in recent weeks, I’ve had the chance to revisit one of my favorite video games from recent years — The Legend of Zelda: Breath of the Wild. Within the game, there are hundreds of hidden “Korok Seeds,” which I’m having an increasingly difficult time finding. Fortunately, there’s a special mask you can acquire in the game that makes a sound any time you’re within a certain distance of a Korok Seed. While playing, I marked nine distinct locations on the game map, forming the 3-by-3 grid shown below: 9 icons in a 3x3 grid. No Korok seeds were within range of the central icon, but all 8 surrounding icons were within range. Each leaf symbol is within range of a Korok Seed, while the point in the middle is not within range of a Korok Seed. Given this arrangement, what is the minimum possible number of Korok Seeds I could have detected? ---- May look a bit tricky at first, but this isn't too hard of a problem.
Player (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
Consider the location where the Korok Seeds are, and draw circles having these points as center, whose radius is the distance the masks can detect the seeds. Seeing the problem this way, we want to minimize the number of circles, all of them with a given radius, where the outer points in the grid are inside the circles, and the center point outside. Can we do it with one circle? Clearly not, a circle is a convex shape. If it contains two points, it contains the entire line connecting them. In particular, if it contains the two diagonal points in the grid, it contains the center one. Therefore, it's impossible to do it with one. So, if we can find a construction with two circles, then it's the minimum. This can be done as follows. Consider two leaves that "form an L". If we imagine the bottom-left one as the origin of an xy axes system (0,0), we pair it with the leaf at (2,1). We can construct a circle containing leaves (0,0), (1,0), (2,0) and (2,1), but not the (1,1) point. For this, construct a line segment between (0,0) and (2,1) and find its midpoint. From this midpoint, construct a perpendicular line going to the bottom right corner. If we define a point on this line sufficiently far, we can define a circle passing through (0,0) and (2,1) that will contain (1,0) and (2,0) but not (1,1). We can repeat the same construction for leaves (0,1) and (2,2) and thus find two circles with the same radius covering the eight leaves, and only them. Therefore, the minimum number of seeds detected is 2. --------------------- Consider a non-constant function f: R -> R satisfying: f(x+y) = f(x)f(y), for all real x and y. Mark as true or false: (1) f(x) is not even. (2) f(0) = 1 (3) f(x) > 0 for all x in R (4) f(x) is an exponential function
Player (98)
Joined: 12/12/2013
Posts: 378
Location: Russia
FractalFusion wrote:
Given this arrangement, what is the minimum possible number of Korok Seeds I could have detected?
My way to solve this problem is here: https://imgur.com/a/e1qRyY0 (album) https://www.desmos.com/calculator/jgadm0j5e0
p4wn3r wrote:
Consider a non-constant function f: R -> R satisfying: f(x+y) = f(x)f(y), for all real x and y.
For those who watched 3Blue1Brown lockdown math, they would think they know answer. But I guess there is some misunderstanding. Proof that is easy to follow that was done by 3Blue1Brown is following: if f(x+y) = f(x)(y) it should also work for y = 0 thus if(x + 0) = f(x)*f(0) = f(x) thus f(0) = 1. Wait! Hold on. Last sentence follows from f(x)*f(0) = f(0) by division by f(0). What if f(0) = zero? Well, then f(x) = f(x+0) = f(x)*f(0) = 0. This means that f(x) = 0 for any x. So, this is why mentioned corner case function f(x) = 0. Spoiler: that is the only constant f(x) satisfying conditions. Second case: f(0) not zero -> f(0) = 1. Move on: f(x+1) = f(x)*f(1), f(x+2) = f((x+1)+1) = f(x+1)*f(1) = f(x)*f(1)*f(1) In other words, for any integer k we have f(x+k) = f(x)*f(1)k Let's call f(1) = a, then f(x+k) = f(x)*ak Then, we have f(1) = f(1/2+1/2) = f(1/2)*f(1/2) = f(1/2)2, thus f(1/2) = +-sqrt(a). Minus sqrt version looks odd, but it fits well so far. So we want to find counterexample. It's easy. f(1/2) = f(1/4+1/4) = f(1/4)*f(1/4) it should be square. So it must be positive. Next, f(1) = f(1/3+1/3+1/3) = f(1/3)*f(1/3)*f(1/3) = f(1/3)3, thus f(1/3)3 = a -> f(1/3) = a1/3. So, for any natural k f(1/k) = a1/k Next, f(2/k) = f(1/k+1/k) = f(1/k)*f(1/k) = f(1/k)2 = (a1/k)2 = a2/k, thus f(2/k) = a2/k. Similarly f(n/k) = an/k for any integer n and natural k. Now we covered all rationals. So only irrationals left. Also we know that f(x+n/k) = f(x)*an/k for any integer n and natural k. Irrational + rational is always irrational. So, we don't have any ristrictions on irrationals. But! within class of irrational x - we know that f(x+n/k) should be f(x)*an/k. So, this is similar to cosets from group theory (I'm not sure that it's precisely cosets). I didn't prove that any set of values for f(x) for each cosets + f(1) is satisfying everything. But I think you can claim it. If we add condition for f(x) to be continious, then for any irrational x there is sequence of rationals n/k with limit x, so f(x) should be limit of an/k so it should be ax. First misunderstanding is filled: if it's continious then yes: f(x) has to be ax or f(x) = 0. Being continious is important! Second misunderstanding is, actually more precise knowledge of previous one. I need only two examples: f(x) = 1 only at x = zero, and everywhere else is 0 is also fit requirements. This is actually how 0x often defined. And next example is following: f(x) = ax for all rational x and f(x) = 0 for anything else is also fit requirements <- this is why I think you can claim that statement about something similar to cosets is true. I want to say more about latest example. Let's prove it fits well. First case: f(rational+rational') = f(rational)*f(rational') - obvious. Second case: f((irrational+rational)+rational') = f(irrational+(rational+rational')) = f(irrational)*an/k for some rational n/k. so this is also ok. (just zero multiplied by something) Third case: f((irrational+rational)+(irrational+rational')) = f((irrational+irrational')+(rational+rational')) = f(x)*f(y)*an/k for irrational x,y and rational n/k. So, this actually disprove my claim about any f(x) for cosets. They actually need to follow same rule: f(x+y) = f(x)*f(y) where x and y is irrational. for example f(sqrt(2)*n/k) = f(sqrt(2))n/k for any rational n/k. This actually means that things similar to cosets should be closed over multiplication by rational and addition of rational. Probably then you can claim that for any values for this new similar to 'cosets' f(x) will fit conditions. Oh, latest is also wrong. f(sqrt(2)+sqrt(3)) = f(sqrt(2))*f(sqrt(3)). You can't define those three independently. Alright. Anyway, I think there exists basis of probably continious number of irrationals where you can arbitrarily define values and reconstruct function using them. Edit: I want to mention recent task from Google Codejam 2020 Round 1B second task under name Blindfolded Bullseye. I don't think everyone here is familar with programming, so for those who interested just look statement there. It's very interesting problem. :) For those who curious about solution, there is "analysis" button with solution. Reason why I mentioned it here, I tell a bit later.
Player (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
r57shell wrote:
Second misunderstanding is, actually more precise knowledge of previous one. I need only two examples: f(x) = 1 only at x = zero, and everywhere else is 0 is also fit requirements.
That's not true. For non-zero x, f(x-x)=f(x)f(-x). For this f, this would imply 1=0, so this function does not work.
Editor, Expert player (2073)
Joined: 6/15/2005
Posts: 3282
For the Korok seeds problem, 2 seeds are enough. (It is easily shown that 1 is not possible.) Below is a diagram showing the positions of the two seeds (labelled by X). The top left one is closer to the blue circles than the center, and the bottom right one is closer to the red circles than the center.
p4wn3r wrote:
Consider a non-constant function f: R -> R satisfying: f(x+y) = f(x)f(y), for all real x and y. Mark as true or false: (1) f(x) is not even. (2) f(0) = 1 (3) f(x) > 0 for all x in R (4) f(x) is an exponential function
Answer: (1), (2) and (3) are all true, and (4) is false Explanation: (3) f(x)=f(x/2)^2 and so f(x) is always non-negative. Furthermore, no f(x) can be 0; otherwise if f(c)=0 for some c, then f(x+c)=f(x)f(c)=0 for all x and so f(x) is the constant zero function, which is not allowed. So f(x)>0 for all x in R, and so (3) is true. (2) f(0)=f(0)^2, and since f(0) is positive from (3), f(0) must be 1. So (2) is true. (1) If f(x) is an even function, then f(x+(-x))=f(x)f(-x)=f(x)^2 but also f(x+(-x))=f(0)=1 (from (2)), so f(x)^2=1. Since f(x) is positive from (3), f(x)=1 for all x (f is the constant one function, which is not allowed). So f(x) is not an even function, and so (1) is true. (4) This is similar to how there are nonlinear solutions to Cauchy's functional equation; that is, f(x+y)=f(x)+f(y) for all real x and y. The explanation runs along similar lines as follows: It is true that f(0) must be 1 (from (2)), and that f(x)>0 for all x (from (3)). However, none of f(x) when x is nonzero is fixed; they are described as follows: Let S be a Hamel basis for R over Q. Here R is considered as an infinite-dimensional vector space over Q, and S is uncountable. Note that S exists because of the axiom of choice but cannot be explicitly described. Then f(x) is uniquely described by the values of f(s) for each s in S, where we can set the value of each f(s) to be any positive number. The equation f(x+y)=f(x)f(y) is sufficient to determine values for all real numbers, given the values over the basis S. This is through closure under addition, subtraction, negation, scalar multiplication by a positive integer, and scalar division by a positive integer. So f(x) need not be an exponential function, and so (4) is false.
Player (98)
Joined: 12/12/2013
Posts: 378
Location: Russia
p4wn3r wrote:
r57shell wrote:
Second misunderstanding is, actually more precise knowledge of previous one. I need only two examples: f(x) = 1 only at x = zero, and everywhere else is 0 is also fit requirements.
That's not true. For non-zero x, f(x-x)=f(x)f(-x). For this f, this would imply 1=0, so this function does not work.
Alright, my mistake :( Then I think for f defined on non-negative R it should work. FractalFusion, thanks, now I know what name of what I was describing. :)
Player (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
r57shell mentioned competitive programming problems. Recently I saw one that's very interesting: https://codeforces.com/problemsets/acmsguru/problem/99999/511 Essentially, write an efficient computer program that finds a solution to a Fermat's Last Theorem-like equation for a field of prime characteristic. The prime and exponent can be as large as 1 million, and the program should run in 750 ms. I am pretty confident I found the solution, but until now, I only had time to code a solution in Kotlin, using functional style so that I could do it fast. Unfortunately, it used way too much memory and I got Time Limit Exceeded. I'll try to write a solution in C++ to see if I can get it to pass. Meanwhile, think about the problem! EDIT: Got AC, the time limit is very tight, and I had to optimize, so it's a programming problem just as it is a math one!
Editor, Expert player (2073)
Joined: 6/15/2005
Posts: 3282
p4wn3r wrote:
r57shell mentioned competitive programming problems. Recently I saw one that's very interesting: https://codeforces.com/problemsets/acmsguru/problem/99999/511 Essentially, write an efficient computer program that finds a solution to a Fermat's Last Theorem-like equation for a field of prime characteristic. The prime and exponent can be as large as 1 million, and the program should run in 750 ms.
Just talking about math theory here (no programming): By multiplying both sides by the multiplicative inverse of x (mod p), you can simplify it to solving 1+Y^n=Z^n, where Y and Z are nonzero (mod p). Then you just generate nth power residues until you get a collision of two consecutive values (which is extremely likely if the nth power residues constitute more than even a small fraction of all modulo classes) or you exhaust them all. If the nth power residues constitute a very large fraction of all modulo classes, such as 1/3 (this happens when n=3 and p=6k+1), then for large enough p a solution is a practical certainty due to how many collisions there are (in fact, it is a proven certainty). So in that case, you just need to guess at a few small values and check whether they are nth power residues until you find two consecutive numbers that work (which can be done efficiently), then find their nth roots using polynomial factorization over Zp, or by other, possibly more efficient, methods such as the https://en.wikipedia.org/wiki/Tonelli-Shanks algorithm. Not sure what your program is like, but I'm guessing it goes along these lines.
Player (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
It's more or less along these lines, but there are more optimizations, that you are unlikely to see unless you keep submitting the problem. I actually solved the equation X^N + Y^N = 1, reducing the problem to whether there are two N-th powers that sum to p+1. Finding two consecutive powers works just as fine. As mentioned, since the map a -> a^n is essentially "random", we expect to find powers that satisfy with complexity O(sqrt(p)), as opposed to O(p). This map can also be efficiently computed by exponentiation by squaring. However, there's still a catch. It's not hard to prove (use the fact that the multiplicative group of a field of prime size has a primitive root) that the image of the endomorphism a -> a^n has size (p-1)/gcd(n,p-1). Because of this, the judge can make it very unlikely for us to find a solution by sending an n which shares lots of common factors with p-1. That way, the set will be very small, and you'll have to scan a large portion of the residues to find a solution, if one exists at all. The solution to this is simple. Keep track of the size of the set of n-th power residues. If, at any point, you reach (p-1)/gcd(n,p-1), give up and say it's impossible. I found this solution pretty neat when I found it. There are two cases: (1) the image of the endomorphism is large and we are very likely to find a solution in O(sqrt(p)) because of "randomness", (2) the image of the endomorphism is small, and we are very likely to find all its elements in O(sqrt(p)), again because of randomness. It should also be pointed out that a -> a^n is not "random" if n = 1 mod (p-1), since by Fermat's Little Theorem, it's just the identity map. But this case is trivial and we can simply write down a solution. DM me if you want the exact code (I don't want to post it on the Internet so anyone can submit it and get the problem), but the idea is:
if p is 2, output impossible
if p is not two, but n = 1 mod (p-1), output 1 1 2
declare a map m
for all numbers k, from 1 to p-1:
  compute a <- k^n
  set m[a] = k
  if (m[p-1-a] is not null) output m[a], m[p-1-a], 1 and break
  if (m.size = (p-1)/gcd(n,p-1)), output impossible and break
The implementation of the map has to be very efficient, because of the tight time limit. If you're using C++, it's just knowing which functions to call to make it run fast.
Player (98)
Joined: 12/12/2013
Posts: 378
Location: Russia
r57shell wrote:
Edit: I want to mention recent task from Google Codejam 2020 Round 1B second task under name Blindfolded Bullseye. I don't think everyone here is familar with programming, so for those who interested just look statement there. It's very interesting problem. :) For those who curious about solution, there is "analysis" button with solution. Reason why I mentioned it here, I tell a bit later.
I waited a bit because I don't want to spoil solution. Part of my question is related to solution. I'll rephrase everything to make question what I find interesting / related. You have square, and you know that there is disk non-strictly inside square. And nothing moves. Everything is in fixed position. You can tell is point non-strictly inside the disk or is it strict outside the disk. How many points enough to check to find at least single point non-strictly within the disk knowing that radius of the disk is greater than one fourth of side of the square.
Player (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
I guess I don't count, because I looked at the solution analysis when you posted it :P Anyway, I have an "abstract nonsense" exercise (which is just about bashing definitions until they fit, which is always a lot of fun!). I already put the definition of a category here, but I'll put it again, because this thread is way too long. A category consists of a collection of objects, and for each pair of objects, a set of morphisms between them. The collection of objects of a category C is often denoted obj(C), but we will usually denote the collection also by C. If A,B are in C, then the set of morphisms from A to B is denoted Mor(A,B). Morphisms compose as expected. If f is in Mor(A,B) and g is in Mor(B,C), there is a morphism g o f in Mor(A,C). Composition is associative. For each object A in C, there is the identity morphism idA: A -> A, such that every morphism that's composed with it, either left or right, returns the same morphism. A morphism f is called an isomorphism if there is a (necessarily unique) morphism g such that both f o g and g o f are the identity morphism. Questions: (a) A category where every morphism is an isomorphism is called a groupoid. A perverse definition of a group is: a groupoid with a single object. Make sense of this. (b) Give an example of a groupoid that's not a group.
Player (98)
Joined: 12/12/2013
Posts: 378
Location: Russia
p4wn3r wrote:
I guess I don't count, because I looked at the solution analysis when you posted it :P
There isn't described minimum number of points. If it is, then can you tell location? (for example Test 3 paragraph 5 statement 10, or in any other understandable way. I don't want quote under spoiler (idk why)) Edit: ah, I didn't say points you check are random. So, I don't mean random points. You also allowed to pick next one based on result of previous one.
Aran_Jaeger
He/Him
Banned User
Joined: 10/29/2014
Posts: 176
Location: Bavaria, Germany
So, I wondered ''why not combine TASing with the maths-y puzzlers' interests?''. Maybe some people from here might be intrigued in finding the fastest solutions for some of the levels of ''(SNES) The Brainies'' which I just explained and laid out in here: http://tasvideos.org/forum/viewtopic.php?p=496075#496075 . I think it'd be a game that is much more approachable without using any emulator than how similar situations would be for other games, at least.
collect, analyse, categorise. "Mathematics - When tool-assisted skills are just not enough" ;) Don't want to be taking up so much space adding to posts, but might be worth mentioning and letting others know for what games 1) already some TAS work has been done (ordered in decreasing amount, relative to a game completion) by me and 2) I am (in decreasing order) planning/considering to TAS them. Those would majorly be SNES games (if not, it will be indicated in the list) I'm focusing on. 1) Spanky's Quest; On the Ball/Cameltry; Musya; Super R-Type; Plok; Sutte Hakkun; The Wizard of Oz; Battletoads Doubledragon; Super Ghouls'n Ghosts; Firepower 2000; Brain Lord; Warios Woods; Super Turrican; The Humans. 2) Secret Command (SEGA); Star Force (NES); Hyperzone; Aladdin; R-Type 3; Power Blade 2 (NES); Super Turrican 2; First Samurai. (last updated: 18.03.2018)
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
blackpenredpen once again provides us with some interesting math. If you have an infinite power tower equaling 2, it's quite easy to solve what x is: x^x^x^x^... = 2 Simply notice that since the entire thing is equal to 2, then the power tower starting from the second terms is also equal to 2, so you get: x^2 = 2 -> x = sqrt(2) So, the same should be the case with any other value, right? Like: x^x^x^x^... = 3 -> x^3 = 3 -> x = 3^(1/3) Except that for some reason that's not the case. If you start raising the cube root of 3 to itself over and over, the value does not approach 3, but something else. And, apparently x^x^x^x^... = 3 has no solution at all. There is no value of x for which the power tower is 3. It's not at all apparent why this is. Why does the "substitution trick" work with 2 but not for 3 (or any larger values either). It only works when the value on the right-hand-side is within a certain range. (If you don't know what this range is, that's a math challenge for you.) But why is this so? The only conclusion that I can draw is that even the original substitution trick was mathematically invalid, and it happened to give the correct answer by pure chance. There doesn't seem to be any obvious reason why the trick would be valid when there's a 2 on the right-hand-side but not when there's a 3. (Although I suppose there may well be a mathematical reason for it, but it's certainly not obvious.)
Player (98)
Joined: 12/12/2013
Posts: 378
Location: Russia
tower of x power was also discussed in lockdown math by 3Blue1Brown recently. With solution and proof. Much funnier to ask x^x^x... = 2 straight after ask about x^x^x... = 4, and you get in both questions answer sqrt(2) :D