-4
$\begingroup$

At a pub, a friend spotted our table number being 412; there were nowhere near 400 tables.

We mused if it could include a checksum so the bartender could tell if customers gave an invalid number.

I thought it even better if it had error-correction, so any single digit being changed (without reordering) would still let the correct number be recovered.

Another friend proposed triplicating the number, so 97 might become 999777, and the majority of each triplet would decide its corresponding digit.

Over the next two days we wondered if we could do better (shorter code) yet can be mentally computed by the average bartender.

Can anyone propose a scheme with a shorter code that can be done without the need for computers?

$\endgroup$
  • 2
    $\begingroup$ I've downvoted this question because of this: en.wikipedia.org/wiki/…. It's not really a puzzle, and you can find different ways of tackling this online $\endgroup$ – Marius Sep 15 '16 at 9:07
  • 2
    $\begingroup$ This might be a good fit if you can restrict the possible answer to a single scheme by giving more restriction on how the code can be generated and used. As of now, "can be done with mental arithmetic" is vague and subjective at best. Do edit the question with more details if you think this is manageable. =) $\endgroup$ – justhalf Sep 15 '16 at 9:48
  • $\begingroup$ Am very intrigued by the concept. Error correcting codes that I know are easier to perform mentally in a library than at a pub. Agreeing with @justhalf, it wouldn't hurt to be more specific, perhaps with a number of tables and which operations are allowed. Someone could still provide a solution that demonstrates what is possible with different conditions. $\endgroup$ – humn Sep 15 '16 at 9:59
  • 1
    $\begingroup$ ​My proposal was to sum the digits and take the units place (9 + 7 = 16 so take 6) and append it to two copies of the table number (97976). When the code is received (say, 97971), if the first two pairs are the same, we use either pair (97). If changed digit is not the last one (say, 37976), we check whether the units place of sum of the first pair, and take the first pair if it matches the checksum, or the other pair otherwise (3 + 7 = 10 but 0 is not 6, so take 97 instead). $\endgroup$ – Gnubie Sep 17 '16 at 20:24
  • 1
    $\begingroup$ Why not post your 5-digit approach for 100 tables as an answer? It works very well and I increasingly doubt that any equally straightforward method can use fewer digits for 100 tables. $\endgroup$ – humn Sep 19 '16 at 4:13
3
+50
$\begingroup$

I'm not a fan of the 999777 scheme. It would work for detecting errors in something indifferent to the content, like a computer, but a human mis-remembering the number is extremely likely to remember it as "two digits, each repeating 3 times", and so in case of an error would make an error in all three.

Reed-Solomon codes: 64 3-digit numbers

My first attempt was to use Reed-Solomon codes. With just one extra digit, these codes are guaranteed to detect any one-digit error, and with two extra digits they can even correct any single one-digit error. They're essentially impossible to compute "on the fly" for a human though.

But the bigger problem is that I don't know if it's possible to make these work over decimal symbols. Best I could do is to generate hex RS code (using the x^4 + x + 1 polynomial) and filter out all the numbers that contain a non-decimal digit.

Here's my set of 3-digit numbers for up to 64 tables, generated using this approach:

000 012 024 036 048 083 091 104 116 120 132 168 187 195 208 240 252 264 276 299 328 344
356 360 372 403 411 427 435 459 480 492 507 515 523 531 579 584 596 619 643 651 667 675
688 739 747 755 763 771 806 814 822 830 878 885 897 902 910 926 934 958 981 993

For 4-digit numbers, this produces a set of 625 unique table numbers.

Brute-force search: 98 3-digit numbers

Brute-force is a viable approach for the 3-digit and 4-digit problem. I wasn't sure if it was going to beat the RS code, but I had high hopes because a theoretical decimal-Reed-Solomon (honestly have no idea if this exists) would be able to fit on the order of 100 table numbers in 3 digits.

The largest set I could find consists of 98 numbers. Actually I found as many as 34 distinct sets of 98 3-digit numbers satisfying this constraint, but not a single set larger than that. Here's one example:

002 019 027 034 045 051 063 070 086 098 103 111 126 139 144 158 160 172 187 195 207 218
223 231 249 250 266 274 285 292 306 317 325 333 348 354 361 389 390 401 414 420 438 453
465 479 482 496 504 515 528 530 547 552 569 576 583 591 609 610 622 635 641 656 664 673
688 697 700 712 724 737 746 759 768 775 781 793 805 813 821 836 840 857 862 878 884 899
908 916 929 932 943 955 967 971 980 994

