Colossal Gardner, ch. 25

Aleph-Null and Aleph-One
Martin starts out by mentioning a question raised by Paul J. Cohen (29) in 1963. Is there an order of infinity higher than the number of integers but lower than the number of points on a line? To answer this, Martin goes into an explanation of Georg Cantor’s discovery of the infinity of higher levels of infinity. The base level, the number of integers, was called Aleph Null. We include in this set any selection of numbers that can be counted (not that anyone is actually going to try counting them), such as all prime numbers, all natural numbers, all even, odd, positive or negative numbers, all rational fractions, and so on. Yes, some of these sets can include values that get much bigger, much faster than some of the other sets, but the important distinction is that they can be counted.

Example with prime numbers:
1 (1), 2 (2), 3 (3), 5 (4), 7 (5), 11 (6), 13 (7), 17 (8), 19 (9), etc.

Aleph-Null numbers are said to be “countable” or “denumerable”. This brings us to a paradox, in that with infinite numbers, “they can be put into correspondence with a subset of themselves,” or with their “subsets.” One example was developed by logician Charles Sanders Pierce. Start with the fractions 0/1 and 1/0 (ignoring the divide by zero issue for the moment). Sum the two numerators and then the two denominators to get the new fraction 1/1 and place it between the original pair. Repeat this process with each pair of adjacent fractions to get the new fractions that go between them.

0/1 . 1/0
0/1 . 1/1 . 1/0
0/1 . 1/2 . 1/1 . 2/1 . 1/0
0/1 . 1/3 . 1/2 . 2/3 . 1/1 . 3/2 . 2/1 . 3/1 . 1/0

As Gardner mentions, as this series continues, every rational number will appear once and only once. Reducible fractions like 10/20 never show up. If you want to count the fractions at any given step, you can take them in their order of appearance. Any two fractions equally distant from the center, 1/1, are reciprocals of each other. And, any two adjacent pairs ab and c/d have the following equalities: bc – ad = 1; c/d – a/b = 1/bd. Also, as Gardner says, this series is closely related to Farey numbers. Pierce’s process creates an infinite number of countable fractions, as a subset of all numbers.

(All rights belong to their owners. Images used here for review purposes only. Example of creating subsets of a set of three elements.)

The next step is to show that there’s another set with a higher order of infinity than Aleph-Null. The above figure uses three objects – a watch, a key and a ring. Below each, you lay out a row of 3 cards, face down (black) or face up (white) to represent subsets. A white card shows that the above object is in the subset, while black indicates that it is not. The first subset consists of the original set. The next three rows are subsets of 2 objects each, the following three are subsets of one object each, and the bottom row is the empty, or null, subset that doesn’t have any objects. “For any set of n elements, the number of subsets is 2^n.”

Apply this procedure to an Aleph-Null set, which is countable, but infinite. The above figure attempts to show that this new set is countable, with each row represented by the white and black cards extending to infinity. They can be listed in any order, and numbered 1, 2, 3, etc. “If we continue forming such rows, will the list eventually catch all the subsets? No – because there is an infinite number of ways to produce a subset that cannot be on the list.” We can do this by taking every card on the diagonal line and flip it white-for-black, making a new subset that hadn’t existed before, even though the original set was infinite. This set is not countable, showing that the assumption was wrong. So, “the set of all subsets of an Aleph-Null set is a set with the cardinal number 2 raised to the power of Aleph-Null.” As a side effect, Cantor’s diagonal proof shows that the set of real numbers (rationals and irrationals) is also uncountable. Again, using the above figure, we’ll assume a line segment with end points at 0 and 1. Assign binary values to the decimal portion of the segment, and list them on the rows of subsets, and you get the same result as before.

Cantor then showed that the subsets of Aleph-Null, the real numbers and the total points on a line segment all have the same number of elements. He gave this cardinal number the name “C,” the “power of the continuum,” and said that this is Aleph-One, the first infinity greater than Aleph-Null.

