Dominion Strategy Forum

Please login or register.

Login with username, password and session length
Pages: 1 ... 4 5 [6] 7 8 ... 47  All

Author Topic: Maths thread.  (Read 307190 times)

0 Members and 2 Guests are viewing this topic.

dnkywin

  • Scout
  • ****
  • Offline Offline
  • Posts: 43
  • Respect: +57
    • View Profile
Re: Maths thread.
« Reply #125 on: May 13, 2014, 01:02:07 am »
0

Will we ever get a problem where we actually get to find a counter-example?  :P

I won't answer that, but I will just say, your proof is wrong.
Try my problem maybe?  :P I'll post a solution after a while if nobody gets it.
Logged

Kirian

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 7096
  • Shuffle iT Username: Kirian
  • An Unbalanced Equation
  • Respect: +9411
    • View Profile
Re: Maths thread.
« Reply #126 on: May 13, 2014, 10:50:38 am »
+2

I'm thinking of a number between 1 and 100.  What is it?  Show your work.

I think I'm turning into Ozle.
Logged
Kirian's Law of f.DS jokes:  Any sufficiently unexplained joke is indistinguishable from serious conversation.

SirPeebles

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3249
  • Respect: +5459
    • View Profile
Re: Maths thread.
« Reply #127 on: May 13, 2014, 10:56:18 am »
0

12.7
Logged
Well you *do* need a signature...

