Wikipedia:Reference desk/Archives/Mathematics/2009 September 13

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

September 13

Path problem

Someone told me about this puzzle:

			o	o
		o	o	o	A
o	o	o	o	o	o	o
o	o	o	o	o	o	o
o	o	o	o	o	o	o
	B	o	o	o
		o	o

The object is to go from A to B, passing through all "o"'s but one. Not sure how to do it. Is it even possible? It seems like I can only miss out an even number of "o"'s. Professor M. Fiendish, Esq. 03:41, 13 September 2009 (UTC)

What are the movement rules? Algebraist 03:50, 13 September 2009 (UTC)

Only horizontally and vertically but not diagonally. Professor M. Fiendish, Esq. 04:06, 13 September 2009 (UTC)

Can an 'o' be traversed more than once? —Anonymous Dissident^Talk 04:39, 13 September 2009 (UTC)

No. Professor M. Fiendish, Esq. 04:52, 13 September 2009 (UTC)

Seems to be impossible. If we color the board with a checker pattern, any path must alternate between white and black squares. A and B are the same color so any path connecting them has to go through an odd number of 'o's. Rckrone (talk) 06:32, 13 September 2009 (UTC)

That's assuming you're not allowed to travel on the blank squares. Is that right? Otherwise it would be pretty easy. Rckrone (talk) 06:37, 13 September 2009 (UTC)

Oops, I checked the puzzle again and there were four rows of complete "o"'s.

			o	o
		o	o	o	A
o	o	o	o	o	o	o
o	o	o	o	o	o	o
o	o	o	o	o	o	o
o	o	o	o	o	o	o
	B	o	o	o
		o	o

Is it possible now? Professor M. Fiendish, Esq. 07:42, 13 September 2009 (UTC)

No. A and B are now on different colors, so any path has to go through an even number of 'o's, but now there are also an even number of 'o's on the board. Rckrone (talk) 08:04, 13 September 2009 (UTC)

Just as a point of interest, this is basically a graph theory problem. The board is a bipartite graph, and so for a pair of vertices A and B, the lengths of any two paths between A and B have to have the same parity. Rckrone (talk) 08:14, 13 September 2009 (UTC)

The parity argument fails if you're allowed to go through the same 'o' more than once. I assume that's something you forgot to include because it's pretty trivial otherwise. This kind of parity argument is very common in puzzles and recreational mathematics. If you wanted to pass through every o, just once, the parity argument fails and it turns out you can do it.--RDBury (talk) 08:17, 13 September 2009 (UTC)

You want A and B on different colours. And the problem is quite easily solved going though the o's once and only once. I've put the path below as where a path of light would go reflected by some mirrors :)

			/	\
		/	/	\	A
/	.	/	/	\	/	\
\	.	.	/	\	/	.
/	.	.	.	.	\	.
\	.	.	.	\	\	/
	B	\	/	/
		\	/

Dmcq (talk) 20:22, 13 September 2009 (UTC)

Just read the question again. It says to leave out one 'o'. Funny condition. It is impossible then. The version with only three lines of o's between is possible then though. Dmcq (talk) 20:26, 13 September 2009 (UTC)

I think Rckrone has already proven that the 3-line version is impossible. -- Meni Rosenfeld (talk) 20:53, 13 September 2009 (UTC)

Right you are - I stand corrected Dmcq (talk) 06:50, 14 September 2009 (UTC)

I feel like this can be done... I feel that it seems quite easy actually. I'm not very versed in this, otherwise I'd post the solution. Anyone want to know, I'll explain it in further detail later.

Table puzzle

Sorry for the influx of puzzles, but I read this in a puzzle book somewhere. Any ideas?

There is a 6-by-6 table. Fill each cell in the table with 1, 2, 3, 4, 5, 6, 7, 8 or 9 to the following rules (R2 meaning row 2 and C6 meaning column 6):

R1: The sum of numbers placed in this row is 21.

R2: The sum of numbers placed in this row is 39.

R3: This row is filled in by six consecutive numbers, in order.

R4: In this row, its largest and smallest numbers are placed next to each other.

R5: There are exactly two 9's in this row.

R6: Sum of all the numbers placed in this row is 21.

C1: There are exactly two 9's in this column. Its smallest number is 2.

C2: This column is filled in by six consecutive numbers, in order.

C3: There are exactly two 3's in this column. The sum of numbers placed in this column is 21.

C4: There are exactly two 8's in this column. There is no number 4 in this column.

C5: There are exactly two 6's in this column. The sum of numbers placed in this column is 40.

C6: There is no number 7 in this column.

Every cell must be occupied! Professor M. Fiendish, Esq. 11:17, 13 September 2009 (UTC)

Q. Does R1 imply 123456 or can i use 1 twice etc?77.86.47.174 (talk) 18:52, 13 September 2009 (UTC)

Note that R5 says there are two 9's in this row. So, there seems to be no rule as far as only one of each digit per row. That's why I stopped thinking about it. It would probably take a very long time to figure out. 39 would also be 4, 5, 6, 7, 8, 9 if no repeats were allowed. Note also that C5 says the sum is 40, which is impossible with no repeats. StatisticsMan (talk) 19:29, 13 September 2009 (UTC)

IMO this isn't a very mathematical problem. The rules are complex and of different types so it seems impossible to try anything but a trial and error approach. You can narrow it down to 2 possibilities for row 3 and column 2 pretty easily, but after that it seems like the possibilities increase exponentially so you'd need a computer to explore them all. I'm not really stumped so much as I think I have better things to do with my time. Do you happen to know if the solution is supposed to be unique?--RDBury (talk) 02:04, 14 September 2009 (UTC)

