/sci/ - Science & Math

[Anonymous No.6241552]

Can /sci/ actually do some fun/creative math problems, and not only talk about it like a bunch of post-modernists?

Here's a problem I invented for you. It's not that difficult but it requires a little bit of thought. If one of you presents a correct solution (I'll post a solution later), I'll be a bit more impressed:

Captain Hook and his p pirates have come across a treasure with N gold coins and obviously squabble about how the coins should be shared. Fortunately, there is a law of the sea saying that the captain may choose r <= p treasure chests to evenly distribute the coins in. The captain may keep the remaining coins at this stage.

Then the p pirates are divided evenly over the chests, so that no chest has more than one extra pirate than any other chest. The pirates then evenly split the coins in each chest, and the captain may also retain what remains from the division at this stage.

Prove that the captain can never get more than p-1 gold coins.

[Anonymous No.6241562]

If I followed you right,

Given 2 pirates and 7 coins,
r = 2 chests

3 coins in each chest, captain keeps 1.
Each chest evenly splits into 1 coin each, with the captain getting the remainder (1 each).

Each pirate has 2 coins and the captain has 3.
3 > 2-1

The conjecture is false

[Anonymous No.6241574]

>>6241562
I should improve the writing, in your situation there are 2 pirates and 2 chests, so each chest gets 1 pirate. Then those pirates get the whole share in each chest, so the captain only gets the one gold coin from the first division.

[Anonymous No.6241578]

>>6241574
Oh, I see. Nevermind then.

[Anonymous No.6241582]

>>6241574
Both extreme cases r = 1 and r = p end up with the captain getting only a single remainder - there might be a smarter strategy for the captain to choose something in between... though it's not necessary to solve the problem.

[Anonymous No.6241608]

notation:
p=pirates
N=gold
r=chests
q gold per chest
euclidian division of N by r:
N=r*q+s, s<r (the captain gets s coins at this stage), the rest is divided in r chests, with q coins in each one.

Now, how are the pirates spread amongst the chests?
let t be the minimum number of pirates sharing a chest.
Then there is either t or t+1 pirates on a chest. We can then write the division of p by r in the following form:
p=r*t+u, u<r.
let t_i be the number of pirates at the chest i.
let's assume that t1=...tu=t+1, t_u+1...tr=t.


in the chests 1 to u, the captain can get a total of u*(q-(t+1)*v) (u times the remaining gold that wasn't shared in each chest.)

in the chests u+1 to r, he can get a total of (r-u)*(q-t*w) ((r-u) times the remaining gold that wasn't shared in each chest).

this means that, adding the coins gotten from the three steps, we get:
Total=s+u*(q-(t+1)*v) + (r-u)*(q-t*w)
now, from the euclidian divisions, we know that: Total<= s+ u*t + (r-u)*(t-1) = s+r(t-1)+u=s+p-r.
And as s<r, s+p-r<p.
Therefore, the captain can't get more than p-1 coins.

[Anonymous No.6241626]

>>6241608
Good job anon. Count yourself amongst those who actually have at least some degree of creative intelligence.

The solution I originally wrote is a bit shorter and uses less notation, but uses the same observations:

Let p = ar + b (where r <= p) with b >= 0 minimum, there would then be r-b chests with a pirates and b with a + 1 pirates. The maximum earnings per chest with a pirates get a-1 coins and a+1-1 = a for them with a+1 pirates, giving the total maximum earnings for second stage

(a-1) (r-b) = ar + ab-ab-r + b + ab = (a-1) r + b = p-r

The maximum earnings from the first stage is, of course, r-1, and you can see that the total is p-r+r-1 = p-1 which proves the claim.

[Anonymous No.6241627]

>>6241626
(google translate fucked up the expression, I wrote the problem in Swedish originally, it should be):

(a-1)(r-b)+ab=ar-ab-r+b+ab=(a-1)r+b=p-r

[Anonymous No.6241631]

>>6241626
moar

[Anonymous No.6241636]

Is it possible to place 2013 different positive integers around a circle so that every consecutive pair, the ratio of the larger to the smaller is a prime?

[Anonymous No.6241642]

>>6241631
Sure. This one's harder. It's a problem solved in 1890 or something but I independently thought about it and its solution in 2009. You might be able to google a solution, I don't know.

A k-regular graph is a graph where each node has degree k. A perfect matching is a set of node pairs such that each pair have an edge, and such that all pairs are mutually disjunct.

Prove that a 3-regular graph always has a perfect matching.

[Anonymous No.6241646]

>>6241636
OP here, let me think about this one for a little, anon, it seems interesting.

[Anonymous No.6241649]

>>6241636
By consecutive, do you mean that they have to be in order around the circle? Or each pair next to one another?

[Anonymous No.6241651]

>>6241626
thank you sir, psistar is always glad to have fun with maths!
I gotta sleep, but I got one too:
imagine your have 2n+1 cows.

You can put aside any cow you want, you will always be able to divide the remaining 2n cows in two groups of n cows such as both groups of cows have the same total weight.

Prove that all the cows have the same weight!

[Anonymous No.6241661]

>>6241649
adjacent numbers around a circle

[Anonymous No.6241681]

>>6241636
OP here again, no, it's impossible. Proof: Start at any integer x = p1p2p3...pn. Taking a step in either direction of the circle entails multiplying or dividing with another prime factor. Let's imagine we do this process (correctly) and see what happens when the integers meet at the other end.

At this point the meeting numbers must have a number of prime factors with opposite the parity of n (so if n is odd, they have an even number of prime factors and vice versa). So the meeting numbers have the same parity. But this is impossible because one must divide the other, and one must have precisely 1 more prime factor than the other to hold.

Is this proof sound?

[Anonymous No.6241696]

Easy but fun:

At a party with five couples, no person checks hands with his or her spouse. Of the number people than than the host, no two shake hands with the same number of people.With how many people does the hostess shake hand?

[Anonymous No.6241699]

>>6241681
seems so

[Anonymous No.6241700]

>>6241696
>Of the number people than than the host
Should be of the nine people other than the host

[Anonymous No.6241722]

>>6241700
can someone shake 0 people's hands?

[Anonymous No.6241750]

>>6241696
4 and for n couples it will be n-1

[Anonymous No.6241891]

>>6241696
Is it !5?

Put ! Before 5 to avoid ambiguity