Maths Problems Thread

[Roflcopter]

As requested by RCJD, here's a problems thread for everyone to contribute to. When you post a new question in the thread give it a number so we can keep track of them or this will get chaotic.

#1 (easy): Prove there are no Pythagorean triplets (a, b, c) such that a b and c are all primes.

#2 (easy): Prove by construction that Q is dense in R. That is, for any real numbers x and x' (with x < x') find a fraction a/b with x < a/b < x' (a and b are integers, b is non-zero).

#3 (medium, requires programming): Find the number of squarefree numbers less than .

#4 (medium, requires programming): How many primes are there less than 123456789109?

#5 (medium): Find all solutions to with x and y positive integers.

[Marti]

Chuck Norris

[Habluka]

I was half asleep and in a state of being incredibly emotionally unstable when I spent less than a minute writing something out for this in the morning, so I'm not going to bother looking at what I wrote or trying to fix it, but I will do the last two.

Spoiler

4.

Here is how I determine a number isn't prime.

[SELECT ALL] Code:

for (NumericalDataType a = 3; a < numberThatIDontWantToFigureOutInMyHead; a++){
    for (NumericalDataType b = 0; b < numberInTheQuestion; b++){
        /*
         *insert code that involves adds the sum of these numbers to some list as they are not prime (think about it if you don't believe me)
         */
    }
}

the answer is 123456789109 - the length of the list of numbers that are not prime determined from that - (log(123456789109) / log(2)) - 1
or something along those lines. I don't feel like creating the objects I would need to be able to get an actual answer at the moment since I already had to do something similar for a different problem a couple days ago, but this should work.

5. instead of x and y, let's use a and b where a is the smaller integer
because of obviousness, b%a=0, so the closest they can be, which is important since we're dealing with power functions, would mean b = 2*a
f(a) = a ^ (2 * a)
g(a) = (2 * a) ^ a
the value for a at which g(a) = f(a) will allow you to get values for x and y such that x^y = y^x where x and y are integers.
these functions intersect at one point and that one point is (2, 4), meaning the only times when x^y = y^x is when x is 2 and y is 4 and when x is 4 and y is 2.

[Roflcopter]

1. Pythagorean Theorem states that a^2 + b^2 = c^2 and a Pythagorean triplet is 3 numbers that satisfy this that are positive integers. a and b must therefore be positive integers and multiplying and adding integers will always get another integer, so you know that a * a + b * b will be an integer, which means c is the square root of an integer. Because of the definition of a Pythagorean triplet, this means c is a perfect square and thus is unable to be prime.

c is not necessarily a perfect square though. For example the triple (3,4,5) is Pythagorean (since 9+16=25) and c is in fact prime.

2. there are no conditions given that state that x < x', meaning that x can be greater than x'. In this condition, there would be no way that x < a/b < x'. Rewrite this one and I don't like proofs by construction.

You're right it was a bit unclear. You should take x < x'.

3. 10^6 - 1 (takes no programming or real calculations since sqrt(10^12 = 10^6)

A squarefree number is a positive integer n such that no square divides n wholly. For example 18 is not squarefree since 3 squared divides it. But 30 is since it has no square factors.

But that answer is far off. Try working with smaller versions of the problem first. For instance there are 11 squarefrees less than 16: 1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15.

[Mael]

Find all solutions to with x and y positive integers.

Spoiler

2^4 & 4^2. Only one I can answer off the top of my head.

[tempest]

Well, if you think about it, it's not specified that x!=y ;)

[Cemer]

dammit tempest.

[Roflcopter]

Spoiler

2^4 & 4^2. Only one I can answer off the top of my head.

Nice solution for the non-trivial solutions.

Spoiler

Since the question didn't ask for proof I think it's solved. Here is the proof I came to:

We note immediately that x=y is a solution for all positive integers.

We'll now further restrict the question to x<y. Then and since both x and y are integers y must divide x, that is, . So we get which implies k=2, which in turn decides x=2 and y=4.

Hence all solutions are (2, 4), (4, 2) and (λ, λ), λ a positive integer.

Spoiler

I didn't prove that implies k=2 above but it's fairly intuitive. First prove that the function is monotonically decreasing for k>1 (high-school calculus will do). Then note that for k>2 we have 1<f(k)<2 so f(k) can never be equal to an integer.

[Flames]

#1. c=sqr[a^2+b^2].
If. a and b are primes , then square root of a^2 + b^2 will not be an integer. To satisfy the
Pythagoras theorem a, b and c should be integers.

[Roflcopter]

#1. c=sqr[a^2+b^2].
If. a and b are primes , then square root of a^2 + b^2 will not be an integer. To satisfy the
Pythagoras theorem a, b and c should be integers.

Seems a bit like hand-waving. Why cannot the square root of two primes squared be an integer? It's a correct statement but the proof of it is essentially as hard as the original question.

[RCJD]

#6 (No programming or advanced math required. Pure logic)

Five pirates found a treasure chest containing 100 coins, but they don't know how to divide it.
Now, these are all very intelligent pirates and they want to use methods of diplomacy as opposed to barbaric fighting.

You can imagine the five pirates as: A B C D E

They agree on the following rules:
-The first pirate in line will make a proposal on how to divide the money between the five pirates. So Pirate A will make the proposal first. If A dies (see below), then B will be next to make a proposal for the remaining four pirates... And so on.

-Proposals are simply about how to divide the money (ex. "A gets 20, B gets 30, C gets 15, D gets 35, E gets 0"). They cannot contain any conditions (ex. "B promises C he will give him extra coins if C helps B kill off A). These pirates don't trust each other.

-After a proposal is made, the pirates make a vote. The pirate who made the proposal votes "YES" for his own proposal. The others must decide "YES" or "NO".

-If 50% or more of the pirates say YES, the proposal passes and takes effect. NOTE, 50% is a pass!

-If less than 50% of the pirates say YES, then the pirate who made the proposal is thrown off board. The next guy in the front of the line will make a new proposal.

All of these pirates have the same priorities:
1) stay alive
2) get as much money as possible
3) see another pirate die

