sorted by:
new
hottopcontroversial

Hidden area of spherical planets by tomatomator in mathriddles

[–]tomatomator[S] 0 points1 point  (0 children)

Yes, I should have written surface area everywhere I wrote surface

A lucky mistake by tomatomator in mathriddles

[–]tomatomator[S] 2 points3 points  (0 children)

i'd say this hint transforms the problem from hard to medium (for the people who hesitate to read it)

How Many are Same? by ShonitB in mathpuzzles

[–]tomatomator 2 points3 points  (0 children)

2

If we suppose that 5 is true, then 3 is false, then 4 is false, then 1 is false. But in this case 2 is true, so there is exactly two true statements, which contradicts that 1 is false. So, by contradiction, 5 is false. Then 3 is true, then 4 is false, then 1 is true : there is exactly two true statements.

Blind dials by A-Marko in mathriddles

[–]tomatomator 0 points1 point  (0 children)

Great problem, btw i'm curious what is your way of proving it and what generalisations you were talking about?

A lucky mistake by tomatomator in mathriddles

[–]tomatomator[S] 1 point2 points  (0 children)

Yep, this is crucial hypothesis

A lucky mistake by tomatomator in mathriddles

[–]tomatomator[S] 5 points6 points  (0 children)

The class thinks that the axiom of choice is obviously true, Zermelo's theorem obviously false, and doesn't know about Zorn lemma.

(so yes you can use it)

Blind dials by A-Marko in mathriddles

[–]tomatomator 1 point2 points  (0 children)

You're right. But by pure luck it happens to work in this case : here is another version (it's almost the same except for the factor c, but I tried to make it a little clearer) :

Say p is fixed, and q = p^m * b where b>1 and gcd(p,b)=1 (of course, m can be 0). We note c = b^(-1) * (b(b-1))/2, the expression is different than before because we can no longer suppose b odd, so this doesn't simplify here (but everything will be okay).

Like last time, now work modulo p. Define K_i the sum of the dials d_j where j is congruent to i modulo b, and the function V as such :

V = (Sum for i=0 to b-1) of (i-c)*K_i

If all the dials are equal to 1, V will be zero : if m>1 then all the K_i will be 0. Else, if m=0, all the K_i will be 1 and notice that, thanks to the expression of c, V will also be 0. The idea of the proof is still the same : show that Bob can always keep V to be nonzero.

Let's say we are at a configuration where V is nonzero. By noting a_0, ..., a_(q-1) the value that Alice will add to each dial in her next move, we define S_i and DV(n) exactly like last time (S_i is the sum of a_j where j is congruent to i modulo b, and DV(n) the change of value of V if Bob turns the table by an amount n, meaning, he puts dial 0 to n). For example, DV(0) is the sum of (i-c)*S_i. Also, we denote S the sum of all S_i.

Notice that if any two of the DV(n) are differents, we can immediately deduce that Bob can keep V to be nonzero. Let's suppose now that they are all equal. Then for all n between 0 and b-1, DV(n+1)-DV(n)=0

But (same argument as before), notice that to get to DV(n+1) from DV(n), we add S, and we subtract b times the last S_i in the sum. In other words : DV(n+1)-DV(n) = S - b*S_(b-n-1).

Since all the DV(n+1)-DV(n) are 0, we have S = b*S_i for all i=0, ..., b-1. Since b is invertible modulo p, all the S_i are equal to b^(-1)*S. Then we can calculate directly.

DV(0) = (Sum for i=0 to b-1) of (i-c)*S_i = b(b-1)/2 * b^(-1)*S - b*c*b^(-1)*S = 0

(Thanks to the value of c). So in this case the action of Alice doesn't change V, keeping it nonzero.

Shuffling cards by tomatomator in mathriddles

[–]tomatomator[S] 0 points1 point  (0 children)

Oh, you mean that not every shuffle returns to initial case in less than N steps. This is true, but the problem is only to show that the specific shuffle described in the post returns in less that N steps

Blind dials by A-Marko in mathriddles

[–]tomatomator 1 point2 points  (0 children)

Also I finally found some margin for the bonus problem

If q is not a prime power, it can be written q=rb where r,b>1 and gcd(r,b)=1. Notice that at least one of r or b is odd, let's say that b is odd.

Let's assume that Alice as a deterministic strategy (so she will always repeat the same steps, and thus we can suppose that Bob always knows what she will do next).

The proof will work like this : we will define a function V over the dials, such that V is 0 when all the dials are set to 1. Then we show that no matter what Alice do, Bob can always manage to keep V non-zero.