Awaclus

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 11809
  • Shuffle iT Username: Awaclus
  • (´。• ω •。`)
  • Respect: +12847
    • View Profile
    • Birds of Necama
Re: Maths thread.
« Reply #128 on: May 13, 2014, 11:48:27 am »
0

I'm thinking of a number between 1 and 100.  What is it?  Show your work.

I think I'm turning into Ozle.
You are Ozle. Or rather, we all are Wandering Winder.
Logged
Bomb, Cannon, and many of the Gunpowder cards can strongly effect gameplay, particularly in a destructive way

The YouTube channel where I make musicDownload my band's Creative Commons albums for free

pacovf

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3499
  • Multiediting poster
  • Respect: +3838
    • View Profile
Re: Maths thread.
« Reply #129 on: May 13, 2014, 12:14:20 pm »
+6

I am Spartacus.

EDIT: I think we should start a new thread where we could just post any little random tidbit that doesn't deserve its own topic
« Last Edit: May 13, 2014, 12:17:10 pm by pacovf »
Logged
pacovf has a neopets account.  It has 999 hours logged.  All his neopets are named "Jessica".  I guess that must be his ex.

navical

  • Golem
  • ****
  • Offline Offline
  • Posts: 196
  • Respect: +268
    • View Profile
Re: Maths thread.
« Reply #130 on: May 13, 2014, 05:41:44 pm »
0

Love this solution, but I think there is a minor bug:
Ah, good point.

I agree your fix does work.

I think the easiest way to define "opposite points" is to draw a line through one point that's otherwise outside the convex hull, then drawing a perpendicular to that, calling that the y-axis and using a point with the highest y-coordinate. But your way is neater.

I did wonder about the complexity of the algorithm, but it's not something I know much about, so thankyou for working it out :) Although the thing I like most about this solution is that it's constructable with straight edge and compass - interesting the different attitudes.
Logged

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2479
    • View Profile
Re: Maths thread.
« Reply #131 on: May 13, 2014, 05:57:18 pm »
+2

I'm thinking of a number between 1 and 100.  What is it?  Show your work.
((x^2)-1)/2 where x is the base you are using. Work:

let x represent the base you are using. I interpret that for a number n to be between two numbers a and b means that abs(n-a)=abs(n-b). 1 = 1 base 10 for any base because x^0 always equals 1. 100 is equal to x^2 in any base. In representing numbers in my experience one always uses an integer base (how would a non-integer base work?), and this is clearly a base greater than 1 because you used both 1s and 0s. For any integer greater than 1, x^2>1. That means that for a number n between 1 and x^2, n-1=x^2-n. From there we can get that n = ((x^2)-1)/2.

Ask a silly question and ask for work to be shown, get a silly answer with some sloppy reasoning.
Logged

soulnet

  • Mountebank
  • *****
  • Offline Offline
  • Posts: 2142
  • Respect: +1751
    • View Profile
Re: Maths thread.
« Reply #132 on: May 14, 2014, 11:02:56 am »
+2

Polynomial's problem actual proof:

p(x,y) = xy - 1
q(x,y) = (xy-1) x^2 - y

Verification is left as exercise for the reader (it is not hard at all).

This is an additional line to make it seem like it might be a proof instead of just the counterexample.


Haha, I made you look
« Last Edit: May 14, 2014, 11:04:30 am by soulnet »
Logged

SirPeebles

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3249
  • Respect: +5459
    • View Profile
Re: Maths thread.
« Reply #133 on: May 14, 2014, 11:19:40 am »
0

Well what do you know.  I didn't think it would be possible, but that works.
Logged
Well you *do* need a signature...

soulnet

  • Mountebank
  • *****
  • Offline Offline
  • Posts: 2142
  • Respect: +1751
    • View Profile
Re: Maths thread.
« Reply #134 on: May 14, 2014, 11:51:50 am »
0

Well what do you know.  I didn't think it would be possible, but that works.

For your peace of mind, nobody actually solved it during the contest.
Logged

pacovf

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3499
  • Multiediting poster
  • Respect: +3838
    • View Profile
Re: Maths thread.
« Reply #135 on: May 14, 2014, 12:10:45 pm »
0

Well what do you know.  I didn't think it would be possible, but that works.

For your peace of mind, nobody actually solved it during the contest.

I guess you don't know what the logic to construct the counter example is? I'm kinda... unsatisfied, right now.
Logged
pacovf has a neopets account.  It has 999 hours logged.  All his neopets are named "Jessica".  I guess that must be his ex.

soulnet

  • Mountebank
  • *****
  • Offline Offline
  • Posts: 2142
  • Respect: +1751
    • View Profile
Re: Maths thread.
« Reply #136 on: May 14, 2014, 12:44:20 pm »
0

I guess you don't know what the logic to construct the counter example is? I'm kinda... unsatisfied, right now.

I don't. And as you can imagine, the dimension and cardinality of the space of counterexamples is the same as the dimension and cardinality of all polynomials, so it is hard to say there is something "special".
Logged

SirPeebles

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3249
  • Respect: +5459
    • View Profile
Re: Maths thread.
« Reply #137 on: May 14, 2014, 02:07:29 pm »
+1

Well what do you know.  I didn't think it would be possible, but that works.

For your peace of mind, nobody actually solved it during the contest.

I guess you don't know what the logic to construct the counter example is? I'm kinda... unsatisfied, right now.

A cubic polynomial always has a real root.  So consider px^3 + qx + r = 0. This always has a solution unless both p and q are zero while r is nonzero, so let's just choose r = p+1 to avoid all three being zero.  Solve for q and you find -q = px^2 + r/x.  We want q to be a polynomial, so let's add a new variable y = r/x.  Voila.  Now p = r - 1 = xy - 1, and -q = p x^2 + r/x = (xy - 1) x^2 + y.
Logged
Well you *do* need a signature...

dominator 123

  • Moneylender
  • ****
  • Offline Offline
  • Posts: 164
  • Shuffle iT Username: dominator 123
  • Notice the space
  • Respect: +369
    • View Profile
Re: Maths thread.
« Reply #138 on: May 15, 2014, 10:25:36 am »
0

Well what do you know.  I didn't think it would be possible, but that works.

For your peace of mind, nobody actually solved it during the contest.

I guess you don't know what the logic to construct the counter example is? I'm kinda... unsatisfied, right now.

A cubic polynomial always has a real root.  So consider px^3 + qx + r = 0. This always has a solution unless both p and q are zero while r is nonzero, so let's just choose r = p+1 to avoid all three being zero.  Solve for q and you find -q = px^2 + r/x.  We want q to be a polynomial, so let's add a new variable y = r/x.  Voila.  Now p = r - 1 = xy - 1, and -q = p x^2 + r/x = (xy - 1) x^2 + y.
Or simply the cubic graph ranges from -infinity to infinity so it must cross the line x=0 somewhere.
Logged
"Strictly Better" compares only effects and not cost, change my mind

heron

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1055
  • Shuffle iT Username: heron
  • Respect: +1183
    • View Profile
Re: Maths thread.
« Reply #139 on: May 15, 2014, 07:21:31 pm »
0

I think I will post a well-known combinatorics question now:

17 students take a 9-question test. For each question on the test, at least 11 students answered the question correctly. Prove there there exist 2 students such that between them they have answered each question correctly.
Logged

SirPeebles

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3249
  • Respect: +5459
    • View Profile
Re: Maths thread.
« Reply #140 on: May 16, 2014, 09:09:15 am »
0

I just read a headline asking whether a certain national health policy would lead to fewer deaths.  I wish news reporters were better at mathing :(

(I'm not giving further details because I don't want a political/policy discussion)
Logged
Well you *do* need a signature...

Jack Rudd

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1323
  • Shuffle iT Username: Jack Rudd
  • Respect: +1379
    • View Profile
Re: Maths thread.
« Reply #141 on: May 16, 2014, 12:53:50 pm »
+1

I think I will post a well-known combinatorics question now:

17 students take a 9-question test. For each question on the test, at least 11 students answered the question correctly. Prove there there exist 2 students such that between them they have answered each question correctly.
With at least 99 correct answers and only 17 students, at least one student must have at least six answers right. Let us concentrate on that student and the three questions he got wrong (if he got 7 or more right, the same types of arguments work but are significantly more trivial to see). Then each of those three questions can only have been got wrong by five of the other students. Even if no two of those students got the same question wrong, that accounts for only fifteen students. The other student therefore got them all right.
Logged
Centuries later, archaeologists discover the remains of your ancient civilization.

Evidence of thriving towns, Pottery, roads, and a centralized government amaze the startled scientists.

Finally, they come upon a stone tablet, which contains but one mysterious phrase!

'ISOTROPIC WILL RETURN!'

sudgy

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3431
  • Shuffle iT Username: sudgy
  • It's pronounced "SOO-jee"
  • Respect: +2706
    • View Profile
Re: Maths thread.
« Reply #142 on: June 16, 2014, 12:12:30 am »
0

(This is probably actually not the best way to go about things, and is half in jest.  You'll see my point at the end.)

Alright, so I decided to try to extend the divisor function σ(n) to the Gaussian Integers.  I realized that the best way to do this is to make it so that only certain numbers can be divisors, because making them all divisors makes the divisor function equal to 0.  After much trial and error, I figured out what would make the best sections.  The two sections are:

Section 1: All numbers in the first and second quadrants of the Cartesian Plane, including the negative reals and not including the positive reals.

Section 2: All numbers in the third and fourth quadrants, including the positive reals and not including the negative reals.

All of the divisors of a Gaussian Integer Z are defined as the Gaussian Integers x in the same section as Z, that, when multiplied by another Gaussian Integer y in the same section, equal Z.

Using this definition, we can find the value of the divisor function for a few different complex numbers:

σ(i) = 0
σ(1 + i) = 0 (I think)
σ(-2i) = (-2i) + (1) + (1 - i) + (2) + (-i) = 4 - 4i
σ(3i) = 0

Wait, let's look at the abundancy at a couple of those.  i and 3i both have an abundancy of 0.  That means they are friendly.  You might not notice, but this has huge ramifications.

...I just proved the existence of imaginary friends.  ;)

(Yes, this was inspired by this xkcd)
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

heron

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1055
  • Shuffle iT Username: heron
  • Respect: +1183
    • View Profile
Re: Maths thread.
« Reply #143 on: June 17, 2014, 11:54:15 pm »
0

I am stumped by the following combinatorics question:

In a mathematical competition some competitors are friends. Friendship is always mutual. Call a group of competitors a clique if each two of them are friends. (In particular, any group of fewer than two competitors is a clique.) The number of members of a clique is called its size.

Given that, in this competition, the largest size of a clique is even, prove that the competitors can be arranged into two rooms such that the largest size of a clique contained in one room is the same as the largest size of a clique contained in the other room.

(ISL 2007, Vasily Astakhov)

I have so far tried induction of various forms, none of which proved successful. I also thought that maybe proving the contrapositive would be easier, but it wasn't. My current tactic is to try to create an algorithm to produce the two rooms with equally sized cliques. This path shows some progress, but there are many cases.

Maybe one of you guys will have better luck.
Logged

DStu

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2627
  • Respect: +1490
    • View Profile
Re: Maths thread.
« Reply #144 on: June 18, 2014, 01:33:57 am »
0

"size of a clique contained in one room" is now only the size on the subset of competitors that are in this room, ignoring the other room? Or do you have to place cliques in one room? Obviously not, because in this case the result would be false...
Logged

florrat

  • Minion
  • *****
  • Offline Offline
  • Posts: 542
  • Shuffle iT Username: florrat
  • Respect: +748
    • View Profile
Re: Maths thread.
« Reply #145 on: June 18, 2014, 02:47:16 am »
+1

This problem is very very hard. I recognize it for being problem IMO 2007-3 which should give an indication of the difficulty. (what does ISL mean? IMO shortlist?)

I have never solved this problem, but I've read the solution when I participated in that IMO a couple years back. You indeed construct an algorithm to make the clique sizes equal.
IIRC, you start with everyone in room A, and then send persons to room B one by one. The nice thing about this is that when you send a person from room A to room B, the max clique size in room A goes down by at most one and the max clique size in room B goes up by one. So the only way this can go wrong is when at some point the difference in max clique size is one, and when you send a person to room B which changes the clique size in both rooms. Unfortunately, you cannot avoid this case in general, so you have to do some more work by sending the right people in room B back to room A.
I forgot the details. If you want to know the solution, you can find it here [pdf].

"size of a clique contained in one room" is now only the size on the subset of competitors that are in this room, ignoring the other room?
Yes
« Last Edit: June 18, 2014, 02:49:20 am by florrat »
Logged

heron

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1055
  • Shuffle iT Username: heron
  • Respect: +1183
    • View Profile
Re: Maths thread.
« Reply #146 on: June 18, 2014, 07:49:43 pm »
0

This problem is very very hard. I recognize it for being problem IMO 2007-3 which should give an indication of the difficulty. (what does ISL mean? IMO shortlist?)

I have never solved this problem, but I've read the solution when I participated in that IMO a couple years back. You indeed construct an algorithm to make the clique sizes equal.
IIRC, you start with everyone in room A, and then send persons to room B one by one. The nice thing about this is that when you send a person from room A to room B, the max clique size in room A goes down by at most one and the max clique size in room B goes up by one. So the only way this can go wrong is when at some point the difference in max clique size is one, and when you send a person to room B which changes the clique size in both rooms. Unfortunately, you cannot avoid this case in general, so you have to do some more work by sending the right people in room B back to room A.
I forgot the details. If you want to know the solution, you can find it here [pdf].

"size of a clique contained in one room" is now only the size on the subset of competitors that are in this room, ignoring the other room?
Yes

Thanks for the link. Yes, ISL stands for IMO Shortlist. Nested acronyms ftw.

I see that if I had continued down that path I might have finished. Oh well. Maybe if I had used the same style of diagram they used in the solution I would have been able to envision the cases better.

It's cool that you went to IMO though! I hope to be able to go in two years, but I will need to make a lot of improvement.
Logged

scott_pilgrim

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1102
  • Respect: +2144
    • View Profile
Re: Maths thread.
« Reply #147 on: June 18, 2014, 08:15:15 pm »
+4

Logged

ConMan

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1400
  • Respect: +1705
    • View Profile
Re: Maths thread.
« Reply #148 on: June 18, 2014, 11:29:12 pm »
0

Nested acronyms ftw.

NAF!
I prefer recursive acronyms. For example, TIARA is a recursive acronym.
Logged

Tables

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2816
  • Build more Bridges in the King's Court!
  • Respect: +3347
    • View Profile
Re: Maths thread.
« Reply #149 on: June 27, 2014, 08:17:12 am »
0

Consider the complete graph on 7 vertices (that is, 7 points, all of which have an edge connecting them to every other point). It has 21 edges. It's possible to pick 7 triangles of 3 edges such that the edges form a triangle, and each edge is part of only one triangle (an example is shown below).

How many different sets of triangles can be picked like this?



My answer: I made the answer 30, which I think is correct, but I think it's an interesting enough question to have a go at.
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.
Pages: 1 ... 4 5 [6] 7 8 ... 47  All
 

Page created in 0.1 seconds with 21 queries.