Not unique. Probably not even close. Just by trying random ideas, I hit on this:

 231861
 941799
 456789
 363x9y
 977869
 383124

Which satisfies all the rules for many different x,y combinations. one of them has to be the "smallest" in the row, meaning a 1 or a 2, since it's next to the 9, but the other one can be almost anything as long as x!=4, x!=8, and y!=7. And if you make x=8, you get a whole new family of solutions by modifying R1/C4 and R1/C6, still plenty of ways to make them add up to 9 without disturbing anything. This ruleset is busted. 69.245.227.37 (talk) 03:48, 14 September 2009 (UTC)

Sample space

Alright, so I'm in a graduate statistics course and this is a very basic question, first question in book. But, I got counted off for it and I have talked to the professor and the TA and they don't seem to understand at all what I'm saying. So, I'll just give you the question but not my answer or the professors and see what you think. Also, I give you the definition of sample space in the book.

1.1 For each of the following experiments, describe the sample space.

(d) Record the weights of 10-day-old rats.

The set, S, of all possible outcomes of a particular experiment is called the sample space for the experiment.

Thanks for your ideas. StatisticsMan (talk) 16:26, 13 September 2009 (UTC)

I'm not a statistician, but based on the information you've given I would say the sample space is the positive real numbers. Or it could be $\mathbb {R} _{+}^{n}$, where n is the number of rats you are measuring. I can't tell if "a particular experiment" refers to each of the rats individually or the rats as a group. --Tango (talk) 16:44, 13 September 2009 (UTC)

Well, my answer was the nonnegative integers, whereas the professor says the answer is all nonnegative reals. However, allow myself to explain my answer because I did explain what I was doing. In the previous part of the problem, part (c), which is a similar problem, I said basically that the sample space could be all nonnegative reals. But, if we are measuring things, perhaps we pick some unit and we measure to the nearest unit. So, I could also see the answer being nonnegative integers. So, then on this part I just said it COULD be nonnegative integers again. The point I want to make here is it specifically says "Record the weight". It is not "The actual weight". If it were actual weight, of course the answer is all nonnegative or positive reals... of course perhaps we could put some upper bound like 100 pounds. Any number in there is possible. But, it says record the weight. So, someone comes to me and says record the weights. I grab a scale which measures in grams to the nearest gram. The only possible weights I am going to get are integers. It's not possible for 1.2847858 to come up. So, the sample space in that case is integers, is it not???? That is my experiment, that is the sample space that goes with it. All reals is actually wrong in that case, is it not? Or, all reals is right but P(not an integer) = 0. Does this make sense? StatisticsMan (talk) 01:47, 14 September 2009 (UTC)

I see what you are saying, but unless your level of precision happens to be to the nearest whatever unit you are using (or more), it won't be integers. If we are measuring in kilograms and precision is to the near gram, say, we will probably get non-integer answers. Yes, strictly speaking it is still a discrete set, but we don't know what discrete set it is, so we have to go with the smallest set that contains all possible answers, and that is the positive reals. (Definitely not the non-negative reals - you can't have a rat with a weight of 0.) --Tango (talk) 02:03, 14 September 2009 (UTC)

Shouldn't we go with positive rational numbers? The question was about recording weight measurements, and any number you actually record is going to be rational.--Rallette (talk) 07:29, 14 September 2009 (UTC)

You are drawing a distinction between two different experiments, "let X be the weight of a rat" and "let X be the number written down by a researcher after measuring the weight of a rat". You interpret "record the weights of 10-day old rats" as the latter, and your professors interpret it as the former. Well, I give you points for attention to detail and thinking out of the box, but realistically the book was probably going for the former.

With the interpretation of the experiment out of the way, there is still the choice of sample space. Of course, the choice of sample space is a subjective decision, but that doesn't stop me from having an opinion. For the former experiment, positive reals is a natural choice. For the latter experiment, natural choices include positive integers, positive rationals, and positive reals. I vote for reals, for two reasons. First: while restricting our sample space to integers / rationals has the advantage of allowing us to use number theoretic properties, it has the associated disadvantage of drawing undue attention to these irrelevant number theoretic properties (e.g., do I care about the prime factorization of the weight of a rat?). The operations I am most likely to perform on "the weight of a rat" are analytic in nature, not number theoretic; for a simpler example, computing the standard deviation involves a square root, which can't be done in the rationals. Second: I would like the choice of sample space of "the number written down by a researcher after measuring the weight of a rat" to be independent of how that measurement is made. If I measure the weight of a rat by putting it on a scale, sure I get a rational number. However, if I measure the mass of two identical rats by placing one of them 1 meter east of me, and one of them 1 meter north of me, and seeing how long it takes for them to collide due to gravitational attraction, then I get not a rational but ${\sqrt {2}}$ times a rational. Thus the rationals are not an adequate sample space for rat mass measurements if that's how I choose to go about measuring rat masses. Eric. 67.169.125.37 (talk) 10:21, 14 September 2009 (UTC)

It's usual to idealize the sample space for measurements of analogue quantities as real numbers and say what you actually measure has got quantization errors. Dmcq (talk) 14:23, 14 September 2009 (UTC)

p.s. there's also observational error, that article doesn't mention quantization error because it is normally insignificant. Dmcq (talk) 14:35, 14 September 2009 (UTC)

Well, I'm not saying this makes perfect sense, but it makes more sense. The problem is, we barely talked about it in class and the book barely talks about it. Yet, we're supposed to know what it means. Thanks for all your help. StatisticsMan (talk) 01:05, 15 September 2009 (UTC)