Math puzzles

Redundant · **#61**

Ok. Then take the integers modulo 6.

Then let f(0) = f(2) = f(4) = 0 and f(1) = f(3) = f(5) = 3

and g(0) = g(3) = 0 g(1) = g(4) = 4 g(2) = g(5) = 2

then f(0) + g(0)=0

f(1) + g(1) =3 + 4=1

f(2) + g(2) = 0 + 2 = 2

f(3) + g(3) = 3 + 0 = 3

f(4) + g(4) = 0 + 4 = 4

f(5) + g(5) = 3 + 2 = 5

This works, but is much easier than the case from R to R. That's why you'd want to specify the domain and codomain.

jts · **#62**

Redundant wrote:

jts wrote:

Shaddy wrote:

problem 2:

Shaddy, will you say a little bit more about your solution? It seems to me that a lot is riding on an ambiguity in "This" in the last sentence. You would agree, right, that when the Nth person recites his number, the maximum number of people who could have gotten their number wrong is "N", and that the number of people who have gotten their number right will be a binomial around N/2?

Looking at the other people, each person will know which equivalence class they are in (as they only fail to know the state of their own hat). Thus everyone will guess based on the same representative of that equivalence class, which differs from the true distribution in only finitely many places.

The actual sequence and the pre-selected member of that sequence's equivalence class differ in only finitely many places, by definition. But the ex ante probability that the first fellow will correctly state the color of his hat is fifty percent. (That is, if he's not in the shared portion of the sequence he's guessing, and the chance that he is in the shared portion is infinitesimally small.) And if the probability that the nth fellow will correctly state the color of his hat is fifty percent, than the probability that the n+1* fellow will correctly state the color of his hat is fifty percent. So by induction there's no limit to the number of people who are just guessing. Which is, under most interpretations of infinity I've seen, the same as saying an infinite number of people are guessing.

Think about an equivalent problem. Take a countably infinite sequence of 0's and 1's; you look at all the elements of the set except for one. If you choose any countably infinite sequence in the same equivalence class as the previous sequence, is the probability that (the hidden element in the first sequence is the same as the element in the same spot in the second sequence) equal to 1?

Shaddy · **#63**

actually, the chance that the first guy is in the shared portion is 1, as the shared portion is infinite and the unshared portion finite. same for everyone else.

jts · **#64**

Shaddy wrote:

actually, the chance that the first guy is in the shared portion is 1, as the shared portion is infinite and the unshared portion finite. same for everyone else.

Hmm, I don't think so. Knowing that a={a_1, a_2, ..., a_n, ...} and b are in the same equivalence class tells us that, for any n, there are are infinitely many i>n s.t. a_i=b_i, but it doesn't tell us anything for i<n. And we can ask, out of the entire equivalence class, what are the odds that we have chosen a sequence b s.t. for all i>1, b_i=a+i? For all i>10? For all i>1x10^100? For any n you choose, knowing b_i and aRb gives you no information about a_i for all i<n.

I'm sure you understand the problem better than I can and could explain it to me, but you're quite wrong to think that the probability that the first guy is in the shared portion of the sequences is 1.

Shaddy · **#65**

I'm tired. I apologize- I don't understand the argument you gave in your second post very well. But I think I can prove (or at least sketch a proof) that the probability that the first person's hat matches the hat in the memorized sequence is 1 as follows:

Choose a finite subset of N. The members of this set will be the indices which differ between our sequence of black and white hats and the memorized sequence. The probability that this subset contains any given natural number is 0, since we choose some number of numbers without replacement and the probability that any given number will be chosen is 0. Therefore the probability that the first hat will be different from the memorized sequence is 0.

I think this works, anyway..

edit: is the shared portion you are talking about the set of n such that for any i > n, a_i = b_i, or the set of all n such that a_n = b_n?

jts · **#66**

What I meant by "shared portion of the set" is aa' where a'={a_1, a_2, ... a_k} s.t. for all i>k, a_i=b_i (that is to say, aa'=bb'). If a and b are in the same equivalence class, such a subset exists by construction.

Consider a restricted subset of one of the equivalence classes to see which of our arguments you like better. Define A as the set of infinite sequences a={a_1, ..., a_n,... } s.t. for all i, a_i = {0, 1} and for all i>0, a_i = 0. Now, randomly choose two sequences, a and b contained in A. By construction, aRb. What is the probability that a_1=b_1?