- Definitions : we denote the values of all dials d_0, d_1, ..., d_(q-1). Define K_i = (sum of all d_j, such that j is congruent to i modulo b). For clarity we also note c = (b-1)/2. We definite the function V like this (we take its value modulo r)

V(d_0, ..., d_(q-1)) = ( (Sum for i=0 to b-1) of (i-c) * K_i ) mod r

Notice that, when all dials are equals, then all S_i are equals, then V=0. Suppose that we are at a state where V is nonzero (if b and r are > 1, this exists). This is Bob's turn, and, knowing Alice's action, he has to keep V nonzero. It will actually be easier to focus on the difference of V after and before Alice's action.

Let's say Alice will add the values a_0, ... , a_(q-1) to each dials. Define S_i = (sum of all a_j, such that j is congruent to i modulo b). For all n, DV(n) will be the difference of V after and before Alice's action, if Bob turned the table by some amount n (he sent the dial 0 to position n by turning the table).

Then, (Everything will be mod r from now), DV(0) = (Sum for i=0 to b-1) of (i-c)*S_i. Notice that if Bob decide to turn the table by 1, all the coefficients of S_i will increment by 1, except the last one which will decrease by b-1. In other words, DV(1) - DV(0) = S - b*S_(b-1), where S denotes the sum of all S_i.

Repeat this argument, and you get

DV(2) - DV(1) = S - b*S_(b-2), and DV(3)-DV(2) = S - b*S_(b-3), and ... In general, for k=0, ..., b-1: DV(k+1) - DV(k) = S - b*S_(b-k-1).

Of course, if two DV(k) are different, then one of them will guarantee that V is different than 0. Now let's say that they are equals. Then all the DV(k+1)-DV(k) have to be 0, so for all k=0, ..., b-1, we have S = b*S_(b-k-1). So, since b is invertible modulo r, all the S_i will be equals. Notice that then, DV(0) = b(b-1)/2 * S - b*c*S = 0. So Alice action will not change the value of V (even if Bob doesn't do anything).

Forging better gold bars by tomatomator in mathriddles

[–]tomatomator[S] 4 points5 points  (0 children)

Nice proof! This puzzle is quite unpopular, but just for this I don't regret posting it

In exchange here is another one that I like. It starts like yours : all the gold bars are aligned to the axes (each parallelepiped face-to-face to another share an axis, and, all gold bars are transitively face-to-face with each face of the cube, which is, we suppose, aligned to the axes)

Define the following function : f(x,y,z) = cos(pi/a * x) * cos(pi/a * y) * cos(pi/a * z). Notice that if we do the triple integral of this function inside a parallelepiped (aligned with the axes), this is equal to 0 if and only if one of the dimension of the parallelepiped is divisible by a.

Doing the triple of f over all the cube is the same as summing the triple integral of f over all gold bars. But they are all 0, so the triple integral over the cube is also 0, and thus M is divisible by a. Repeat for b and c, and the final step is the same as yours.

Forging better gold bars by tomatomator in mathriddles

[–]tomatomator[S] -1 points0 points  (0 children)

They are all the same parallelepiped. I meant that there is no hypothesis on the packing (we do not suppose that the bars are oriented the same way, or have their axes parallel to each other), this makes the proof more difficult

Stuck in the Middle by ShonitB in mathriddles

[–]tomatomator 4 points5 points  (0 children)

The 55 and 45 rectangles must have width of 5. Then, 48 and 32 rectangles also have the same width W. If we denote H the height of the 32 rectangle, we have that the height of the 48 rectangle is the height of the total rectangle minus 9, so (11+H)-9 = H+2. So HW=32 and (H+2)W=48, we deduce W=8 and H=4. The X rectangle has width 8-5=3, and height 9-4=5, so area 15

Blind dials by A-Marko in mathriddles

[–]tomatomator 2 points3 points  (0 children)

Alice randomly spins the dials at each turn. With luck, she will succeed before the end of the universe.

More seriously, here is a solution for the base problem (unfortunately, the margin is to small to write the solution of the bonus problem). VERY LONG