Priority 1 > 2 > 3. 1 is most important, 3 is least.

Basically, these priorities apply to how a pirate makes a proposal or votes.


Good luck, I made this problem sound a lot longer than it should. It's not that hard, and only requires logic. It's not a trick question. Please leave solutions in spoilers (type [spoiler.] "insert solution here" [/spoiler.]. Without the periods in the brackets xD).

[Flames]

#6. I have seen this :P

Spoiler

A will propose a 98 : 0 : 1 : 0 : 1 split, in other words A gets 98 coins, the C pirate gets 1 coin and D gets 1 coin.

Working backwards:

2 Pirates: D splits the coins 100 : 0 (giving himself all the gold). His vote (50%) is enough to ensure the deal.

3 Pirates: C splits the coins 99 : 0 : 1. E will accept this deal (getting just 1 coin), because he knows that if he rejects the deal there will be only two pirates left, and he gets nothing.

4 Pirates: B splits the coins 99 : 0 : 1 : 0. By the same reasoning as before, D will support this deal. B would not waste a spare coin on C, because C knows that if he rejects the proposal, he will pocket 99 coins once B is thrown overboard. B would also not give a coin to E, because E knows that if he rejects the proposal, he will receive a coin from C in the next round anyway.

5 Pirates: A splits the coins 98 : 0 : 1 : 0 : 1. By offering a gold coin to C (who would otherwise get nothing) he is assured of a deal.

Note: In the final deal A would not give a coin to B, who knows he can pocket 99 coins if he votes against A's proposal and A goes overboard. Likewise, A would not give a coin to D, because D knows that if he votes against the proposal, A will be voted overboard and B will propose to offer D the same single coin as A. All else equal, D would rather see A go overboard and collect his one coin from B.

More questions
#7(easy)
The houses of a row are numbered consecutively from 1 to 49. Show that there is a value of x such that the sum of the numbers of the houses preceding the house numbered x is equal to the sum of the numbers of the houses following it. Find this value of x.
#8(easy)
A ladder has rungs 25 cm apart. The rungs decrease uniformly in length from 45 cm at the bottom to 25 cm at the top.If the top and bottom rungs are 2.5 m apart, what is the length of the wood required for the rungs ?

[jamz]

nb. If you're struggling to see the black-on-grey latex, click on "Lite (Archive) Mode" in yellow at the bottom of the page - it's black-on-white.

[Roflcopter]

#7

Spoiler

x = 35. Found by putting 1+2+...+x-1 = x(x-1)/2 = 49*50/2 - x(x+1)/2 = x+1 + x+2 + ... +49.

#8

Spoiler

There are 250/25+1 = 11 rungs. For the rung length numbering from the bottom, we get L(n) = 45 - (n-1)k with L(11) = 45 - 10k = 25 which implies k=2. So the length of wood required for rungs is 385cm by summing L(j) for j=1..11 (can be done by arithmetic progressions).

[Flames]

kk gj

#9[difficult]
No three positive integers a, b, and c can satisfy the equation a^n + b^n = c^ n for any integer value of n greater than two. Give a proof to this theorem
[troll]

[Roflcopter]

#9[difficult]
No three positive integers a, b, and c can satisfy the equation a^n + b^n = c^ n for any integer value of n greater than two. Give a proof to this theorem
[troll]

I doubt I can do Fermat's Thm but I can get a little way. If n=uv then (a^u)^v + (b^u)^v = (c^u)^v so there would be a solution to the case with n=v. Therefore we only need to prove for n an odd prime or 4. (This is a well-known idea and not originally mine.)

If gcd(a,b,c)>1 then a solution a' = a/g, b' = b/g, c' = c/g exists, hence we only have to prove a,b and c with gcd(a,b,c)=1. (Probably also not original.)