The way I would do it is accept that for any i<100, exactly half of the elements of the set A have 0 as the i-th element, and half have 1. Therefore, for all i<100, aRb gives us no information about whether a_i=b_i.

By your suggested proof, we choose a finite subset of N (in this case, a finite subset of [1, 100]). Let's call it FS. The probability that this subset contains any given natural number is 0, obviously. (I think the most obviously way to formalize this statement is to say "consider the sequence {|FS|/i | i in N}. This sequence approaches zero.") Therefore, the probability that a_1=b_1 is one.

That last step of your proof is an obvious non sequitur. (Specifically, it's called the ecological fallacy.)

But of course, the chance that the sets a and b that our prisoners choose have a_i=b_i for all i>100 is infinitesimally small, because the actual equivalence classes they are dealing with are sets like A=V{A_i | i in n}, where A_i is defined s.t. the set in my example would be A_100. A_100 is only an infinitesimal subset of A.

Shaddy · **#67**

jts wrote:

What I meant by "shared portion of the set" is aa' where a'={a_1, a_2, ... a_k} s.t. for all i>k, a_i=b_i (that is to say, aa'=bb'). If a and b are in the same equivalence class, such a subset exists by construction.

Consider a restricted subset of one of the equivalence classes to see which of our arguments you like better. Define A as the set of infinite sequences a={a_1, ..., a_n,... } s.t. for all i, a_i = {0, 1} and for all i>0, a_i = 0. Now, randomly choose two sequences, a and b contained in A. By construction, aRb. What is the probability that a_1=b_1?

The way I would do it is accept that for any i<100, exactly half of the elements of the set A have 0 as the i-th element, and half have 1. Therefore, for all i<100, aRb gives us no information about whether a_i=b_i.

By your suggested proof, we choose a finite subset of N (in this case, a finite subset of [1, 100]). Let's call it FS. The probability that this subset contains any given natural number is 0, obviously. (I think the most obviously way to formalize this statement is to say "consider the sequence {|FS|/i | i in N}. This sequence approaches zero.") Therefore, the probability that a_1=b_1 is one.

That last step of your proof is an obvious non sequitur. (Specifically, it's called the ecological fallacy.)

But of course, the chance that the sets a and b that our prisoners choose have a_i=b_i for all i>100 is infinitesimally small, because the actual equivalence classes they are dealing with are sets like A=V{A_i | i in n}, where A_i is defined s.t. the set in my example would be A_100. A_100 is only an infinitesimal subset of A.

ah, you're right. it should be 1/2.

cyclops · **#68**

Gocat, introducing clocks, is hot. I believe the simplest solution is:
f(x) = x and g(x) = 0 with as domain and range the integers modulo 2, that is the group { 0 , 1} in which x + y = 0 for x = y and 1 otherwise.

flOvermind · **#69**

I think it's time for another puzzle

This one is a bit simpler, it doesn't really need advanced math, just a bit of logic thinking...

Puzzle 3
There is a set of at least 3 coins. One of them is false and has a slightly different weight. All the others weigh exactly the same. It is not known whether the false coin it is heavier or lighter.
You have a simple scale available. With it you can compare the weight of two sets of coins and determine which one is heavier.

You may use the scale at most 3 times. You have to find the false coin.

The question is: How many coins can there be for the task to have a solution, and what's the corresponding strategy?
(For example, there is obviously a solution for 3 coins. Find the two coins that weigh the same, the other one is the false one. That can be done using 3 comparisons. That means the answer is at least 3

).

This is more or less an open puzzle. In the original version, there was a number of coins given, but my solution can do slightly better than that number. I have no guarantee that there isn't an even better solution available.

robinz · **#70**

Quick thoughts on puzzle 3:

cyclops · **#71**

The original problem I posted before in GoDiscussion.
The problem was solved there for n =

.
It will surprise me if there is a solution for any bigger n.

cyclops · **#72**

In a two dimensional vectorspace the solution is easy.
Assume two indepent directions. The first (vector) function gives the component of any vector x along one direction. The other does likewise along the other direction.
Both functions are constant along their opposite direction and hence trivially periodic.
This is easily generalized to any multi-dimensional vectorspace.

Solution for an ordered field.
Let v be the square root of 2 and w the square root of 3, and F the field of all numbers a + bv + cw +dvw with a, b, c and d rational.
a, b, c and d are unique for any number in F.
Now from F to F define f(a +bv + cw + dvw) = a + bv and g(a +bv + cw + dvw) = cw + dvw.
f and g are easily seen to solve the problem.

It seems the real problem is for which fields the first problem cannot be solved.
I think it can't be solved in the reals. But the problem would be nice if I'm wrong. Please flovermind, give us a hint.

Edit: Well, Robinz thought about these lines before. But I doubt intuitively that there exists such ( countable ) basis for the reals as he assumes. But maybe the axiom of choice comes in here. And maybe the concept of an overcountable basis makes sense.

flOvermind · **#73**

cyclops wrote:

In a two dimensional vectorspace the solution is easy.

In any vectorspace with more than one dimension, the solution is easy

cyclops wrote:

It seems the real problem is for which fields the first problem cannot be solved.
I think it can't be solved in the reals. But the problem would be nice if I'm wrong. Please flovermind, give us a hint.

Edit: Well, Robinz thought about these lines before. But I doubt intuitively that there exists such ( countable ) basis for the reals as he assumes. But maybe the axiom of choice comes in here. And maybe the concept of an overcountable basis makes sense.

Robinz already found the correct solution:
http://www.lifein19x19.com/forum/viewto ... 820#p39820

Further elaboration:

flOvermind · **#74**

cyclops wrote:

The original problem I posted before in GoDiscussion.
The problem was solved there for n =

.
It will surprise me if there is a solution for any bigger n.

robinz · **#75**

Further thoughts:

OK, I've come up with solutions for 5,6 and 7 coins. What is pleasing is that they are essentially the same

So, take n=5 first. As before I'll label the coins alphabetically. First, I shall weigh A and B against C and D. If the two sides balance, we know E is the fake. If not, we weigh B and C against D and E - if both sides of this balance then A is the fake. Note, for future reference in the n=6 and n=7 cases, that it is impossible for them both to balance, as we know one (and only one) of the coins is fake.

So, assume neither weighing balanced. Then there are 4 possibilities, which I list in notation which I have just made up, but is hopefully easy-to-understand:
1) AB<CD, BC<DE
2) AB<CD, BC>DE
3) AB>CD, BC<DE
4) AB>CD, BC>DE

