Dominion Strategy Forum

Please login or register.

Login with username, password and session length
Pages: 1 ... 37 38 [39] 40  All

Author Topic: Maths thread.  (Read 90992 times)

0 Members and 1 Guest are viewing this topic.

silverspawn

  • Governor
  • *****
  • Offline Offline
  • Posts: 4108
  • Shuffle iT Username: sty.silver
  • ♦ Twilight ♦
  • Respect: +1817
    • View Profile
Re: Maths thread.
« Reply #950 on: November 13, 2018, 04:58:11 pm »
+4

How would you even start solving it? I haven't graduated high school yet, but I know at least up through Calc II, so I figurde I would be qualified to post in this thread.

But still, I have no idea how to even start.

You probably have no chance (I certainly didn't).

https://www.quora.com/How-do-you-find-the-positive-integer-solutions-to-frac-x-y+z-+-frac-y-z+x-+-frac-z-x+y-4

Quote
You may have seen such meme images before. They are always pure click-bait garbage: “95% of MIT graduates couldn’t solve this!”, where “this” is some inane, or ill-defined, or trivial brain teaser.

This one is not. The meme is a clever, or wicked, joke. Roughly 99.999995% of the people don’t stand a chance at solving it, and that includes a good number of mathematicians at leading universities who just don’t happen to be number theorists. It is solvable, yes, but it's really, genuinely hard.
Logged

Iridium

  • Herbalist
  • **
  • Offline Offline
  • Posts: 6
  • Shuffle iT Username: Iridium
  • Respect: +1
    • View Profile
Re: Maths thread.
« Reply #951 on: November 13, 2018, 06:58:20 pm »
0

Welp.
Back to studying Diff Eq.

oh well :(
« Last Edit: November 13, 2018, 07:02:15 pm by Iridium »
Logged

Awaclus

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 10929
  • Shuffle iT Username: Awaclus
  • (´。• ω •。`)
  • Respect: +11551
    • View Profile
Re: Maths thread.
« Reply #952 on: November 13, 2018, 09:19:05 pm »
0

I tried getting rid of the denominators and gave up after seeing the resulting mess.
Logged
Bomb, Cannon, and many of the Gunpowder cards can strongly effect gameplay, particularly in a destructive way

The Twitch channel where I stream DominionThe YouTube channel where I make musicDownload my band's albums for free

GendoIkari

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 7476
  • Respect: +8299
    • View Profile
Re: Maths thread.
« Reply #953 on: November 13, 2018, 09:43:16 pm »
+4

I'm so tempted to share this on Facebook simply as revenge against the people who post the really stupid things like this simply because it makes them feel smart that they figured out a problem which any grade schooler could figure out.
Logged
Check out my F.DS extension for Chrome! Card links; Dominion icons, and maybe more! http://forum.dominionstrategy.com/index.php?topic=13363.0

Thread for Firefox version:
http://forum.dominionstrategy.com/index.php?topic=16305.0

Oyvind

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 126
  • Respect: +88
    • View Profile
Re: Maths thread.
« Reply #954 on: November 14, 2018, 04:00:25 am »
+1

I tried getting rid of the denominators and gave up after seeing the resulting mess.

At least I came to the following conclusion (a=apple, b=banana, p=pineapple):

a3+b3+p3=3a2b+3a2p+3ab2+3ap2+5abp+3b2p+3bp2

Now, how do we solve this mess?

EDIT: added the closing parenthesis before the colon.
« Last Edit: November 14, 2018, 04:03:10 am by Oyvind »
Logged

Polk5440

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1697
  • Respect: +1769
    • View Profile
Re: Maths thread.
« Reply #955 on: November 14, 2018, 01:08:22 pm »
0

The hard part is the requirement for whole number solutions. Standard algebra techniques can easily get you a real answer. Even a real, positive answer.

For example:
Let  b = p = 1. Now there is a cubic equation in one variable.

a^3 - 6a^2 - 11a - 4 = 0

The rational roots theorem gives possible rational roots of +/-1, +/-2, or +/-4. Checking, -1 is a root. But (-1,1,1) doesn't look good as a solution to the original equation; we get a division by zero. Moving on, dividing out (a+1) gives

(a+1)(a^2 - 7a - 4) = 0

The quadratic formula gives a = (7 +/- sqrt(65))/2. Take the positive root.

You can verify ((7 + sqrt(65))/2, 1, 1) is a solution to the original equation. All three variables are positive and real. But one is irrational.


It's the whole number restriction that puts this into number theory territory and makes this really difficult. The Quora answer linked above does a really nice explaining the (higher) math involved. Wow, is it difficult!

Two side notes: It's not clear why this equation would have such a large "smallest" answer, but if the right hand side equaled 2 instead of 4, the very nice (1, 1, 3) works, no problem. Additionally, the insight that there are whole classes of problems that are "hard to solve, easy to verify" is the basis of a lot of cryptography.
Logged

Kirian

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 7089
  • Shuffle iT Username: Kirian
  • An Unbalanced Equation
  • Respect: +9347
    • View Profile
Re: Maths thread.
« Reply #956 on: November 14, 2018, 08:18:33 pm »
+2

How would you even start solving it? I haven't graduated high school yet, but I know at least up through Calc II, so I figurde I would be qualified to post in this thread.

But still, I have no idea how to even start.

You probably have no chance (I certainly didn't).

https://www.quora.com/How-do-you-find-the-positive-integer-solutions-to-frac-x-y+z-+-frac-y-z+x-+-frac-z-x+y-4

Quote
You may have seen such meme images before. They are always pure click-bait garbage: “95% of MIT graduates couldn’t solve this!”, where “this” is some inane, or ill-defined, or trivial brain teaser.

This one is not. The meme is a clever, or wicked, joke. Roughly 99.999995% of the people don’t stand a chance at solving it, and that includes a good number of mathematicians at leading universities who just don’t happen to be number theorists. It is solvable, yes, but it's really, genuinely hard.

Oh man.  That was actually a brilliant explanation.  I now know more about elliptic curves than I ever had before.
Logged
Kirian's Law of f.DS jokes:  Any sufficiently unexplained joke is indistinguishable from serious conversation.

Oyvind

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 126
  • Respect: +88
    • View Profile
Re: Maths thread.
« Reply #957 on: November 15, 2018, 05:49:35 am »
0

How would you even start solving it? I haven't graduated high school yet, but I know at least up through Calc II, so I figurde I would be qualified to post in this thread.

But still, I have no idea how to even start.

You probably have no chance (I certainly didn't).

https://www.quora.com/How-do-you-find-the-positive-integer-solutions-to-frac-x-y+z-+-frac-y-z+x-+-frac-z-x+y-4

Quote
You may have seen such meme images before. They are always pure click-bait garbage: “95% of MIT graduates couldn’t solve this!”, where “this” is some inane, or ill-defined, or trivial brain teaser.

This one is not. The meme is a clever, or wicked, joke. Roughly 99.999995% of the people don’t stand a chance at solving it, and that includes a good number of mathematicians at leading universities who just don’t happen to be number theorists. It is solvable, yes, but it's really, genuinely hard.

Oh man.  That was actually a brilliant explanation.  I now know more about elliptic curves than I ever had before.

Your comment about elliptic curves should be marked as a spoiler.
Logged

Tables

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2741
  • Build more Bridges in the King's Court!
  • Respect: +3228
    • View Profile
Re: Maths thread.
« Reply #958 on: November 15, 2018, 05:03:51 pm »
+2

I was thinking about a weird probability scenario today, and after figuring out how it worked I was pleasantly surprised with the answer. So I'll present it to all of you to puzzle and see if you enjoy it (and its answer) as much as I did.

A bag contains 1 red and 1 green ball. A ball is taken at random from the bag. Another ball of the same colour is then added to the bag, and the original ball replaced (for example if a red ball is taken, you would end up with 2 red and 1 green balls in the bag). This process is repeated indefinitely.

When the bag contains n balls, find the chance that exactly r balls are red, and (n-r) balls are green, in terms of n and r (n>=2, 1<=r<n, both natural numbers).
Logged
...spin-offs are still better for all of the previously cited reasons.
But not strictly better, because the spinoff can have a different cost than the expansion.
I hereby declare myself the best dominion player in the world. Obviously.

Skumpy

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 126
  • Shuffle iT Username: skumpy
  • Respect: +202
    • View Profile
Re: Maths thread.
« Reply #959 on: November 15, 2018, 05:49:23 pm »
+1

            1/(n-1)     
Not the answer I expected. Cool problem. Easy enough (and very easy for the average problem in this thread) to get the unsimplified version. Then fun to plug in numbers and watch the telescoping magic.
Logged
He is (and take this in a positive light Skumpy) eccentric, flamboyant and excessive at times. His posts are ones that cause people to look at him and say "huh?"

Tables

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2741
  • Build more Bridges in the King's Court!
  • Respect: +3228
    • View Profile
Re: Maths thread.
« Reply #960 on: November 16, 2018, 11:29:58 am »
+1

Yep, that's the correct answer. Much easier than most of this thread, definitely - you can solve it and prove your answer is correct with nothing above AS level Maths (16-17 year old level), though it's a slightly more complex way to put together than they would normally see.

The fact I quite like from the answer is it means every possible arrangement of balls is equally likely. Which is quite unexpected from the problem, I feel.
Logged
...spin-offs are still better for all of the previously cited reasons.
But not strictly better, because the spinoff can have a different cost than the expansion.
I hereby declare myself the best dominion player in the world. Obviously.

silverspawn

  • Governor
  • *****
  • Offline Offline
  • Posts: 4108
  • Shuffle iT Username: sty.silver
  • ♦ Twilight ♦
  • Respect: +1817
    • View Profile
Re: Maths thread.
« Reply #961 on: November 16, 2018, 02:15:02 pm »
0

Without looking at spoilers:

Every number is equally likely, so 1/n.

I first wrote down a recursive formula which didn't help, but once you start to compute a bunch of values it becomes clear.
Logged

silverspawn

  • Governor
  • *****
  • Offline Offline
  • Posts: 4108
  • Shuffle iT Username: sty.silver
  • ♦ Twilight ♦
  • Respect: +1817
    • View Profile
Re: Maths thread.
« Reply #962 on: November 16, 2018, 03:08:25 pm »
0

So intuitively, I guess what explains the result is

balls beget balls, so a one-sided ball population makes a one-sided ball population more likely. This shifts probability to unequal populations. But a priori, similarly sized populations are more likely. Those effects cancel out exactly.
Logged

Titandrake

  • Mountebank
  • *****
  • Offline Offline
  • Posts: 2077
  • Respect: +2528
    • View Profile
Re: Maths thread.
« Reply #963 on: November 19, 2018, 02:14:05 am »
+1

Let me try.

We need to add n-2 more balls. Consider a fixed sequence of red and green balls, r-1 red and n-r-1 green. The probability of drawing balls in exactly this sequence is (r-1)!(n-r-1)!/(n-1)!. The denominator comes from having 2,3,4,...,n-1 balls to pick. For the numerator, at the time we are picking the kth red ball, there must be k-1 other red balls in the bag, and similarly for green. This logic holds for every sequence, and there are (n-2) choose (r-1) = (n-2)!/((r-1)!(n-r-1)!) such sequences, giving a probability of 1/(n-1)

PPE: I messed up my final step a bit but the core logic was correct.
Logged
I have a blog! It's called Sorta Insightful. Check it out?

silverspawn

  • Governor
  • *****
  • Offline Offline
  • Posts: 4108
  • Shuffle iT Username: sty.silver
  • ♦ Twilight ♦
  • Respect: +1817
    • View Profile
Re: Maths thread.
« Reply #964 on: November 23, 2018, 05:54:16 pm »
+2

This is a really cool puzzle from LessWrong (cool because it's super easy to understand and doesn't require any advanced math). Given a graph like this one,



where the key property is that none of the nodes on the left diagonal are green, none on the right diagonal are blue, and none on the bottom are red, prove that an odd number of the n^2 little 3-node triangles is trichromatic (in the above picture there's exactly 1). Light hint: Apply Sperner's 1D lemma (see link). Stronger hint: show that you can change the color of any node without losing this property
« Last Edit: November 24, 2018, 03:27:57 am by silverspawn »
Logged

pacovf

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3365
  • Multiediting poster
  • Respect: +3700
    • View Profile
Re: Maths thread.
« Reply #965 on: November 23, 2018, 10:40:43 pm »
+1

Is a trichromatic triangle a triangle whose 3 corners have different colours, or one in which the sides of the triangle contain all 3 colours?
Logged
pacovf has a neopets account.  It has 999 hours logged.  All his neopets are named "Jessica".  I guess that must be his ex.

silverspawn

  • Governor
  • *****
  • Offline Offline
  • Posts: 4108
  • Shuffle iT Username: sty.silver
  • ♦ Twilight ♦
  • Respect: +1817
    • View Profile
Re: Maths thread.
« Reply #966 on: November 24, 2018, 03:26:45 am »
+1

Is a trichromatic triangle a triangle whose 3 corners have different colours, or one in which the sides of the triangle contain all 3 colours?

Ah, I think you think that bigger triangles also count, right? (Because the two conditions are equivalent for the small ones). But only the small 3-node triangles count.
Logged

Titandrake

  • Mountebank
  • *****
  • Offline Offline
  • Posts: 2077
  • Respect: +2528
    • View Profile
Re: Maths thread.
« Reply #967 on: November 24, 2018, 06:11:39 am »
+1

About to sleep so too lazy to fill in the details but I think I have the core ideas.

statement is equivalent to showing
1. There exists a graph with odd number of RGB triangles.
2. Given any graph, changing the color of 1 vertex to another valid color does not change the parity of RGB triangles.

Combined this is enough because every grid can be transformed into another by some series of color changes.

For 1. Just fill the interior with red, then color the sides all red / blue / green and show there's such a triangle.

For 2. You can enumerate all the cases. Changing 1 vertex affects at most the 6 local triangles defined by the 6 local neighbors so it should be bashable.
Logged
I have a blog! It's called Sorta Insightful. Check it out?

silverspawn

  • Governor
  • *****
  • Offline Offline
  • Posts: 4108
  • Shuffle iT Username: sty.silver
  • ♦ Twilight ♦
  • Respect: +1817
    • View Profile
Re: Maths thread.
« Reply #968 on: November 24, 2018, 08:10:36 am »
0

That's the right approach (or the one I used, anyway), though much of the work is finding a way to do 2. without lots of cases. It can be done in just a few lines.
Logged

Titandrake

  • Mountebank
  • *****
  • Offline Offline
  • Posts: 2077
  • Respect: +2528
    • View Profile
Re: Maths thread.
« Reply #969 on: November 24, 2018, 02:13:37 pm »
0

That's the right approach (or the one I used, anyway), though much of the work is finding a way to do 2. without lots of cases. It can be done in just a few lines.

Well, depends if you want a solution or want a clean solution. The bash isn't terrible, you can exploit a lot of symmetry to reduce the cases.
Logged
I have a blog! It's called Sorta Insightful. Check it out?

heron

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1013
  • Shuffle iT Username: heron
  • Respect: +1134
    • View Profile
Re: Maths thread.
« Reply #970 on: November 24, 2018, 04:25:13 pm »
+2

The classic solution is to

Draw a graph where the vertices are the interiors of the triangles (and also there is a vertex for the outside), and there is an edge between any two triangles separated by a side with both red and green end points. Then a vertex has odd degree iff if is a trichromatic triangle or the outside vertex. The property that the sum of the degrees of the vertices is twice the number of edges finishes the proof, since that means the number of vertices of odd degree must be even.

Edit: note that this solution also shows the existence of trichromatic triangles in more general configurations.

Also bonus problem, using the result of the triangle problem, prove that every continuous function from the closed disk to itself must have a fixed point.
« Last Edit: November 24, 2018, 04:28:04 pm by heron »
Logged

Kirian

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 7089
  • Shuffle iT Username: Kirian
  • An Unbalanced Equation
  • Respect: +9347
    • View Profile
Re: Maths thread.
« Reply #971 on: November 24, 2018, 05:42:41 pm »
0

How would you even start solving it? I haven't graduated high school yet, but I know at least up through Calc II, so I figurde I would be qualified to post in this thread.

But still, I have no idea how to even start.

You probably have no chance (I certainly didn't).

https://www.quora.com/How-do-you-find-the-positive-integer-solutions-to-frac-x-y+z-+-frac-y-z+x-+-frac-z-x+y-4

Quote
You may have seen such meme images before. They are always pure click-bait garbage: “95% of MIT graduates couldn’t solve this!”, where “this” is some inane, or ill-defined, or trivial brain teaser.

This one is not. The meme is a clever, or wicked, joke. Roughly 99.999995% of the people don’t stand a chance at solving it, and that includes a good number of mathematicians at leading universities who just don’t happen to be number theorists. It is solvable, yes, but it's really, genuinely hard.

Oh man.  That was actually a brilliant explanation.  I now know more about elliptic curves than I ever had before.

Your comment about elliptic curves should be marked as a spoiler.

I mean... this is a problem that's basically unsolvable by any other means, and my spoiler is hardly a hint.  I don't think anyone here was actually going to "solve" this--that was the whole point!
Logged
Kirian's Law of f.DS jokes:  Any sufficiently unexplained joke is indistinguishable from serious conversation.

silverspawn

  • Governor
  • *****
  • Offline Offline
  • Posts: 4108
  • Shuffle iT Username: sty.silver
  • ♦ Twilight ♦
  • Respect: +1817
    • View Profile
Re: Maths thread.
« Reply #972 on: November 24, 2018, 06:10:56 pm »
0

The classic solution is to

Draw a graph where the vertices are the interiors of the triangles (and also there is a vertex for the outside), and there is an edge between any two triangles separated by a side with both red and green end points. Then a vertex has odd degree iff if is a trichromatic triangle or the outside vertex. The property that the sum of the degrees of the vertices is twice the number of edges finishes the proof, since that means the number of vertices of odd degree must be even.

Edit: note that this solution also shows the existence of trichromatic triangles in more general configurations.

Also bonus problem, using the result of the triangle problem, prove that every continuous function from the closed disk to itself must have a fixed point.

That is in fact very similar to the following exercises that were posted. (It's a sequence of 13 where the above was #4). More precisely, #5 was proving that every continuous function (with a property mirroring that of the graph of this exercise) from a triangle to the disk has a point that maps to the center, and #6 that every continuous function from the triangle to itself has a fixed point.
Logged

sudgy

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3333
  • Shuffle iT Username: sudgy
  • It's pronounced "SOO-jee"
  • Respect: +2582
    • View Profile
Re: Maths thread.
« Reply #973 on: January 17, 2019, 01:53:21 am »
+2

What do you all think of this problem?  The result is so unexpected when you first hear it.  I managed to solve it myself, but I still think that the result is fascinating.
Logged
If you're wondering what my avatar is, watch this.

Check out my logic puzzle blog!

   Quote from: sudgy on June 31, 2011, 11:47:46 pm

silverspawn

  • Governor
  • *****
  • Offline Offline
  • Posts: 4108
  • Shuffle iT Username: sty.silver
  • ♦ Twilight ♦
  • Respect: +1817
    • View Profile
Re: Maths thread.
« Reply #974 on: January 17, 2019, 10:58:56 am »
0

(Unrelated to sudgy). A few years ago, I made a post here complaining about the way coordinate vectors are introduced in linear algebra. In particular, no-one ever explained me whether, if you write (2,3,4), what you mean is "the element (2,3,4) \in \R^3" or "the vector 2*b_1 + 3*b_2 + 4*b_3 for some basis {b_1, b_2, b_3}". In the former case, writing (2,3,4)_B would then mean "I apply the operation _B to the vector (2,3,4) which means I map it onto 2*b_1 + 3*b_2 + 4*b_3, which is a different vector". And in the latter case, you would technically -always- have to denote which basis you mean when you write down any 'coordinate vector', and not doing this would just be an abbreviation. The second case is weird because no-one follows it consistently (also how do you write down the vectors of a basis? You need two different notations!), and the former is weird once you throw matrices into the mix, because matrices are defined relative to a basis, and vectors aren't. And when you define a function as applying a matrix, i.e. f : x -> A * x it gets even worse, because A still depends on a basis, but f definitely shouldn't. Our lecture did this, ugh. As far as I remember, though there were some decent comments, no-one really gave me a satisfying explanation.

Forward to today, I've been reading "Linear Algebra Done Right" and it immediately did what both lectures I visited didn't manage to. In the book, vectors are elements in F^n, not relative to anything. Matrices are something separate. There is a function M taking any linear map and the basises of two vector spaces and returning a matrix. Matrix multiplication is defined in the usual way, but there is no multiplication of a matrix with a vector. Instead, there is another function which takes a vector and a basis and returns a n*1 matrix representing the vector relative to that basis. That matrix can then be multiplied with another matrix following matrix multiplication as usual.

I find that super awesome, so I wanted to share it. This is actually a completely consistent way to differentiate between vectors and 'coordinate vectors' that answers all questions in a satisfying way, and it's not even difficult! That's how you should do it. The book completely deserves its title. Even though the justification they gave for the title wasn't about this, but about something involving the determinant and how it's usually explained without providing any intuition, which is also true for the lectures I've visited. Looking forward to how this book handles that, too.
Logged
Pages: 1 ... 37 38 [39] 40  All
 

Page created in 0.328 seconds with 20 queries.