We need only prove for pairwise-coprime (a,b,c) since... if g := gcd(x,y) > 1 with x and y two different elements of (a,b,c) and z = the third element, then a^n + b^n = c^n (mod g) => z^n = 0 (mod g) => z=0 (z can't be any other zero divisor of g since then gcd(x,y,z)>1 which we proved above was a case we didn't need to consider). (Probably also not original.)

This means we only need to prove it for n=3, 4, 5, 7, 11, .. and pairwise coprime a, b and c.

---

#1 solution:

Spoiler

Without loss of generality let's take a ≤ b < c.

If a=2 then b^2 = c^2-4 = (c-2)(c+2). We can assume c>3 since the case c=3 leads to b^2 = 5. So (c-2)(c+2) contains at least two different prime factors p and q, so p|b^2 => p|b and q|b^2 => q|b, hence b is not prime.

If a>2 then a,b and c are all odd so a^2+b^2=0≠1=c^2 (mod 2).

Spoiler

To see why (c-2)(c+2) has two different prime factors we note c must be odd since c has to be a prime greater than 3. Then gcd(c-2, c+2) = gcd(4, c-2) = 1 since c-2 is odd.

#2 solution:

Spoiler

There exists an integer b with b > 1/(x'-x) => 1/b < x'-x (α).

Consider the interval (bx, bx'), with width b(x'-x) > 1 (using α). So there must be an integer a in (bx, bx'). So we see bx < a < bx' => x < a/b < x' as required.

[Mystered]

#6 :

Spoiler

Obviously, we would think that A has to give lots of money to B and C to stay alive, it is not accurate, and false. To get it right the problem has to be solved the other way round.

This problem was really difficult, but possible. I knew it was not possible to solve it exactly if we started with A so i thinked the other way round, so lets start :
- If their is only D and E left, D will propose 100 coins for him since it's 50% vote.

- If their is C, D and E left, C knows that D will give E 0 coins next round, so he have to give 1 coin to E so that E votes for him, and 99 for C.

- if Their is B, C, D and E, B also knows this, so he has to offer 1 coin to D so that he votes for him, cause otherwise D will get 0 coin, and 99 for B, because 50% votes is enough

- with all pirates, and A knows all the previous things, he will give 1 coin to C and 1 to E so that they get saved from B and get one more coin.

Solution :
- A : 98 coins
- B : 0 Coins
- C : 1 coin
- D : 0 coins
- E : 1 coin

The other solutions where for example D get 1 coin and not C is not valid since D would rather vote F2 to see A die and then get one coin from B.

ggs

[Roflcopter]

#10 (medium):
Prove that for n>4, F_n is composite if n is composite. F_n is the nth Fibonacci number (F_0 = 0, F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3, ..).

[RCJD]

Congrats, Sarath and Mystered. Your solutions to #6 were all 100% correct and they were surprisingly clear and concise!

Here comes #11:
A king receives 1000 wine bottles for his birthday. He knows that exactly one of them is poisoned, while the other 999 are all fine.

He wants to find out which bottle is the poisoned one. He decides to use 10 of his prisoners to use as testers (:

Basically, here are the rules:
-After drinking the poisoned wine, it could take up to 24 hours (1 day) before the poison kills whoever drank it.
-You can assume there is an infinite volume of wine in each bottle (no need to worry about running out). You can also assume drinking wine takes 0 time, for argument's sake.

That's it! So, using the 10 prisoners, what is the fastest way to find the poisoned bottle? There may be multiple solutions, but the best one I have lets me find the poisoned bottle in one day.

[Flames]

#11

Spoiler

First number the prisoners from 0 to 9. Then the wine bottles from 0 to 999.
Then lets make the poor prisoner 0 sample every odd numbered wine bottle.
After that group the bottles into blocks of 2. Prisoner 1 must sample all the odd numbered groups, group the bottles into group of 4 and get priosoner 2
to sample the odd numbered groups. Then group them into 8's and so on until the last prisoner gets bottles numbered from 512 to 999. After the poison takes action many prisoners will die. Decode their numbers as a binary digit in a 10bit number. This will locate the bad bottle.

[RCJD]

#11

Spoiler

First number the prisoners from 0 to 9. Then the wine bottles from 0 to 999.
Then lets make the poor prisoner 0 sample every odd numbered wine bottle.
After that group the bottles into blocks of 2. Prisoner 1 must sample all the odd numbered groups, group the bottles into group of 4 and get priosoner 2
to sample the odd numbered groups. Then group them into 8's and so on until the last prisoner gets bottles numbered from 512 to 999. After the poison takes action many prisoners will die. Decode their numbers as a binary digit in a 10bit number. This will locate the bad bottle.

:O
Haven't heard this one before. Pretty similar to the one I had in mind... neat though!

[D1551D3N7]

Spoiler

42 /:D