Now, if B were the fake, then we would get either scenario 1 or scenario 4, depending on whether B was lighter or heaver than the rest. The same if D were. If C were the fake, we would be in scenario 2 or 3. Thus, if 2 or 3 occurs, we already know C is the fake. And if 1 or 4 does, then we know the fake is one of B or D. So, for our third weighing, we simply take one of these and weigh it against one of the three known non-fakes - if it fails to balance, we've picked the fake, and if it balances then the fake must be the other one.

OK, that's n=5. But for n=6 we can simply ignore coin F for the time being, and do exactly the same thing. The thing to note is that, if F is the fake, then both of the first two weighings will balance, and this is only possible if F is the fake. Thus we know in only two weighings if the fake is F, and if it isn't we simply reason as for n=5.

For n=7, the only difference is that, if the first two weighings balance, the fake might be either F or G. But again we can figure out which by simply weighing one of them against any of A to E.

I can't be bothered to try to figure out how to do n=8 or higher for now - I suspect it'll be something similar to the above, but now involving sets of 3.

It's also worth pointing out that the problem certainly isn't soluble for n>27, as 27 (=3^3) is the maximum number of different possible outcomes of 3 weighings. Of course, this doesn't mean that it's possible for all n<28, just that it's certainly impossible for n>27.

robinz · **#76**

and a reply to cyclops about the other problem:

A basis certainly exists, if we assume the axiom of choice, as fl0vermind says. In fact, as he says, the argument seems to prove the existence of a countable basis. But I don't think it matters even if the basis turns out to be uncountable - all that is required is that one exists; then we take any two different elements of it and proceed as before.

Incidentally, the same argument can be used to produce any finite number of periodic functions whose sum is the identity function

