## Math and Logic Puzzles: Redux

This forum is for playing games other than Mafia and Mafia variants.
Mitillos
Mafia Scum Joined: August 23, 2012
Pronoun: He
Start with a specific permutation. If all the characters in the string of length n are distinct, there are (n choose 2) possible inversions to perform, and therefore (n choose 2) neighbours to the corresponding vertex.

On the other hand, if any two characters in the permutation are the same, inverting the substring starting and ending with these characters is the same as inverting the substring between these two characters. Therefore, each pair of copies of characters reduces the number of distinct permutations that can be created by inversion (and therefore the number of neighbouring vertices) by 1.
Note that there are two degenerate cases: If two copies of the same character are consecutive or have a third arbitrary character between them, then the corresponding substring between these two copies is too short to be inverted; once again such an inversion can be ignored when counting the degree of a vertex.

Since every vertex corresponds to a permutation of the same collection of characters, the number of pairs of copies of characters, k, is the same for every vertex. Then, the degree of every vertex is (n choose 2) - k, and the graph is regular.

I'm sleepy, so I hope I didn't mess the reasoning up. I also can't think of any interesting problems right now, so someone else can ask something, instead.
You don't have ambiguity; you have options.

Mitillos
Mafia Scum Joined: August 23, 2012
Pronoun: He
Answer 1: 25. Product of bottom numbers minus sum of top numbers.
Answer 2: 11. Bottom left number + 3.
Answer 3: 5. 23 - 2 * top left number.
Answer 4: 17. 2 * Top right number + 5.
Answer 5: 5. 15 - 2 * bottom right number.
Answer 6: 9. Sum of top numbers, multiplied by π, divided by bottom right number, and rounded down.
You don't have ambiguity; you have options.

Mitillos
Mafia Scum Joined: August 23, 2012
Pronoun: He
I think it can be done if we split the proof up into odd and even perfect numbers.

1) Let n be an odd perfect number with k divisors s_1 < s_2 < ... < s_k that is refactorable. Then n = s_1 + s_2 + ... + s_{k - 1} and n = ak for some integer a. Since n is odd, a and k have to be odd, and so do all s_i. But if k is odd, k - 1 is even. An even sum of odd integers is even, so we have that n is even, contradicting the hypothesis.

2) Let n be an even perfect number. Then n is of the form (2^k - 1)2^{k - 1} with 2^k - 1 prime, and n has 2k divisors. Observe that since 2^k - 1 is prime, so is k. Therefore, if 2k divides n = (2^k - 1)2^{k - 1}, then either k = 2, or k = 2^k - 1 (the only prime divisors of n). If k = 2, n = 6, which is not refactorable, and there is no prime k > 1 so that k = 2^k - 1.
You don't have ambiguity; you have options.

Mitillos
Mafia Scum Joined: August 23, 2012
Pronoun: He
Spoiler: Attempt
Let a_k be the number of patterns for k spikes, and b_k be the number of patterns for k spikes so that the last marble is red. Then we have: a_k = 2a_{k - 1} + b_{k - 1}, where b_j = a_j - a_{j - 1}.

Explanation for a_k: For every pattern for k - 1 spikes, we can colour the top of the kth spike green, and the last marble either green or red. If we colour the top of the kth spike red, the penultimate bottom marble and the last one both have to be red.

Explanation for b_j: The number of patterns which end in red is equal to the total number of patterns, minus the ones which end in green, i.e. the ones in which the last top and bottom marbles are green. The colours of all the previous marbles in such a pattern are therefore not restricted by the jth top marble, hence there are a_{j - 1} of them.

Simplifying the expression we get a_k = 3 * a_{k - 1} - a_{k - 2}, with a_0 = 1 and a_1 = 2. Recall that the Fibonacci sequence goes f_j = f_{j - 1} + f_{j - 2}, and usually starts with f_0 = 1, f_1 = 1, and therefore has f_2 = 2. Then f_j = 2f_{j - 2} + f_{j - 3} = 2f_{j - 2} + f_{j - 2} - f_{j - 4} = 3f_{j - 2} - f_{j - 4}. In other words, a_k matches exactly f_{2k}, so the number of patterns for n spikes is the (2n)th Fibonacci number.
You don't have ambiguity; you have options.

Mitillos
Mafia Scum Joined: August 23, 2012
Pronoun: He
Oh, yeah, I was counting bottom marbles, not top marbles. Mea culpa.
You don't have ambiguity; you have options.

Mitillos
Mafia Scum Joined: August 23, 2012
Pronoun: He
Do the factors on the two sides have to be the same, or can you have different factors giving you the same product?
You don't have ambiguity; you have options.

Mitillos
Mafia Scum Joined: August 23, 2012
Pronoun: He
Yeah, that was my point, in that 3, m, and m+1 potentially need not be consecutive. :Þ
You don't have ambiguity; you have options.

Mitillos
Mafia Scum Joined: August 23, 2012
Pronoun: He
1/2 + 1/3 + 1/9 = 17/18
You don't have ambiguity; you have options.

Mitillos
Mafia Scum Joined: August 23, 2012
Pronoun: He
Lend the dead man a camel.
You don't have ambiguity; you have options.

Mitillos
Mafia Scum Joined: August 23, 2012
Pronoun: He
Since you insist: You can't. By the time the will takes effect, the trader is dead. It is impossible to change the number of camels, assuming you have provided all pertinent information, thus at least one camel will have to be chopped up.
If we allow silly solutions like lending a dead man a camel, he now has 18 camels, which can be divided as you have requested. The sum I gave shows that one camel will be left over, which can then be returned to the lender.
You don't have ambiguity; you have options.

Mitillos
Mafia Scum Joined: August 23, 2012
Pronoun: He
In post 102, vizIIsto wrote:You don't need to 'lend a camel' to solve it, but adding an extra camel is how you will be able to divide the 17 camels fair and square.

This is extremely incorrect. The only way to divide the 17 camels "fair and square" is to give each of the sons the amount stipulated in the will, including part-camels.
To see why this is true, consider a similar scenario, where the father leaves one sixth of his camels to each of his three sons and dictates that the remainder are to be released. Let's say he happens to have 18 camels. Normally, this would mean that each son gets 3 camels, with 9 left-over and released. If we accept the idea of adding camels and then removing them, we could add another 18 camels for a total of 36, give each son 6 camels (twice what the will states), and then return the remaining 18 camels to wherever we got them from, leaving no released camels. This is a ridiculous way to do a will, given that it results in going in opposition to what the deceased stated their intent to be.
You don't have ambiguity; you have options.

[ + ]