I really wonder if a 99-long set exists. I find it rather likely that the way this brute-force search works makes it exceedingly unlikely for it to stumble upon a 99-long set if it exists, especially so if it's unique. Also, is a 100-long set possible? Reed-Solomon codes achieve the equivalent of a 100-long set for hex digits, after all.

For 4-digit numbers, the best I could find is a 796-long set.

Source code for the brute force searcher here.

Check digit

I briefly wondered about this, but apparently I dismissed it too quickly. ISBNs use a mod-11 check digit which uses an alphabet of 11, not 10, so is not suitable for this task. But it does more than specified by the OP; it also guards against digits being switched.

This answer points out that if you simply add a check digit such that the sum of all digits mod 10 is 0, that will guarantee error detection for any single digit error, thus achieving 100 tables in 3 digits. This also satisfies the constraint that it is easy to mentally check any given number. The 100 table numbers are thus:

000 019 028 037 046 055 064 073 082 091 109 118 127 136 145 154 163 172 181 190 208 217
226 235 244 253 262 271 280 299 307 316 325 334 343 352 361 370 389 398 406 415 424 433
442 451 460 479 488 497 505 514 523 532 541 550 569 578 587 596 604 613 622 631 640 659
668 677 686 695 703 712 721 730 749 758 767 776 785 794 802 811 820 839 848 857 866 875
884 893 901 910 929 938 947 956 965 974 983 992

So all that brute-forcing was in vain (but fun nevertheless!) and is even a little embarrassing considering the simplicity of the check digit...

Furthermore, there exist algorithms that manage to detect not only all single digit errors, but also all adjacent transpositions (in the entire number including the check digit), in just a single decimal check digit: Verhoeff algorithm, Damm algorithm.

$\endgroup$
  • 1
    $\begingroup$ ^vote with a note: Is there a way for bartenders to work this system in their heads within seconds? (oops, answered in the solution, will delete) $\endgroup$ – humn Sep 19 '16 at 21:46
  • 1
    $\begingroup$ @humn I don't think so. But as alluded to in my first paragraph, any trivial scheme would be "cracked" by the patrons and lose its value. For 3-digit codes with something like 20 tables, I imagine anyone working there for 6 months or more will remember all of them. After all, people working in supermarkets remember the PLU codes for all of the common products... $\endgroup$ – RomanSt Sep 19 '16 at 21:51
  • 1
    $\begingroup$ Most bartenders have excellent memories, indeed, already holding more ways to mix a drink than there will ever be tables. $\endgroup$ – humn Sep 19 '16 at 22:03
  • $\begingroup$ You're getting closer and closer to error correction for 100 or more tables with 4 digits. I spent over a decade with ISBNs and could mentally fill in a digit of an ISBN-10 (which seems like a perfect system compared to ISBN-13) when the digit's position was known, and I wasn't even a bartender. $\endgroup$ – humn Sep 20 '16 at 8:44
  • 1
    $\begingroup$ @Gnubie I don't think the previous sections address correction. If you don't know which digit has the error then there are multiple applicable corrections. Example from the 98-set: table number is 285, customer says 215. Is it 285, 515, or 218? All three are possible. Sorry if I made it sound like correction is taken care of! $\endgroup$ – RomanSt Sep 20 '16 at 12:46
2
$\begingroup$

For starters, an approach that requires no calculation at all

Here is a way to assign 4-digit numbers to 70 85 tables, still not 100, so that any single incorrect digit will leave a number that nonetheless matches 3 digits of only one table..

             0000 0111 0222 0333 0444 0555 0666 0777 0888 0999
             1012 1120 1231 1345 1453 1564 1679 1786 1907
             2021 2102 2210 2354 2435 2543 2687 2768 2876
             3034 3156 3203 3317 3429 3570 3641 3792 3865
             4046 4137 4258 4301 4460 4519 4693 4724 4972
             5057 5148 5269 5326 5471 5532 5604 5713 5890 5985
             6063 6174 6247 6380 6406 6591 6615 6739 6852
             7075 7183 7294 7362 7628 7740 7809 7916
             8089 8195 8378 8527 8630 8751 8814
             9098 9482 9705 9823 9950

This approach stems from a limited understanding of Gray codes and a possible misunderstanding of Hamming codes. Fewer than 4 digits cannot work this way at all, while 5 digits can identify at least 532 tables whose numbers differ by at least 3 digits from all others. Seems that 6 digits can identify at least 5258 tables for larger-than-average pubs, suggesting an efficient scale-up of almost 10 times the tables per additional digit. Surely this can be figured more reliably with mathematics than with the loosely-verified hack program that was used for expedience and also produced the following 5-digit table numbers.