EDIT: fl0vermind's post is a little confused in one respect - we don't need the axiom of choice to prove that the reals are a rational vector space; one simply checks that the axioms are true (which is trivial). The AC only comes in when actually constructing a basis. It is indeed one of the most useful consequences of the AC (it's probably even equivalent, although I'm not sure about this) that every vector space has a basis

cyclops · **#77**

flOvermind wrote:

...........
B is countably infinite by construction. The elements are linearly independent by construction. And seen as vector space over the rationals, the reals must be countably-infinite-dimensional because R and Q^N are the same size. Therefore, B is a basis.
.........

Nice! I'm almost convinced. But from R and Q^N are the same size I wouldn't dare to conclude that R and L(B) are equal. After all the set of integers and the set of rationals are also the same size but unequal. Also I'm not sure the uniqueness of the representation survives the limit.

Redundant · **#78**

flOvermind wrote:

cyclops wrote:

In a two dimensional vectorspace the solution is easy.

In any vectorspace with more than one dimension, the solution is easy

cyclops wrote:

It seems the real problem is for which fields the first problem cannot be solved.
I think it can't be solved in the reals. But the problem would be nice if I'm wrong. Please flovermind, give us a hint.

Edit: Well, Robinz thought about these lines before. But I doubt intuitively that there exists such ( countable ) basis for the reals as he assumes. But maybe the axiom of choice comes in here. And maybe the concept of an overcountable basis makes sense.

Robinz already found the correct solution:
http://www.lifein19x19.com/forum/viewto ... 820#p39820

Further elaboration:

This is very much not true that the basis is countable. Then we'd have R, an uncountable set, written as linear combinations of a countable set with coefficients from a countable set. Since linear combinations are finite, the set of all linear combinations is countable.

The flaw here is that you cannot get a basis just by taking the limit of independent sets as the number of elements goes to infinity. You need the full strength of Zorn's Lemma here. It turns out that every vector space having a basis is equivalent to the axiom of choice.

flOvermind · **#79**

Redundant wrote:

This is very much not true that the basis is countable. Then we'd have R, an uncountable set, written as linear combinations of a countable set with coefficients from a countable set. Since linear combinations are finite, the set of all linear combinations is countable.

I'm not sure if my proof is without flaws, but I am pretty sure that the basis R/Q is countable.

The linear combinations are not finite. You have a linear combination of countably-infinite elements, and each element can be choosen from a countably-infinite set. That's aleph0^aleph0 combinations, and that turns out to be the equal to c, the cardinality of the reals.

Another example: Q^N is a countably-infinite-dimensional vector space. But the cardinality of Q^N is certainly not countable.
Or the other way round: If the R/Q would be uncountably-dimensional, it would have to have the same cardinality than Q^R, the functions from the reals to the rationals...

Redundant wrote:

The flaw here is that you cannot get a basis just by taking the limit of independent sets as the number of elements goes to infinity. You need the full strength of Zorn's Lemma here.

I'm not taking the limit of sets, I'm constructing an infinite sequence. Perhaps my notation is a bit misleading. In my notation, B is a sequence, and B_i is a prefix of the sequence (a vector). Turning that around, the sequence is the limit of the prefix vectors. If you prefer, you can forget about the limit and just read the whole thing as a recursive definition of a sequence, where each element depends on all elements before it.

What I did with that was construct a base of a sub-space. That follows directly from the construction. The remaining question is whether it is a proper sub-space, or if this sub-space is identical to the whole vector space. And that is easily shown using the dimension...

I honestly don't see a flaw in that argument...

Redundant wrote:

It turns out that every vector space having a basis is equivalent to the axiom of choice.

Yes, and that's certainly a lot harder to proove. But that's more than we need for the task at hand

Redundant · **#80**

Linear combinations are taken of finitely many elements. If there is a countable basis of R over Q, then the set of all linear combinations of these basis elements is countable.

Let B be a countable basis of R over Q. Let C^n be the set of all linear combinations of n basis elements and n elements of Q. This is countable as we can biject it to B x Q x B x Q ... n times. The finite cartesian product of countable sets is countable.

Then the set of all linear combinations of basis elements with coefficients from Q is the union of C^n over all natural n. This is the countable union of countable sets, and thus countable.

There is a surjection from the union of all C^n to R by just evaluating the linear combinations. Thus R is countable. Contradiction.

Math puzzles

Who is online