Gardner continues to talk about the importance of the Cantor sets in geometry, using the above figure. Say you have an infinite plane tessellated with hexagons. “Is the total number of vertices Aleph-One or Aleph-Null?” The answer is – Aleph-Null, because you can count them along a spiral path. But, the number of circles of one-inch radius placed on a sheet of paper is Aleph-One, because inside any small square near the center of the page are an Aleph-One number of points that are the centers of their own 1-inch circles.

Puzzle for today:
Using J. B. Rhine’s ESP card symbols, are there any symbols that can be drawn an Aleph-One number of times on a sheet of paper, assuming lines of no thickness, with no overlapping or intersections of the lines? (They don’t have to be the same size, but they must have similar shapes.)

To come back to Cohen… Cantor thought there would be an infinite hierarchy of Alephs, obtained by raising the previous one to the power of 2, and that there are no other Alephs in between. There’s no Ultimate Aleph, either. He tried, but could not prove that there’s no Aleph between Aleph-Null and C. Kurt Godel showed in 1938 that the so-called Cantor conjecture could be assumed to be true. And here we get Cohen, who proved in 1963 the opposite could also be assumed – that C is not Aleph-One. There can be at least one Aleph between Aleph-Null and C, although no one has any idea how to specify it. All he did was demonstrate that the continuum hypothesis is unprovable within standard set theory.



Suugaku Cafe – Sandeco

There’s a coffee shop just across the street from City Hall in Kagoshima that I see all the time when I go to and from the English school. They used to roast their own coffee, and I went one time a few years back to check it out. The hand-ground and poured coffee was good, but they were charging something like 400 ($3.70 USD) yen for one small cup, with no free refills, so I didn’t go back.

Then, a few weeks ago, a couple of my students told me about this “suugaku cafe” (mathematics), where the owner was a recreational math enthusiast. The cafe serves as a coffee shop during the day, and then as a cram school for junior high students in the evening. My students suggested I check it out, but they didn’t know the name of the place. So I went online and did a google search on “suugaku cafe kagoshima”. The results showed it was near my school, and the next day I had a little free time and was in the area, so I swung by. I was surprised to see that it was the former coffee roaster, Sandeco, and that they still had the same sign as before. Underneath the sign, it says “mathematics cafe and cram school.” So, maybe it always was math-oriented and I just didn’t realize it then (but I don’t think so. I think they may have changed ownership.)

In general, they look like a regular cafe, serving curry rice with sweet Kagoshima pork, and Shirokuma shaved ice desserts. This lunch set of the curry rice, onion soup, salad, and a small cup of hot coffee after the meal was 750 yen ($7 USD). A bit more than I want to pay for lunch on a regular basis, but it was good, at least.

The only thing that hints at the math aspect of the place is this row of text books, and the white case of drawers in the lower right corner of the nook. (Plus, advertising in the menu for their mascot, Suuga-kuma, (a play on Suugaku (math) and kuma (bear)).) The drawers hold 12 different math puzzles on 3×5 cards, and are divided up into 1st year through 3rd year junior high-level difficulties, 4 cards per level.

I asked the waitress how the system worked, and she explained it, saying that the easiest puzzle was in the upper left drawer, and the hardest one, which she thought was really hard, was in the lower right drawer. (So, difficulty goes from top to bottom, left to right.) I decided to try my luck with the easiest one. What I got was 2(x-1) = 3(x+2) + (x-4), solve for x.

It took me more time to figure out the instructions than it did to do the actual problem. I showed all my steps just in case that’s what the rules required. While I was at the cafe, there were another 9-10 customers, who were also there to do the problems. The rules allow two puzzles per customer per order, so I grabbed the second puzzle for 1st year students. I messed up on one step, showing that it’s better for me to not do these things in pen. I did correct my mistake, though.

Sandeco loves its coffee and math.

There’s kind of a window display in the hallway leading from the door to the main seating area, and in the display were coffee-themed Halloween decorations.

