Wikipedia:Reference desk/Archives/Mathematics/2023 August 11

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

August 11

Maximum number of days

If we want to separate the numbers 1, 2, 3, …, n^2 to n parts, each part has n numbers, every day, and any two numbers can be in the same part at most one day, what is the maximum number of days such that this is possible? For example, for n = 3, 4 days is possible:

• Day 1: (1,2,3) (4,5,6) (7,8,9)
• Day 2: (1,4,7) (2,5,8) (3,6,9)
• Day 3: (1,5,9) (2,6,7) (3,4,8)
• Day 4: (1,6,8) (2,4,9) (3,5,7)

But 5 days is not possible. 218.187.65.9 (talk) 17:34, 11 August 2023 (UTC)

This is actually a problem in finite geometry, in fact the example you've given is known as the Hesse configuration. It's not hard to see that n+1 is an upper limit, there are n²-1 numbers ("points") other than 1, and each day you use up n-1 of them, so you can have at most (n²-1)/(n-1)=n+1 days. Each group would correspond to a line, and each day a set of parallel lines in this geometry. If you count each day as a "point at infinity" you get a finite projective plane of order n. (Sorry to throw a lot of jargon at you, but it's the easiest way to think of the problem.) If n is prime then you can create examples relatively easily as follows: Relabel the numbers 1 ... n² as ordered pairs (0, 0), (0, 1), ... (0, n-1), (1, 0), (1, 1), ... (1, n-1), ... (n-1, 0), (n-1, 1), ... (n-1, n-1). For day k starting with k=0, group the pairs (a, b) according to the value of a+kb (mod n). You get the last day by grouping on b. So with n=3 you get

• Day 0: {(0, 0), (0, 1), (0, 2)}, {(1, 0), (1, 1), (1, 2)}, {(2, 0), (2, 1), (2, 2)}
• Day 1: {(0, 0), (1, 2), (2, 1)}, {(0, 1), (1, 0), (2, 2)}, {(0, 2), (1, 1), (2, 0)}
• Day 2: {(0, 0), (1, 1), (2, 2)}, {(0, 1), (1, 2), (2, 0)}, {(0, 2), (1, 0), (2, 1)}
• Last day: {(0, 0), (1, 0), (2, 0)}, {(0, 1), (1, 1), (2, 1)}, {(0, 2), (1, 2), (2, 2)}

This method fails when n is not a prime. But when n is a prime power it can be fixed using finite fields; I won't go into details but they should be in the articles mentioned above. See also Galois geometry. It's an open problem whether n+1 is possible for n not a prime power. What I know of what is known is that it's been proven in the negative for n=6 and 10, with 10 being fairly recent and involving a computer search. That leaves 12 as the next candidate. --RDBury (talk) 06:32, 12 August 2023 (UTC)

Interesting stuff, RD! Thanks! --Trovatore (talk) 18:51, 12 August 2023 (UTC)

Hyperoperation: Does the n-th hyper operator relate to n or to n-1 or to n-2?

Does the relation a[n]b (the n-th hyperoperation, i.e. n=1 for addition, n=2 for multiplication, n=3 for exponentiation, n=4 for tetration, n=5 for pentation, n=6 for hexation, etc. relate to n or n-1 or n-2? The Graham’s number has 64 towers of Knuth's up-arrow notation, but Knuth's up-arrow notation has n-2 instead of n up-arrows for the n-th hyperoperation, a[n]b. 218.187.65.9 (talk) 17:40, 11 August 2023 (UTC)

I think the $a[n]b$ notation was developed by enthusiasts on Usenet; it's not clear that it's really become standard in more formal (not mathematically formal but "register"-wise) venues. The hyperoperation article frankly has a problematic title and should be moved to something like generalizations of exponentiation, which I suggested some time ago but haven't followed up on.

That said, at a quick glance, the $a[n]b$ notation seems to be shifted by two from the Knuth notation — natural-number exponentiation $a^{b}$ is $a[3]b$ but $a\uparrow ^{1}b$. --Trovatore (talk) 19:41, 11 August 2023 (UTC)