{"id":3606,"date":"2023-11-23T08:00:18","date_gmt":"2023-11-23T13:00:18","guid":{"rendered":"https:\/\/sites.williams.edu\/Morgan\/?page_id=3606"},"modified":"2023-11-23T08:00:18","modified_gmt":"2023-11-23T13:00:18","slug":"well-arranged-sequences","status":"publish","type":"page","link":"https:\/\/sites.williams.edu\/Morgan\/math-chat-archives\/well-arranged-sequences\/","title":{"rendered":"Well Arranged Sequences"},"content":{"rendered":"

February 1, 2001<\/p>\n

 <\/p>\n

Old Challenge<\/b>\u00a0(Walter Wright). Consider the sequence: 3 1 2 1 3 2. It consists of a pair of 1’s separated by\u00a0one<\/i>\u00a0other number, a pair of 2’s separated by\u00a0two<\/i>\u00a0other numbers, and a pair of 3’s separated by\u00a0three<\/i>\u00a0other numbers. Can you find a similar sequence with a pair of 4’s too? More?<\/p>\n

Answer.<\/b>\u00a0Yes with 4’s: 4 1 3 1 2 4 3 2. Not with 5’s or 6’s. Al Zimmermann did a computer search up through 12’s:<\/p>\n

 <\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
N<\/td>\nNumber of solutions<\/td>\nExample solution<\/td>\n<\/tr>\n
1<\/td>\n0<\/td>\n<\/tr>\n
2<\/td>\n0<\/td>\n<\/tr>\n
3<\/td>\n1<\/td>\n3,1,2,1,3,2<\/td>\n<\/tr>\n
4<\/td>\n1<\/td>\n4,1,3,1,2,4,3,2<\/td>\n<\/tr>\n
5<\/td>\n0<\/td>\n<\/tr>\n
6<\/td>\n0<\/td>\n<\/tr>\n
7<\/td>\n26<\/td>\n7,3,6,2,5,3,2,4,7,6,5,1,4,1<\/td>\n<\/tr>\n
8<\/td>\n150<\/td>\n8,3,7,2,6,3,2,4,5,8,7,6,4,1,5,1<\/td>\n<\/tr>\n
9<\/td>\n0<\/td>\n<\/tr>\n
10<\/td>\n0<\/td>\n<\/tr>\n
11<\/td>\n17792<\/td>\n11,6,10,2,9,3,2,8,6,3,7,5,11,10,9,4,8,5,7,1,4,1<\/td>\n<\/tr>\n
12<\/td>\n108144<\/td>\n12,10,11,6,4,5,9,7,8,4,6,5,10,12,11,7,9,8,3,1,2,1,3,2<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

 <\/p>\n

He guessed that there are solutions if and only if N is a multiple of 4 or one less than a multiple of 4. Joseph DeVincentis came up with a clever proof (reproduced below) that other numbers cannot work. Walter Wright, the proposer, wrote: “I read many years ago (in one of Martin Gardner’s\u00a0Scientific American<\/i>\u00a0columns, I think), that [there is a solution] if and only if N is a multiple of 4 or one less than a multiple of 4. I also read that no general formula had been found to describe how to arrange the sequences–in other words, the only known way was (and probably still is) by brute strength.” He was unable to locate the reference. He did provide a solution with 24’s:<\/p>\n

24 22 23 19 17 21 13 20 10 8 18 4 1 16 1 15 4 14 8 10 13 12 17 19 22 24 23
\n21 20 18 16 15 14 11 12 7 9 3 5 2 6 3 2 7 5 11 9 6.<\/p>\n

Here is Joseph DeVincentis’s proof that N has to be a multiple of 4 or one less than a multiple of 4:<\/p>\n

Since the ones are 2 places apart, the twos 3 places apart, and so on, until the N’s are N+1 places apart, the sum of the differences of the places where each number occurs is 2 + 3 + . . . + (N+1). This has the same parity (odd or even) as the sum of all the places, 1 + 2 + . . . + 2N. If N is even, this means that N\/2 (the number of odd terms in the first sum) has the same parity as N (the number of odd terms in the second sum), and N must be a multiple of 4. If N is odd, it means that (N-1)\/2 has the same parity as N, and N must be one less than a multiple of 4.<\/p>\n

New Challenge<\/b>\u00a0(Todd Feitelson). How many different strings of ten 1’s and 0’s are there such that no two 1’s are consecutive? That is,<\/p>\n

 <\/p>\n

1000101010 is acceptable, but
\n1000010110 is not acceptable.<\/p>\n

 <\/p>\n

\n

Send answers, comments, and new questions by email to\u00a0Frank.Morgan@williams.edu,<\/a>\u00a0to be eligible for\u00a0Flatland\u00a0<\/i>and other book awards. Winning answers will appear in the next Math Chat. Math Chat appears on the first and third Thursdays of each month. Prof. Morgan’s homepage is at\u00a0www.williams.edu\/Mathematics\/fmorgan.<\/a><\/p>\n

THE MATH CHAT BOOK,<\/a>\u00a0including a $1000 Math Chat Book\u00a0QUEST,\u00a0<\/a>questions and answers, and a list of past challenge winners, is now available from the MAA (800-331-1622).<\/p>\n

Copyright 2001, Frank Morgan.<\/p>\n","protected":false},"excerpt":{"rendered":"

February 1, 2001   Old Challenge\u00a0(Walter Wright). Consider the sequence: 3 1 2 1 3 2. It consists of a pair of 1’s separated by\u00a0one\u00a0other number, a pair of 2’s separated by\u00a0two\u00a0other numbers, and a pair of 3’s separated by\u00a0three\u00a0other numbers. Can you find a similar sequence with a pair of 4’s too? More? Answer.\u00a0Yes […]<\/p>\n","protected":false},"author":2965,"featured_media":0,"parent":3459,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"footnotes":""},"class_list":["post-3606","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/pages\/3606","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/users\/2965"}],"replies":[{"embeddable":true,"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/comments?post=3606"}],"version-history":[{"count":1,"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/pages\/3606\/revisions"}],"predecessor-version":[{"id":3607,"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/pages\/3606\/revisions\/3607"}],"up":[{"embeddable":true,"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/pages\/3459"}],"wp:attachment":[{"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/media?parent=3606"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}