The prizes for completing the puzzles correctly are little paper stickers featuring Suuga-kuma (a white caricature of a bear, wearing a textbook for a professor’s cap) and some kind of joke saying. The one on the left says “eating meals, taking baths, and sleeping are good for you.” There are a total of 50 seals, but only 12 puzzle cards, so I don’t know how the cafe selects the seals you get at any given time, if they’re related to the puzzle, or if they’re totally random.

It’s not worth going back every week just to collect the little seals, but I might consider getting one of the shaved ice desserts on a Saturday if I have a 1-hour break between lessons.

(Secret – I did sneak a look at the hardest problem just to find out how hard it is. It’s pretty simple, but I’m having trouble understanding the Japanese instructions. It’s asking for dy/dx of a simple equation, but I’m not sure if this is supposed to be differentiation or integration. I’m guessing differentiation. Keep in mind, this is a junior high-level problem, and in the U.S. in the 1970’s, I didn’t get into differentiation until I got into college.)

New Gakken Adult Science kit coming out Dec. 15

Finally got some news out of Gakken on their Otona no Kagaku (Adult Science) magazine/book/kit series.

Their facebook page announced near midnight on Tuesday that their tiny letterpress printer kit will come out mid-December, for 3,500 yen (not including tax). There’s nothing on this yet on the official website, and the Amazon page is just a blank stub, showing a Dec. 15 release date.

The machine translation of the Facebook announcement reads:
“I’ve been waiting for you for a long time!
The Latest Edition of an adult science magazine, a bath, “small typographical printing machine” on sale on December 15th!
A Letterpress Printing machine called ” Texaco You can create a business card, a message card, etc. The price is 3500 Yen (excluding tax). Thank you for your patronage!
By the way, this is the actual chintakureifu.”

Answer for regression of the answer for the article on regression with the answer…

For the cross-stitch curve, how long is the final perimeter, and how large is the enclosed area?

If the cross-stitch is built to extend outward from the center of the square, the perimeter is infinite, but the area is twice that of the original square. If the stitch extends inward towards the center, the perimeter is still infinite, but the area goes to zero.

Colossal Gardner, ch. 24

We are now into the section on Infinity, with the chapter on Infinite Regress. The idea here is that you take increasingly many increasingly smaller slices of something on into infinity. Gardner gives examples both from real life, as well as math. These include the plays Tiny Alice, (1964) by Edward Albee and Six Characters in Search of an Author (Luigi Pirandello), and stories like The Town in the Library in the Town in the Library (E. Nesbit), Point Counter Point (Aldous Huxley), The Sorrow of Search (Dunsany), and The Notebook (Norman Mailer). Plus, we also have M. C. Escher’s Drawing Hands.

(All rights belong to their owners. Images used here for review purposes only. A graphic proof for the impossibility of cubing the cube.)

On the math side, both positive and negative numbers disappear into infinity, and every infinite series is an infinite regress. Above is part of a proof for whether it is possible to cube the cube, which is related to squaring the square. In the latter problem, you want to create a tiling of “an integral square only using other integral squares”. Is it possible to do this with cubes? The answer is no.

(Droste ad using regression.)

Gardner also mentions processes that are repeated on smaller and smaller segments of a regular polygon to create something with an infinite perimeter but finite area, including the Koch snowflake.

And the cross-stitch curve (I drew this one.)

For the cross-stitch curve, how long is the final perimeter, and how large is the enclosed area?


A different riff on Smullyan

Zack Weinersmiths’s take on Smullyan’s Knights and Knaves puzzles…

Nontransitive problem answer for Wednesday

TTHH has a waiting time of 16, and HHH has a waiting time of 14. Which tuplet is most likely to appear first, and with what probability?

Using Conway’s rule,

0011 = 3 (BA)

000 = 0 (AB)

1000 = 8 (BB)

111 = 7 (AA)

AA – AB : BB – BA = 7 – 0 : 8 – 3
TTHH is more likely to occur before HHH with a probability of 7/12, or odds of 7 to 5.

