Haven't had a problem for a while, so here goes.
Find all positive integers n with the following property: If you add the digits of n to obtain the number s and then you multiply s with the the digit reversal of s, you get n. In addition, prove that those are the only such positive integers with that property.
For example:
1729: 1+7+2+9=19
19*91=1729
It's not hard (at least in my opinion).
There are two useful facts about the solutions to that problem:
1) The number of digits in n increases exponentially with respect to the number of digits in the highest value of s seen so far. If n has 5 digits or more, there is no way for s to have enough digits to make the product large enough. Therefore, n has at most 4 digits, and s is at most 36.
2) s = n (mod 9) because it is the sum of the digits, and s^2 = n (mod 9) because the reversal has the same digits as s (and is thus the same mod 9). Hence s*(s-1) is a multiple of 9, and thus s = 0 or 1 (mod 9).
From here, we can just enumerate the possibilities:
s=1: n=1*1=1 (works)
s=9: n=9*9=81 (works)
s=10: n=10*01=1 (doesn't work)
s=18: n=18*81=1458 (works)
s=19: n=19*91=1729 (works)
s=27: n=27*72=1944 (doesn't work)
s=28: n=28*82=2296 (doesn't work)
s=36: n=36*63=2268 (doesn't work)
Therefore, the (only) solutions are 1, 81, 1458, and 1729.
I actually got the idea for this problem from a Wikipedia page (article about the number 1729). I even added an outline of the proof on that page.
Nitrodon, you basically got it right, although it is possible to prove that s cannot be 3 or more digits using mathematical induction.
Edit: Finishing off, if s has k digits, n has no more than 2k digits, so its digit sum is no more than 18k. But 18k has less than k digits for k>2. In other words, 18k < 10^(k-1).
k=3: 18(3)=54, 10^2=100
Suppose true for k=j. Then 18j < 10^(j-1)
18(j+1) < 18(10j) < (10)10^(j-1) = 10^j
So it is true for j+1. Therefore it is true for all k>2.
New problem: Prove that there cannot be an equilateral triangle on points with integer coordinates in the 2-dimensional plane.
Also, find a regular tetrahedron on points with integer coordinates in 3-dimensional space.
the first is easy. take any two integer coordinates, then calculate the position of the third. There are two possible positions, but both of them can't be integers because sin(60°) is not rational.
the tetrahedron can be constructed by placing any cube on integer coordinates, then using one of the two touching tetrahedrons inside.
I got this one from a book (this one), so anyone owning it is out.
Here's the original version:
Ten pirates found a treasure of 100 gold pieces and want to distribute the loot. The pirates have their own way of democracy and share by this algorithm: The wildest pirate makes a proposal of how to share, and all of them vote. Everyone including the proposing one votes for one. If at least 50% vote positive, the proposal is accepted and the loot distributed. If not, the pirat who came up with is thrown overboard, and the next wildest pirat makes his offer. Every pirate likes to see people walking the plank, but if in doubt, they prefer coins, because, well, you never know who's next to go overboard.
In a nutshell:
- 10 pirates
- 100 coins
- Wildest pirate offers how to distribute
- Everyone votes (once per proposal)
- 50%+ means loot is shared, else substract one pirate and repeat.
You may assume that each pirate is perfect with logic, and a very quick thinker. ;)
How is the loot going to be distributed and why?
If you've got that one, there's a considerable harder version with 500 pirates and 100 gold pieces. How is the loot going to be shared there?
Hmm, well if that is the case then isn't the wildest pirate going to get all of the coins in both problems?
If there are 2 pirates, the wildest will get them all because he can vote for himself giving him the needed 50%. If there are 3, then the wildest can propose to give himself all. And he will win because the least wildest won't get any anyways so will accept. This is then repeated.
I guess I must be misinterpreting something though because that wouldn't make it much of a problem.
The beginning is right, but well, lets say the above only holds true for pirates actually getting anything. If they don't get anything, they'll opt for seeing someone walk.
Joined: 3/6/2006
Posts: 15
Location: Santa Maria, RS, Brazil
Essentially, between getting X gold and walking N pirates and getting X gold and walking N + 1 pirates, the pirate will choose to get X gold and walk N + 1 pirates.
No.
A pirate will just never accept 0 gold without a very good reason.
The complete PI (pirate AI) would look like this I guess:
Am I going to walk the plank if I vote no? - Vote yes if true.
Am I getting anything at all? - Vote no if false.
Am I going to get a better option down the line and am sure that none of the options in between gets accepted? - Vote no if true.
Am I going to get the same option down the line? - Vote yes if true, hard coinage is better than vague speculation. (this one is only needed for the 500 pirates question)
In flagitious solution, the last priate would gladly make the third one walk for his insolence, even knowing he wouldn't get anything anyway.
Joined: 3/6/2006
Posts: 15
Location: Santa Maria, RS, Brazil
Gorash wrote:
A pirate will just never accept 0 gold without a very good reason.
What I meant in my post is that the primary objective of the pirate is to get as much gold as possible, and the secondary objective is walking the most pirates. So, for example, if any pirate has an option of getting 1 gold and walking no pirates, or getting 0 gold and walking 50135 pirates, he'll try to get 1 gold and walk no one.
So, a pirate will only accept 0 gold if he knows he can't get more.
flagitious wrote:
If there are 2 pirates, the wildest will get them all because he can vote for himself giving him the needed 50%. If there are 3, then the wildest can propose to give himself all. And he will win because the least wildest won't get any anyways so will accept. This is then repeated.
In the case with 2 pirates, that is right. With 3 pirates with the proposer proposing (100, 0, 0) will vote yes, the 2nd wildest will vote no, as he can get 100 if the first one walks, and the third one will vote no, as if he votes yes he gets 0 gold and 0 walks, and voting no he gets 0 gold and 1 walks.
Joined: 5/2/2006
Posts: 1020
Location: Boulder, CO
the best strategy would be for the third to last to offer 99-0-1 because he can secure the vote of the last this way.
this extends to 4 because the fourth because the fourth to last could offer 99-0-0-1 because the thirsd will vote against him no matter what (he can get 99 if 4th to last walks) but can get the votes of the last because the most he will get if the 4th to last walks is 1. (and one in the hand is better then vague speculation).
the case of 5 is the critical one. the 5th pirate needs 2 other votes, so he needs to offer 98-0-1-0-1, because the last again will accept, and the 3rd to last stands to get nothing should the 5th walk.
this pattern continues,
100-0
99-0-1
99-0-0-1
98-0-1-0-1
98-0-0-1-0-1
97-0-1-0-1-0-1
97-0-0-1-0-1-0-1
96-0-1-0-1-0-1-0-1
96-0-0-1-0-1-0-1-0-1
the best proposal for the most fearsome pirate.
Joined: 5/2/2006
Posts: 1020
Location: Boulder, CO
and for 500 pirates, the 200th weakest should offer himself 1 the next 2 0, and alternating after thatso that he gets 100 votes and survived (a simple extention of the 10 pirate example)
New problem: Prove that there cannot be an equilateral triangle on points with integer coordinates in the 2-dimensional plane.
Also, find a regular tetrahedron on points with integer coordinates in 3-dimensional space.
Tub wrote:
the first is easy. take any two integer coordinates, then calculate the position of the third. There are two possible positions, but both of them can't be integers because sin(60°) is not rational.
the tetrahedron can be constructed by placing any cube on integer coordinates, then using one of the two touching tetrahedrons inside.
Clarify. If (a,b) and (c,d) are the two points, what are the two positions for the third?
There is another proof of the fact as well, using the area of the triangle. Anyone else can try to solve it that way.
If there is more than one way for a pirate to distribute the coins, that still give him the same amount and guarantee acceptance of the proposal, shall we assume the proposing pirate chooses which proposal to use randomly, and that the other pirates know he will chose randomly?
Edit, should we also assume you cannot give fractions of coins? That seems obvious, but if the pirates are as smart as you claim they are, then they could propose to flip a coin to see who gets a coin (thus acting like fractions).
Joined: 5/2/2006
Posts: 1020
Location: Boulder, CO
all fractional coins would accomplish is making the solution for 10 pirates almost all for the first, 0 for the second, 0 for the third, and alternating the smallest allowable fraction for every other pirate after that.
flipping a coin to see who gets it is interesting however. this should make it possible for the first pirate to get 98 of the coins, as he will need to offer 4 of the pirates (who would otherwise get nothing) a coin flip chance if winning the coin.
the problem is that if you allow chance to be involved, you can offer a pirate ludicrously small fragment of a coin (on average) by saying that he would need to win many flips in a row in order to claim the coin.
The wildest one starts. He has one vote (his own), needs to get at least 5 more votes to stay alive. The least wild one is likely to vote against him because the more pirates die, the more he gets and he himself has no risk of dying. The second wildest pirate will probably vote for him because he fears he could be the next one to die.
So pirate 1 won't give anything to pirate 2 and probably also nothing to pirate 10.
How does he distribute the money so he gets 4 more votes to stay alive? Idk, this problem is too much for me. x_X
Edit: After thinking about it for a bit...
If there are 2 pirates (9 and 10), the least wildest (10) gets all the money or pirate 9 dies. So if there are 3 pirates (8, 9 and 10) and pirate 8 decides to give pirate 9 one coin, pirate 9 will vote for him because he gets more than nothing that way.
So for 2 pirates: 0 - 100
For 3 pirates: 99 - 1 - 0
Now if there are 4 pirates (7,8,9 and 10) pirate 10 will vote yes as long as he gets more than 0 coins. Pirate 9 needs more than 2. Pirate 8 more than 99. Pirate 7 needs 3 votes.
For 4 pirates: 97 - 0 - 2 - 1
5 pirates - 3 votes needed...
Brackets say how many votes needed
Bolded pirates will vote yes.
For 1 (1): xx - xx - xx - xx - xx - xx - xx - xx - xx - 100
For 2 (2): xx - xx - xx - xx - xx - xx - xx - xx - 00 - 100
For 3 (2): xx - xx - xx - xx - xx - xx - xx - 99 - 01 - 00
For 4 (3): xx - xx - xx - xx - xx - xx - 97 - 00 - 02 - 01
For 5 (3): xx - xx - xx - xx - xx - 97 - 00 - 01 - 00 - 02
For 6 (4): xx - xx - xx - xx - 96 - 00 - 01 - 02 - 01 - 00
For 7 (4): xx - xx - xx - 96 - 00 - 01 - 02 - 00 - 00 - 01
For 8 (5): xx - xx - 95 - 00 - 01 - 02 - 00 - 01 - 01 - 00
For 9 (5): xx - 95 - 00 - 01 - 02 - 00 - 01 - 00 - 00 - 01
For 0 (6): 94 - 00 - 01 - 02 - 00 - 01 - 00 - 01 - 01 - 00
Am I rite?
Yes, I haven't found a formula, but an algorithm.
Twelvepack got it exactly right. 96-0-1-0-1-0-1-0-1-0 is the correct distribution for 10 pirates.
For 500 you'll have to think a little bit further than that though.
And, as has been stated correctly, allowing split coins or vague percentage chances for a coin is stupid. Keep it integer.
Kuwaga: You're mistake is to assume the pirate who made the proposal is not allowed to vote. He gets to vote on his own proposal too!
I get it, so I've found the solution to a different problem. That's still something. :p
Actually the mistake I made was to assume that >50% votes are needed.
That reminds me of those countless times I got a worse grade just because I cannot read... It's so unfair. :X