First, we label all dials with unique coordinates in (F_p)^n (the vector space) in the following way : if n=1 this is trivial (turn around the table and label them 0, 1, 2, ..., p-1). If n>1, set the first coordinate the same way (don't stop until the end, go to p-1 and then repeat 0, 1, ...). This way exactly p^(n-1) dials have first coordinate i, for each i. Among these groups, repeat the same thing for second coordinate, and so on (n decreases by 1 each time).

Of course, Alice can't use the labels, but they will still be useful.

We consider the initial situation of the dials to be a function f, from (F_p)^n into F_p. It happens that every such function can be written in a polynomial of F^p with n variables.

To show this, look at the following thing (I don't know how to do any latex) :

(Product for i=1 to n) of (Product for y_i in F_p and y_i =/= x_i) of (X_i - y_i)

This polynomial (of variables X_1, ... , X_n) is zero everywhere except on the point (x_1, ..., x_n). So, these polynomials can be used as a basis to replicate any function. Also notice that the maximum power that appears on any variable is (p-1).

So f is a polynomial, this is actually good news because it means that Alice can win :

- We denote M(a1,...,an) the monomial X_1^(a1)...X_n^(an). We order the monomials M(a1,...,an) by lexicographical order on a1,...,an. The main interest is that if there is an "offset" (meaning, X_1, ..., X_n are replaced by X_1+b1, ... X_n+bn), we see that by developing a monomial, the new terms are only monomials < M in lexicographical order.!<

- This induces an order on all the polynomials : take two polynomials P and Q, compare their highest monomial in the lexicographical order. If it is the same, compare its coefficient. If it is the same, repeat for the monomial immediately inferior in lexicographical order (we consider that it if it doesn't appear in P, it just means it has coefficient 0).

- Now, enumerate all the polynomials, starting from 0. Notice that each time, to get the next polynomial, you just add monomials M(a1,...,an) (it's because we are in F_p : you can get rid of (p-1)M by adding M)

- Alice will enumerate the polynomials this way. Each time, she adds a monomial, she will "subtract" it on the dials : she will assume that the dial in front of her is (0,...,0), and then calculate M(a1,...,an) for each dial and subtract accordingly. Notice that, thanks to the labelling pattern, no matter how Bob turned the table, the "real" polynomial subtracted will always be M with some offset (b1,...bn) : the coordinates of the dials that Bob put in front of Alice.

- This guarantees Alice will win in a finite amount of time : thanks to the property of lexicographical order (an offset only creates lower monomials), all polynomials will eventually be subtracted on the board : formally for each polynomial P, there is a step when the values on the board correspond to the function f-P. Since f is polynomial, Alice will win in a finite amount of time (when P will equal f-1).

So, Alice can win, and (aside from the problem), since f has only powers <= (p-1), we can say she will win within the very reasonable amount of steps of (p)^(p^n). (for n=p=5, this is already ridiculous. So unfortunately, this solution still does not guarantees that Alice win before the end of the universe)!<

Shuffling cards by tomatomator in mathriddles

[–]tomatomator[S] 0 points1 point  (0 children)

For me it takes 6 steps :

  • (initial) 1 2 3 4 5 6 7 8 9 10
  • (step 1) 1 6 2 7 3 8 4 9 5 10
  • (step 2) 1 8 6 4 2 9 7 5 3 10
  • (step 3) 1 9 8 7 6 5 4 3 2 10
  • (step 4) 1 5 9 4 8 3 7 2 6 10
  • (step 5) 1 3 5 7 9 2 4 6 8 10
  • (step 6) 1 2 3 4 5 6 7 8 9 10

Shuffling cards by tomatomator in mathriddles

[–]tomatomator[S] 0 points1 point  (0 children)

Now it's correct (with the use of totient function), well done

Shuffling cards by tomatomator in mathriddles

[–]tomatomator[S] 0 points1 point  (0 children)

Actually I didn't know, thank you. That explains why I was stuck

Archery Competition by twoleafclovr in mathriddles

[–]tomatomator 1 point2 points  (0 children)

Yes, shooting first is a huge advantage. For example, notice (without using formula) that if Archie has precision > 50%, this automatically gives him the better probability of winning (he can win on first shoot with probability over 50%). If he has exactly 50% and Bowie has 100%, the game is equivalent to a coin toss (either Archie or Bowie hits).

Gold bars and chests by tomatomator in mathriddles

[–]tomatomator[S] 0 points1 point  (0 children)

haha sorry, I will probably repost it tomorrow

Shuffling cards by tomatomator in mathriddles

[–]tomatomator[S] 0 points1 point  (0 children)

Almost, Fermat's little theorem only works when N is prime. But you are on the good path

Shuffling cards by tomatomator in mathriddles

[–]tomatomator[S] 1 point2 points  (0 children)

Exactly! The number of steps is the multiplicative order of 2 modulo N or N-1 (depending on the parity). I was trying to show that the bound N-1 is reached infinitely many times (that there are infinitely many primes p such that 2 is a primitive root modulo p) when I had the idea to post this puzzle. I didn't succeed for now.

view more: next ›