Colossal Gardner, ch. 23

More Nontransitive Paradoxes
This chapter was written independently of the last one on intransitive dice, and includes different examples of transitivity (if A = B, and B = C, then A = C) and intransitivity (if A is the father of B, and B is the father of C, A is NOT the father of C; or, if A loves B and B loves C, it’s not guaranteed that A loves C (just ask any father what they think about their daughter’s latest boyfriend). Gardner then comments that intransitive relationships are sometimes so counterintuitive in probability theory and decision theory that they’re referred to as intransitive paradoxes. One of the oldest ones is a voting paradox called the Arrow paradox after Kenneth J. Arrow’s use of it in his “impossibility theorem” (for which he shared a Nobel prize in economics in 1972).

Arrow gave 5 criteria that he deemed essential in a “democracy in which social decisions are based on individual preferences expressed by voting” in his work “Social Choice and Individual Values.” The problem is, the conditions are logically inconsistent, and in most instances it is impossible to devise a voting system that doesn’t violate at least one of the conditions. That is, “a perfect democratic voting system is in principle impossible.”

This is something very relevant in the current political environment in the U.S. these days…
In Martin’s words: [Our current system] “frequently puts in office a man who is cordially disliked by a majority of voters but who has an enthusiastic minority following.” Say that 40% of the voters really like candidate A. The opposition gets split between 30% for B and 30% for C. A is elected even though 60% of the people dislike him.

(All rights belong to their owners. Images used here for review purposes only. The voter’s paradox.)

One suggestion for resolving this problem is by letting voters rank the candidates in order of preference, but this works poorly, too. Using the chart above, The top row has 1/3 of the voters preferring candidates A, B and C in that order. The middle row shows another third ranks them BCA, and the bottom row gives the remaining third as liking the candidates in the order CAB. If you rank the candidates in pairs, 2/3rds prefer A to B, 2/3rds prefer B to C, and 2/3rds prefer C to A. If the candidates are paired up, A would defeat B, or B would defeat C, but C would defeat A. If instead of candidates, you vote on proposals, then it’s easy to rig the system to get the proposals you want to win by determining how to pair them up. This flaw has been recognized as far back as the 1700’s, but people keep rediscovering it, including Lewis Carroll. It turns out that the best solution when you get a paradox like this is to select a “dictator” to break the ties.

The same situation can occur when pitting teams against each other in a round-robin tournament, as shown in the above matrix. The paradox arises when picking two alternatives from a set of three or more. Say a woman ranks three men based on intelligence (A), physical attractiveness (B) and wealth (C). If, taken in pairs, she prefers A over B, B over C and C over A, she may have difficulty in selecting simultaneously from three suitors that fall into only one category each. Alternatively, we have Paul R. Halmos’s pie problem. If a restaurant can only serve two pies at any given meal (Apple, Blueberry and Cherry) and customers can make decisions over freshness, taste and size of slice, then it may be reasonable for someone to prefer apple over blueberry, blueberry over cherry, and cherry over apple.

Nontransitivity in gambling games is actually rather common and can lead to some major sucker bets. One kind of nontransitive game is the above top designed by Andrew Lenard. The lower disk is fixed while the upper one rotates. Two players pick different arrows (A, B or C) and spin the spinner. The player whose arrow points to the section with the highest number wins. A will beat B, B will beat C and C will beat A in 2/3rds of the cases.

Mathematician Walter Penney found one of the better betting systems. If you have a coin and flip it three times, the equally possible 8 outcomes are: HHH, HHT, HTH, HTT, THH, THT, TTH and TTT. One player selects one of these triplets, and the other player takes a different one. Now, start flipping the coin. The first person whose triplet appears first as a run wins. Example, A picks HHT and B takes THT. If the coin flips are THHHT, A wins. You would think that all 8 triplets are equally likely, but first let’s look at two flips: HH, HT, TH and TT. Say that you flip the coin and get H. From here, HH and HT are equally possible (HH = HT). But, starting from scratch, HH = TT, and with the same symmetry, TT = TH, and HT = TH. But, TH beats HH by 3 to 1. Looking at a longer run from the game, say we’re comparing HT and TT. TT is always preceded by HT except when TT shows up on the first 2 flips. I.e – HHHT versus TT on the first two flips. The odds are shown in the above matrix for triplets, and HT is much more likely to appear first in the run than TT is.

Followed by the odds for quadruplets.

John Conway developed a procedure for calculating the odds that one n-tuplet will precede another (above figure). To show how this works, let’s use the 7-tuplets (A) HHTHHHT and (B) THHTHHH. Can B beat A? First, write A above A, B above B, A above B, and B above A. Above each pair, you build up a binary number using the following rule: Do the first 7 letters match the seven letters of the tuplet below it? For A/A, the answer is “yes”, so write “1” above the first letter. Do the 6 letters starting with position 2 match the first 6 letters of the second tuplet? No, so write “0” above the second letter. Do the 5 letters starting with the third letter of the top line match the first 5 letters of the second line? No, so also write “0” here. Keep doing this for all 7 positions, then translate the binary value “1000100” to decimal to get 68. And repeat the entire process for the other three pairings. The odds of B beating A are given in the ratio AA – AB : BB – BA. In the above example, that’s 68-1 : 64-35 = 67:29.

If you look at the run of heads and tails, waiting for a particular string to show up, the number of tosses expected is called the waiting time. If you’re standing on a street corner waiting for a bus, the longer you wait, the shorter the time expected before the bus shows up. Coins, however, don’t have a memory, so the waiting time for a particular string of flips remains the same no matter how many times you’ve already flip the coin. The waiting time for H and T is 2. For doublets, it’s 4 for HT and TH, and 6 for HH and TT. For triplets, it’s 8 for HHT, HTT, THH and TTH; 10 for HTH and THT, and 14 for HHH and TTT. So far, so good. “But with a quadruplet, THTH has a waiting time of 20 and HTHH has a waiting time of 18, yet THTH is more likely to show up than HTHH with a probability of 9/14. That is, an event that is less likely to occur, is more likely to occur first. There’s no logical contradiction here, but it does look paradoxical.

Problem for the week: TTHH has a waiting time of 16, and HHH has a waiting time of 14. Which tuplet is most likely to appear first, and with what probability?


Gomen ne Mister Roboto

During the entire time I was working at getting the RoboDesigner robot fully functional and up and running, I had in the back of my mind the desire to give it running lights. Specifically, the idea was to put a line of LEDs along both the right and left sides of the top board. I certainly have enough LEDs to do this, but what I wasn’t sure of was whether I had a stock of resistors stashed somewhere. I’d also need a micro toggle switch to control power from the main kit batteries, and that would probably have to be sent to me from the U.S., most likely as part of a Christmas package. But, if I needed the resistors too, then I’d be willing to wait to pull this off.

A few days ago, I’d decided to clean out the apartment a little, and in the back of a small bookshelf, I found a bag with some of my soldering supplies, which I then put in with the rest of my spare parts. So, I went to the spare parts case, and pulled everything out to see what I did have. Unfortunately, while I found the bag of LEDs, I didn’t locate any small-value resistors. On the other hand, I located my old 8×8 LED matrix board for the Arduino-based Gakken Japanino micro-controller. So, why not?

I dug out the Japanino and the battery pack, plugged in the matrix, and turned it on. The LEDs lit, so the batteries still worked, as did the Japanino, but the thing had an old program loaded that was for a different project. That meant that I had to break out the Arduino programming environment again, but I’d upgraded to a new laptop last Spring, and I hadn’t gotten around to transferring the environment to the new PC. So, I go to the Arduino website, download the latest version of the software (which downloaded slow and took almost 15 minutes to finish), ran the installer, and finally remembered that I had to dig out my backup hard drive in order to copy off the old matrix sketch files to the new PC, too. This is when I realized that I have too many files.

(Robot with the Japanino controlling the old 8×8 LED matrix.)

I had written a variety of programs for the Japanino over the years, and built several different hardware forms of LED matrices, and now I couldn’t find the file I needed for this circuit. I spent an hour on that, while struggling with the Arduino environment to get it to talk to the Japanino. I slowly figured stuff out (the board type is the Duemilanova, with the ATmega168, attached to COM6, and English is specified in the preferences section (the environment defaulted to Japanese) that I’ll document here in case I need this information again in the future). In fact, I had everything going right except for the correct sketch.

I was leaning towards writing the sketch all over from scratch, which I didn’t think would take that long. Except, I haven’t used the Japanino in almost 3 years, and suddenly, I can’t remember how the code works. I’ve got the old code for a 4×4 LED matrix, so I could print that out, and slowly reverse-engineer it, but that’s looking to be a bigger project than I want to take on right now. That’s when I located the 8×8 matrix sketch file that I’d been looking for. Yay, me.

So, I load the sketch into the environment, and it won’t compile. Seems that the Arduino guys stopped supporting the prog_uchar data type that had been required for reading static memory, and that had been a central part of my original sketch. Fortunately, I found a webpage on the net that gave an updated example for reading static memory, and the new code used “byte” instead of “prog_uchar”. I do a replace all on my files, recompile, and download the sketch to the Japanino, and my text scroller routine pops up and scrolls text on the matrix. So that part is good now. Yay, me.

The final step is to figure what to do about mounting the Japanino on the robot. After messing with things for a while, the only option seems to be to take a pair of longer bolts, and several nuts, and use them as stand-offs to hold the Japanino and matrix in place over the robot’s battery holder. There are several options for placing the Japanino battery pack around the robot (loose in between the sandwich boards, taped under the bottom board near the motor assemblies, or on the top board, sandwiched in with the cables. I settle for the third option because it’s easier to reach the power switch that way. I put everything back together again, test the kit and the Japanino, and everything works ok.

(One of the text scroller sketch animations.)

Right now, there’s no relationship between what’s on the matrix and what the robot is doing, but that’s ok. At some point, I’ll probably change the scroller to just have a scrolling arrow pointing forward, or maybe marquee lights. All that really matters right now is that I’ve got a bit of bling on the robot. Yay, me.

Wednesday probable answers

Puzzle for the week:

What’s the correct answer for the probability that 2 randomly selected cards are of the same color?

The packet has 4 cards, two red and two black. If you pick a red card first, then there are three cards left, only one of which is also red. So the probability of getting the second red card is 1/3. Conversely, if the first card is black, then you have 1:2 odds (1/3) of getting the second black card. That is, the probability is 1/3 of getting 2 randomly selected cards of the same color, regardless of the first color chosen. So, actually, the game is 2:1 in favor of the cards having different colors.

This may seem counter-intuitive, especially if you change the conditions so that the dealer shuffles the cards, deals two to you and keeps 2 for him/herself. In this case, you’re looking at both cards in your hand simultaneously, and you should get either RR, RB, BR or BB, which seems to be 50-50 odds. But, say that you assign unique numbers to the cards: 1, 2, 3 and 4. (1 and 2 are the red cards, 3 and 4 are the black ones.)

Next, look at the permutations if you lay the cards out in a row (just taking the first 25% of the permutations as a working case. The remaining 75% of the permutations turn out to follow the same pattern).

1234 – RR BB
1243 – RR BB
1324 – RB RB
1342 – RB BR
1423 – BR RB
1432 – BR BR

If you get the first two cards of any layout, and the dealer keeps the second two cards, then only the first 2 permutations (1234 and 1243) of the above 6 possible will result in you getting both red cards. Expanding the pattern to all 24 permutations, 8 of them will be in RR BB, or BB RR order, and the other 16 won’t be. That’s 16-8, or 2-1 odds of getting two different color cards, confirming the original proof at the beginning of this blog entry where you took 2 cards one at a time.