00000 00111 00222 00333 00444 00555 00666 00777 00888 00999 01012 01103 01230 01321 01456 01547 01674 01765 02023 02132 02201 02310 02467 02576 02645 02754 03031 03120 03213 03302 03475 03564 03657 03746 04048 04159 04284 04395 04806 04917 05069 05178 05296 05387 05814 05905 06085 06194 06249 06358 06827 06936 07097 07186 07268 07379 07835 07924 08408 08519 08680 08791 08842 08953 09429 09538 09692 09783 09850 09941
10013 10102 10231 10320 10457 10546 10675 10764 11001 11110 11223 11332 11445 11554 11667 11776 11889 11998 12030 12121 12212 12303 12474 12565 12656 12747 13022 13133 13200 13311 13466 13577 13644 13755 14079 14168 14297 14386 14815 14904 15058 15149 15285 15394 15807 15916 16096 16187 16278 16369 16834 16925 17084 17195 17259 17348 17826 17937 18439 18528 18693 18782 18851 18940 19418 19509 19681 19790 19843 19952
20021 20130 20203 20312 20465 20574 20647 20756 21033 21122 21211 21300 21477 21566 21655 21744 22002 22113 22220 22331 22446 22557 22664 22775 22898 22989 23010 23101 23232 23323 23454 23545 23676 23767 24087 24196 24258 24349 24824 24935 25095 25184 25279 25368 25836 25927 26059 26148 26286 26397 26805 26914 27078 27169 27294 27385 27817 27906 28481 28590 28609 28718 28863 28972 29493 29582 29628 29739 29871 29960
30032 30123 30210 30301 30476 30567 30654 30745 31020 31131 31202 31313 31464 31575 31646 31757 32011 32100 32233 32322 32455 32544 32677 32766 33003 33112 33221 33330 33447 33556 33665 33774 33899 33988 34094 34185 34269 34378 34837 34926 35086 35197 35248 35359 35825 35934 36068 36179 36295 36384 36816 36907 37049 37158 37287 37396 37804 37915 38492 38583 38638 38729 38870 38961 39480 39591 39619 39708 39862 39973
40089 40198 40840 40951 41288 41399 41852 41943 42409 42518 42682 42793 42861 42970 43428 43539 43690 43781 43873 43962 44005 44114 44236 44327 44441 44550 44663 44772 45017 45106 45224 45335 45453 45542 45671 45760 46044 46155 46267 46376 46410 46501 46629 46738 47056 47147 47275 47364 47432 47523 47608 47719 48615 48704 48886 48997 49634 49725
50419 50508 50683 50792 51438 51529 51691 51780 52088 52199 52853 52942 53289 53398 53841 53950 54016 54107 54225 54334 54452 54543 54670 54761 55004 55115 55237 55326 55440 55551 55662 55773 56071 56160 56254 56345 56403 56512 57063 57172 57246 57357 57421 57530 57614 57705 58027 58136 58894 58985 59035 59124 59606 59717
60482 60593 60618 60709 61490 61581 61639 61728 62819 62908 63838 63929 64051 64140 64273 64362 65043 65152 65261 65370 66037 66126 66600 66711 66872 66963 67025 67134 67407 67516 67641 67750 67883 67992 68006 68117 68235 68324 69014 69105 69227 69336 69653 69742
70491 70580 70829 70938 71483 71592 71808 71919 72884 72995 73860 73971 74242 74353 74400 74511 74688 74799 75072 75163 75250 75341 76422 76533 76617 76706 77620 77731 78034 78125 78207 78316 78652 78743 79026 79137 79215 79304
80895 80984 83882 83993 84060 84171 84413 84502 85401 85510 85623 85732 86435 86524 86642 86753 87470 87561 87636 87727 88041 88150 88214 88305 88426 88537 89007 89116 89240 89351
91893 91982 94489 94598 94601 94710 95412 95503 95630 95721 96451 96540 96673 96762 97443 97552 97699 97788 98055 98144 98260 98371 99061 99170 99256 99347 99885 99994
$\endgroup$
  • 1
    $\begingroup$ "Fewer than 4 digits do not work at all" - using this approach, yes, but that doesn't mean it's altogether impossible; see my answer. $\endgroup$ – RomanSt Sep 19 '16 at 21:39
1
$\begingroup$

My proposal was to sum the digits and take the units place (9 + 7 = 16 so take 6) and append it to two copies of the table number (97976).

When the code is received (say, 97971), if the first two pairs are the same, we use either pair (97). If changed digit is not the last one (say, 37976), we check whether the units place of sum of the first pair, and take the first pair if it matches the checksum, or the other pair otherwise (3 + 7 = 10 but 0 is not 6, so take 97 instead).

This uses 5 digits for a 100-table pub.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.