Math and Logic Puzzles: Redux

[Mitillos]

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.

[Mitillos]

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.

[Mitillos]

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.

[Mitillos]

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.

[Mitillos]

Oh, yeah, I was counting bottom marbles, not top marbles. Mea culpa.

[Mitillos]

Do the factors on the two sides have to be the same, or can you have different factors giving you the same product?

[Mitillos]

Yeah, that was my point, in that 3, m, and m+1 potentially need not be consecutive. :Þ

[Mitillos]

1/2 + 1/3 + 1/9 = 17/18

[Mitillos]

Lend the dead man a camel.

[Mitillos]

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.

[Mitillos]

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.

[Mitillos]

Spoiler:

4	1	3	7	5	2	8	6	9
8	5	6	1	4	9	3	2	7
7	2	9	6	8	3	1	5	4
5	8	2	3	6	4	9	7	1
9	3	4	2	1	7	6	8	5
1	6	7	5	9	8	4	3	2
3	4	8	9	2	5	7	1	6
2	7	1	4	3	6	5	9	8
6	9	5	8	7	1	2	4	3

Edit:

Spoiler: @Scigatt

I don't think your proof works. You appear to be proving some kind of converse to the statement? You end up with the assertion that the lines drawn are of equal length, but that's given by the problem statement.

[Mitillos]

Edit: Thinking about it some more.

Edit2: Yeah, I missed a couple of critical sentences there. It works.

[Mitillos]

Spoiler:

6	3	2	7	8	5	1	9	4
5	7	4	9	6	1	2	3	8
9	1	8	4	3	2	5	6	7
7	6	5	8	4	9	3	1	2
4	8	1	5	2	3	9	7	6
3	2	9	6	1	7	8	4	5
2	9	7	1	5	6	4	8	3
8	5	6	3	9	4	7	2	1
1	4	3	2	7	8	6	5	9

[Mitillos]

Spoiler:

[Mitillos]

Spoiler:

Any collection of 3 rows (resp. columns) must have each number 1 to 9 exactly three times. The windows account for one copy of each number each. Since each of the green and blue (resp. pink and yellow) sets combine with two windows to make three rows (resp. columns), each of those sets must account for a copy of each number. Thus we have 8 sets (4 windows, 4 colours) each accounting for one copy of each number. The remaining (white) cells must account for the ninth and final copy of each number.

[Mitillos]

Spoiler: Solution for e trillion's problem

Let's see if this works: Take the unit square [0, 1] X [0, 1], which has area 1. The points corresponding to floor(x/y) being even within this square are as follows:
- Everything to the left (or above) of y = x.
- Everything between x = 2y and x = 3y.
- Everything between x = 4y and x = 5y.
etc., forming triangles between the lines x = 2ky and x = (2k + 1)y, for positive integers k.
These triangles will have an apex at (0, 0) and the corresponding base on the line x = 1. The end-points of the base will be at 1/(2k) and 1/(2k + 1) respectively. In other words, the area of the kth triangle will be (1/2) * [1/(2k) - 1/(2k + 1)]. Note that the first triangle (left of y = x) is not included in this calculation and has area 1/2.
Therefore, the total area of the triangles will be 1/2 + Sum (k = 1 to infinity) (1/2) * [1/(2k) - 1/(2k + 1)] = (1/2) * [2 + Sum (n = 1 to infinity) [(-1)^n]/n]. This sum is the negative of the alternating harmonic series, so the area comes to (1/2) * (2 - ln 2) = 1 - (ln 2)/2, which is the probability requested and approximately 65.34%.